The Climb Function
The climb function C(m, n) is defined for non-negative integers by three rules:
C(0, n) = n + 1C(m, 0) = C(m - 1, 2)whenm > 0C(m, n) = C(m - 1, C(m, n - 1))whenm > 0andn > 0
Return C(m, n). The third rule calls the function inside its own argument, so a recursive function is the natural fit; the inputs are kept small enough that no memo table is needed.
For example, C(1, 1) = C(0, C(1, 0)) = C(0, C(0, 2)) = C(0, 3) = 4.
Example 1
m 1
n 1
returns 4
C(1, 0) is C(0, 2) = 3, and then C(0, 3) = 4.
Example 2
m 0
n 5
returns 6
The first rule applies directly: 5 + 1 = 6.
Constraints
0 <= m <= 30 <= n <= 60, andn <= 2whenm = 3
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Count the BlobsMedium
- Discs After k MovesMedium
- Distinct Arrangements in OrderMedium
- Every Route Through the GardenMedium
- Fair SplitMedium
- Fill In the BracketsMedium
- Hidden Word CountMedium
- Maze EscapeMedium