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

for i in range(5):
    print(fib(i))

I want to print first 5 result of Fibonacci sequence only to get

RecursionError: maximum recursion depth exceeded in comparison

I think there is an exit of every positive n and print(fib(4)), print(fib(20)) and print(fib(100)) works perfectly.

What's wrong with my code?

kalikkkk
  • 3
  • 2
  • This user had the same exact problem, check here for help: http://stackoverflow.com/questions/3323001/maximum-recursion-depth – rscarth May 20 '16 at 16:02
  • Try use the code in main page on python.org The big number of recursion cost much more processing. –  May 20 '16 at 16:02

2 Answers2

2

range(5) starts at 0 and since you are not checking for 0 in your function, the recursion never ends.

As a sidenote, you are not calculating the fibonacci sequence correctly, you should add up 

fib(n-1) + fib(n-2)

Try this:

def fib(n):
    if n <= 2:
        return n
    return fib(n-1) + fib(n-2)

A generally better approach at calculating the n-th fibonacci number is to use a loop, since you end up calculating the same values over and over again if you use recursion. Using a loop you can do it like this:

def fibonacci(n):    
    if n < 2:
       return 1

    a = 1
    fib = 1
    for i in range(n-2):
        a, fib = fib, a + fib            
    return fib
Keiwan
  • 8,031
  • 5
  • 36
  • 49
  • It's probably better to use `if n < 2:` and `return n` (fib(0) needs to be 0, if fib(1) and fib(2) are both 1, since we know that `fib(n -2) == fib(n) - fib(n - 1)` . Of course, that potentially leaves fib(-1) at the wrong value, but, you know... – Vatine May 20 '16 at 16:12
  • Yeah, you're right about that. Also about the fact that if the OP wants to be 100% exact they would have to add a check for negative inputs, since fibonacci is only defined for `n >= 0` , but yeah, for our purposes I think we can assume that n is not negative. – Keiwan May 20 '16 at 16:18
1

there is an exit of every positive n.

Yes, there is. But how about fib(0)?

Try print(list(range(5)))

Rahn
  • 4,787
  • 4
  • 31
  • 57