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))

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. — Kevin
– Kevin, Commented Mar 13, 2020 at 15:30
You are not accounting for the possibilty that fib(n - 2) will give you an n of -1 when n is 1. — Mark
– Mark, Commented Mar 13, 2020 at 15:30
If you do input like 1, I think you'll see the problem. Is fib(1 - 2) ever going to terminate? — ggorlen
– ggorlen, Commented Mar 13, 2020 at 15:30
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
– chepner, Commented Mar 13, 2020 at 16:06
Save recursion for recursive data structures; for everything thing else, use loops. — chepner
– chepner, Commented Mar 13, 2020 at 16:07

ePi272314 · Accepted Answer · 2020-03-19 23:29:37Z

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.

user12364557 · Accepted Answer · 2020-03-13 15:35:38Z

1

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:

answered Mar 13, 2020 at 15:35

user12364557

Comments

score 0 · Accepted Answer · 2020-03-13 20:29:31Z

0

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))

edited Mar 13, 2020 at 20:29

answered Mar 13, 2020 at 16:25

user13052453

Collectives™ on Stack Overflow

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

3 Answers 3

Two problems

The infinite loop

Printing all terms

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Two problems

The infinite loop

Printing all terms

Comments

Comments

Comments

Related