Replacing recursion with a while loop (stair climbing puzzle): Python
I am in the process of replacing recursion with while loops and I am stuck with the following problem.
How many ways can you climb a ladder of length n if you can only climb 1 or 2 ladder at a time?
The recursive solution is pretty simple:
def stairs(n):
if n <= 1:
return 1
else:
return stairs(n-2) + stairs(n-1)
It seems to me that the structure of an iterative program should look something like this:
def stairs_iterative(n):
ways = 0
while n > 1:
# do something
ways +=1
return ways
But I don't know what I need to contribute to the #do part. Can anyone help me? The pseudocode is fine!
source to share
This means a top-down (recursive) approach to a bottom-up (iterative) approach for dynamic programming.
Since you know n
you need all the values stairs(p)
for in order to enter 0 <= p <= n
. You can iteratively compute stairs(p)
starting at p = 0
until you reach p = n
as shown below:
def stairs(n):
table = [1, 1] # p = 0 and p = 1
for i in range(2, n + 1):
table.append(table[i - 2] + table[i - 1])
return table[n]
source to share
Another approach than @univerio is to use a stacked list:
def stairs_it(n):
res = 0
stack = [n]
while len(stack) > 0:
curr = stack[0]
stack.remove(curr)
if curr == 0:
res += 0
elif curr == 1:
res += 1
elif curr == 2:
res += 2
else:
stack.append(curr-1)
stack.append(curr-2)
return res
source to share