Count Paths in a Grid (Recursive)

Hard ⏱ 18 min 34% acceptance ★★★★☆ 4.4
A robot starts at the top-left corner of an m x n grid and can only move right or down. Implement count_paths(m, n) returning the number of distinct paths to the bottom-right corner, using pure tree-like recursion: each cell branches into the path count of the cell to its right plus the cell below it.

Examples

Example 1
Input
count_paths(3, 3)
Output
6
Explanation

A 3x3 grid has C(4,2) = 6 distinct right/down paths.

Example 2
Input
count_paths(1, 5)
Output
1
Explanation

A single row only has one path: straight across.

Constraints

  • 1 <= m, n <= 15 (bounds the recursion tree size).
  • No memoization — this problem is about the raw branching recursion.

Topics

RecursionTree-Like Recursion

Companies

GoogleMetaUber

Hints

Hint 1

Base case: if m == 1 or n == 1, there is exactly 1 path.

Hint 2

Recursive case: count_paths(m - 1, n) + count_paths(m, n - 1).

← Reverse a String Using Recursion Sum 1..N — Accumulator vs Plain Recursion →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.