Your code is easy to understand and just works but it can still be improved.
Documentation
It could be nice to add some documentation to tell which values are expected.
Domain
When I tried with 0
as an input, I got a RuntimeError: maximum recursion depth exceeded
. This is because the recursion calls go deeper and deeper into negative numbers without reaching a stop.
Adding :
if n < 0:
return 0
if n == 0:
return 1
just solves this problem. By the way, there is 1 way to flight a 0 stair case step.
Tests
It is a good habit to add tests for your code. I won't dive into testing framework and everything but just adding :
if __name__ == "__main__":
for n, value in enumerate([1, 1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55]):
res = count_stair_ways(n)
assert res == value, "exp:%d got:%d for n = %d" % (value, res, n)
gives you a nice way to see if things ever go wrong.
Keep it simple
Once you handle all n <= 0
, you don't need to handle the cases 1 and 2 individually. You can remove :
if n == 1: # 1 way to flight 1 stair case step
return 1
if n ==2: # 2 ways to flight 2 stair case steps(1+1, 2)
return 2
and see that it still works fine.
At this point, the code becomes :
def count_stair_ways(n):
""" Some doc. Input can be any integer n."""
if n < 0:
return 0
if n == 0:
return 1
return count_stair_ways(n-1) + count_stair_ways(n-2)
if __name__ == "__main__":
for n, value in enumerate([1, 1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55]):
res = count_stair_ways(n)
assert res == value, "exp:%d got:%d for n = %d" % (value, res, n)
Performance
Your solution will be slow for any big (or even medium) inputs. You can easily see add a print statement at the beginning of the function to see how many times it gets called and you'll see that we compute the same things many times.
When n is 15, the function gets called that many times with the different inputs :
610 -1
987 0
610 1
377 2
233 3
144 4
89 5
55 6
34 7
21 8
13 9
8 10
5 11
3 12
2 13
1 14
1 15
There must be a better way.
Using memoization is the way to go but there's an even easier option involving a simple loop.
def count_stair_ways(n):
""" Some doc. Input can be any integer n."""
a, b = 0, 1
for _ in range(n + 1):
a, b = b, a + b
return a
Going further
You sequence actually corresponds to Fibonacci numbers. You'll find various super efficient way to compute them.
for i in range(n)
construction? \$\endgroup\$