Climbing Stairs Problem in DSA Typescript - Execution Trace

Concept Flow - Climbing Stairs Problem

Start at step 0

↓

Check if current step == target

Yes↓

Return 1 way

No↓

Calculate ways from step-1

↓

Calculate ways from step-2

↓

Sum ways from step-1 and step-2

↓

Return total ways

↓

Repeat until step == target

Start from step 0, recursively count ways to reach target by taking 1 or 2 steps, summing all possible paths.

Execution Sample

DSA Typescript

function climbStairs(n: number): number {
  if (n <= 1) return 1;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Counts ways to climb n stairs by summing ways to climb n-1 and n-2 stairs.

Execution Table

Step	Operation	Current n	Recursive Calls	Return Value	Visual State
1	Call climbStairs(3)	3	climbStairs(2), climbStairs(1)	3	Ways(3) = Ways(2) + Ways(1) = 2 + 1 = 3
2	Call climbStairs(2)	2	climbStairs(1), climbStairs(0)	2	Ways(2) = Ways(1) + Ways(0) = 1 + 1 = 2
3	Call climbStairs(1)	1	Base case	1	Ways(1) = 1
4	Call climbStairs(0)	0	Base case	1	Ways(0) = 1
5	Call climbStairs(1)	1	Base case	1	Ways(1) = 1
6	Return final result	3	None	3	Total ways to climb 3 steps = 3

💡 Reached base cases n=0 or n=1, return 1; recursion unwinds summing ways.

Variable Tracker

Variable	Start	After Call 1	After Call 2	After Call 3	Final
n	3	2	1	0	3
Return Value	N/A	2	1	1	3

Key Moments - 3 Insights

Why do we return 1 when n is 0 or 1?

Because at n=0 or n=1, there is exactly one way to stand still or take the last step, as shown in execution_table rows 3 and 4.

Why do we add climbStairs(n-1) and climbStairs(n-2)?

Because from step n, you can reach the top by taking either 1 step or 2 steps, so total ways are sum of ways from n-1 and n-2 steps, as in execution_table row 1.

Why does the recursion stop?

Recursion stops when n reaches 0 or 1, the base cases returning 1, preventing infinite calls, as seen in execution_table rows 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of climbStairs(2) at step 2?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Return Value' column in execution_table row 2.

At which step does the recursion reach the base case for n=0?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the row where n=0 and base case is mentioned in execution_table.

If climbStairs(n-2) was removed from the code, how would the total ways for n=3 change?

A It would become 3

B It would become 2

C It would become 1

D It would become 0

💡 Hint

The code would become `return climbStairs(n-1);`, which recurses down: climbStairs(3) -> climbStairs(2) -> climbStairs(1) -> base case 1, returning 1 up the chain.

Concept Snapshot

Climbing Stairs Problem:
- Count ways to reach step n
- Base cases: ways(0)=1, ways(1)=1
- Recurrence: ways(n) = ways(n-1) + ways(n-2)
- Recursive calls sum ways from previous two steps
- Stops when n <= 1
- Total ways = number of distinct sequences of 1 or 2 steps

Full Transcript

The Climbing Stairs Problem counts how many ways to climb n stairs taking 1 or 2 steps at a time. The code uses recursion: if n is 0 or 1, return 1 because there is only one way to stand or take the last step. Otherwise, return climbStairs(n-1) plus climbStairs(n-2), summing ways from previous steps. The execution table shows calls for n=3, breaking down into calls for n=2 and n=1, then base cases at n=1 and n=0 returning 1. The recursion stops at base cases and sums results on return. Key moments clarify why base cases return 1, why we add two recursive calls, and why recursion stops. The visual quiz tests understanding of return values, base cases, and effect of removing one recursive call.