Advanced · Recursion · 165 of 264
Paths in a grid
In a grid of r rows and c columns you start top-left and may only move right or down. How many different paths reach the bottom-right? Use recursion with memoisation (remember answers you have already worked out).
Input: r and c (1 to 16), one per line. Output: the number of paths.
Examples
Input
2 2
Output
2
Input
3 3
Output
6
Input
1 5
Output
1
One more test checks other inputs when you press Check.
Stuck? The idea behind recursion
A recursive function calls itself on a smaller version of the problem, until it reaches a case small enough to answer directly (the base case).
Trust the smaller call to be right, and only work out how to build this answer from it.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5))Watch for: Without a base case, or if the problem doesn't get smaller, it never stops: Python gives up with a RecursionError.