## Recursion vs. Dynamic Programming Using a Question from AMC8

Here is an example from 2010 AMC8 Question \(25\) (American Mathmatical Competition):

Everyday at school, Jo climbs a flight of \(6\) stairs. Jo can take the stairs \(1\), \(2\), or \(3\) at a time. For example, Jo could climb \(3\), then \(1\), then \(2\). In how many ways can Jo climb the stairs?

\[\textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24\]### Recursion

This mathmatical question can be easily solved using the following python recursion code:

1
2
3
4
5
6
7
8
9
10

def stairs(x):
if x == 1:
return 1
elif x == 2:
return 2
elif x == 3:
return 4
else:
return stairs(x - 1) + stairs(x - 2) + stairs(x - 3)
print(stairs(6))

But, what if there is a quicker way? Letâ€™s try using dynamic progamming.

### Dynamic Programming

We can start with \(\text{step}_1\) as the last step, \(\text{step}_2\) as the second to last step, and \(\text{step}_3\) as the third to last step. According to the recursion code, if \(x\) is the current step, we have \(\text{step}_x = \text{step}_{x-1} + \text{step}_{x- 2} + \text{step}_{x - 3}.\)

Writing it in the dynamic programming way, we get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def stairs(x):
step1 = 1 # stair 1
step2 = 2 # stair 2
step3 = 4 # stair 3
run = 0
# This is x - 3, and not x because using this method,
# it starts from the stair 4
while run < x - 3:
temp = step1
step1 = step2
step2 = step3
step3 = temp + step1 + step2
run += 1
return step3
print(stairs(6))

which runs much faster than recusion.