Python Recursion Error: RecursionError: maximum recursion depth exceeded while calling a Python object

Question

I'm trying to build a function that will take in a number and then use recursion to print out a Fibonacci sequence and end the sequence on the number. So if I have a sequence that starts on 0 and 1 if the users input is 4 it will return 0,1,1,2,3. I am getting this RecursionError:

RecursionError: maximum recursion depth exceeded while calling a Python object

This is my code:

num = input("Give me a number.")
def fib(n):
 n = int(n)
 if n == 0:
 return 1
 return fib(n - 1) + fib(n - 2)
print(fib(num))

• Kevin: What should fib(-1) return? If you're thinking "fib never gets called with a negative argument", consider what return fib(n - 1) + fib(n - 2) does when n equals 1.
• Mark: You are not accounting for the possibilty that fib(n - 2) will give you an n of -1 when n is 1.
• ggorlen: If you do input like 1, I think you'll see the problem. Is fib(1 - 2) ever going to terminate?
• chepner: Spoiler alert: if you are patient enough, you are going to get a RecursionError for large values of n even if you fix the current issue. This is not a good way to compute arbitrary Fibonacci numbers.
• chepner: Save recursion for recursive data structures; for everything thing else, use loops.

Answer 1

Two problems

There are two problems with your code:

• There is an infinite loop, which generates the RecursionError exception
• It is impossible to retrieve all terms of the sequence (you said you want to print all the sequence, not only the last term)

The infinite loop

Try the code below. I just added n==1 as another stop condition.

def fib(n):
 n = int(n)
 if n == 0 or n == 1: # Changed here
 return 1
 return fib(n - 1) + fib(n - 2)
num = input("Give me a number: ")
print(fib(num))

The case f(1)=1 is required by definition (see here).
Or just debugging your code, you will realize that the loop will never end for fib(1) because it returns:
f(1-1) + f(1-2)>>> f(0) + f(-1)>>> 1 + infinite loop.

Printing all terms

You could try to use lists in your recursive code, which is tricky to do or perhaps change to a version with loops.

With loops:

# A version using a while loop
# This code returns the list of terms
def fib(n):
 n=int(n)
 terms = []
 i=0
 while i<=n:
 if i==0 or i==1:
 terms.append(1)
 else:
 terms.append(terms[-2]+terms[-1])
 i+=1
 return terms

Recursive:

Working on it

Try all these examples here .

Answer 2

The second call to fib is the problem. You pass the base case (exit condition) and continue to recurse without end. This generates the recursion error.

# to fix, replace "if n == 0:" with:
if n == 0 or n == 1:

Answer 3

The error occurred because you are using the wrong rule for Fibonacci... The Rule says that the initial number is 1 and 2 but you wrote your code starting in 0. Change your code:

num = input("Give me a number.")
def fib(num):
 n = int(num)
 if n == 1 or n == 2: # Changed here
 return 1
 return fib(n - 1) + fib(n - 2)
print(fib(num))