1
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

georg
  • 204,715
  • 48
  • 286
  • 369
user3181877
  • 9
  • 1
  • 1
  • 2
  • possible duplicate of [How to write the Fibonacci Sequence in Python](http://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence-in-python) – Martijn Pieters Jan 10 '14 at 13:55
  • How do you invoke this function? – aga Jan 10 '14 at 13:57
  • @aga With either fib(0), fib(1), or fib(5). See Martijn's [answer](http://stackoverflow.com/a/21046091/667820) – Henk Langeveld Jan 10 '14 at 14:13
  • @HenkLangeveld I know how to make a call of function, I wanted to know how exactly OP does that - this function is already recursive, so in order to get the issue he gets ("When I run the programme and enter a digit, the same digit is given back") he has to call it in a wrong manner. – aga Jan 10 '14 at 16:35
  • 1
    @aga, I was trying to point out that OP's test methods were not exhaustive. For any value from [0,1,5], he will get the described results. OP's sample space was too small. – Henk Langeveld Jan 10 '14 at 18:08
  • @HenkLangeveld I feel sooo stupid, many thanks for clarification. :) – aga Jan 10 '14 at 19:57

4 Answers4

6

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
Henk Langeveld
  • 7,670
  • 42
  • 56
Martijn Pieters
  • 963,270
  • 265
  • 3,804
  • 3,187
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]
pentadecagon
  • 4,527
  • 1
  • 17
  • 25
  • OP's code time complexity is not quadratic; it is exponential (that is much much worse). – jfs Jan 10 '14 at 14:48
0

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]
James Mills
  • 17,799
  • 3
  • 45
  • 59
0

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.

Henk Langeveld
  • 7,670
  • 42
  • 56