Staircase problem solved using recursion

Problem

Question taken from here.

I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs? Write a function count_stair_ways that solves this problem for me.
def count_stair_ways(n):

Solution:

def count_stair_ways(n):
    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
    return count_stair_ways(n-1) + count_stair_ways(n-2)

Can we improve this code?

The staircase problem actually just generates the Fibonnacci sequence.

Whilst the recursive solution is nice, without memoization you're much better off just using a loop:

def count_stairways(n):

   a, b = 0, 1
   for _ in range(n):
       a, b = b, a+b

   return b

A nice alternative if you want multiple values out is to create a generator:

def count_stairways():

    a, b = 0, 1
    while True:
        a, b = b, a+b
        yield b

If you just want a particular value (possibly for a large n), the fibonnacci sequence actually has a closed form

def count_stairways(n):

     phi = (1 + math.sqrt(5)) / 2

     return int((pow(phi, n+1) - pow(1-phi, n+1))/math.sqrt(5))

StackExchange Code Review Q#96197, answer score: 9