How to create a recursive function to calculate Fibonacci numbers

Question

def fib(n):
    if n == 0:
        return 0
    elif n ==1:
        return 1
    else:
        return fib (n-1) + fib (n-2)

How do I make this recursive? When I run the programme and enter a digit, the same digit is given back

Answer 1

Your function is already recursive. You simply need to pass in a number other than 0, 1, or 5 to see the effect:

>>> def fib(n):
...     if n == 0:
...         return 0
...     elif n ==1:
...         return 1
...     else:
...         return fib (n-1) + fib (n-2)
... 
>>> fib(0)  # returns immediately, because n == 0
0
>>> fib(1)  # returns immediately, because n == 1
1
>>> fib(2)  # returns fib(1) + fib(0) == 1 + 0 == 1
1
>>> fib(3)  # returns fib(2) + fib(1) == (fib(1) + fib(0)) + 1 == (1 + 0) + 1 == 2
2
>>> fib(100) # returns fib(99) + fib(98) == (fib(98) + fib(97)) + (fib(97) + fib(96)) == ...
# This one takes a while because 2**100 calculations need to be completed
354224848179261915075

Answer 2

Your solution is an example about what can go wrong with recursion, because it exhibits quadratic complexity for a problem that has a trivial solution with linear complexity. You normally wouldn't use recursion here. That said, it is possible to use recursion here an keep linear complexity:

def fib(n):
    def aux( n ):
        if( n==1 ):
            return (0, 1)
        else:
            (a,b) = aux( n-1 )
            return b, a+b
    return  aux(n)[1]

Answer 3

As an exercise, here's a Fibonacci Sequence Generator that does not use recursion and therefore won't hit Python's recursion limit for large values of n:

def fib():
    a, b = 0, 1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

Example:

>>> f = fib()
>>> next(f)
0
>>> next(f)
1
>>> next(f)
1
>>> next(f)
2
>>> next(f)
3
>>> next(f)
5
>>> next(f)
8
>>> next(f)
13

First 10 Fibonacci Numbers:

>>> from itertools import islice
>>> list(islice(fib(), 0, 10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Answer 4

The function is already recursive, and correct. You must have used a very small number of tests. If your testing method produced these results, you can only have used some of the digits 0, 1, and 5. Try larger integers.