get RecursionError when running Fibonacci function

Question

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?

This user had the same exact problem, check here for help: stackoverflow.com/questions/3323001/maximum-recursion-depth — rscarth
Try use the code in main page on python.org The big number of recursion cost much more processing. — user6320679

Keiwan Keiwan · Accepted Answer · 2016-05-20T16:02:23

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

get RecursionError when running Fibonacci function

2 Answers