1

I am trying to use a recursive function to calculate the fibonacci sequence. This is what I have come up with:

import sys
new_recursion_limit=3000
sys.setrecursionlimit(new_recursion_limit)
fibonacci_cache = {}


def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    if n == 1:
        return 1
    else:
        result = fibonacci(n - 1) + fibonacci(n - 2)
        fibonacci_cache[n] = result
        return result



number = int(input("Enter the number for fiboonacci value: "))
result = fibonacci(number)
print(f"The value of fibbonaci {number} is {result}")

I used chatGPT so that I can have a basic idea to implement the method. The error I receive is a RecursionError: maximum recursion depth exceeded. even for the int 5 I am receiving this error. I am a beginner in programming and I am trying to implement the recursive function so that I have a proper idea about the functioning. Can anyone please help me with this error?

When I received the error I tried to use sys function to se a recursive limit. Th repetation is 1000+ in this case. I was expecting the recursive function to work normally. but I still receive the error.

Harikrishnan Venugopal
  • 13
  • 2
  • 3
    if `n` is `2` what is `fibonacci(n - 2)` since you only treat n of 1 as a special case.... – JonSG Aug 04 '23 at 14:13
  • 1
    Note: [The recursion limit is not the limit on recursion but the maximum depth of the python interpreter stack](https://stackoverflow.com/questions/38265839/max-recursion-is-not-exactly-what-sys-getrecursionlimit-claims-how-come/38265931#38265931) – jarmod Aug 04 '23 at 14:13
  • 1
    Add a `print(n)` at the top of your fibonacci function. See what happens. – jarmod Aug 04 '23 at 14:14

4 Answers4

2

As has been pointed out, the core issue here is that you need to account for two special cases, n == 1 and n == 0. You can do that in your code, but since you are manually initializing a cache you can also just do it there.

## ----------------
## initialize our cache in a way that will
## handle our special cases. Note that this
## also simplifies our method.
## ----------------
fibonacci_cache = {0: 0, 1: 1}
## ----------------

def fibonacci(n):
    if n not in fibonacci_cache:
        fibonacci_cache[n] = fibonacci(n-1) + fibonacci(n-2)
    return fibonacci_cache[n]

number = int(input("Enter the number for fiboonacci value: "))
result = fibonacci(number)
print(f"The value of fibbonaci {number} is {result}")

At this point, you might add in a test to ensure that n >= 0 and throw a ValueError if not, but I'll leave that to you to consider.

JonSG
  • 10,542
  • 2
  • 25
  • 36
1

The problem comes when your code gets to the recursive call of fibonacci(2).

Inside this call, it will then call fibonacci(1) and fibonacci(0).

In the fibonacci(1) call, it will hit the if n == 1 condition, and properly terminate with a return value of 1.

But the fibonacci(0) call does not stop; it calls fibonacci(-1) and fibonacci(-2). And the negative numbers just keep growing from there.

You need to account for the case where n is zero.

John Gordon
  • 29,573
  • 7
  • 33
  • 58
0

Assume n=2, your else in your function would be met, then it faces fibonacci(n - 1) + fibonacci(n - 2), which is fibonacci(1) + fibonacci(0).

fibonacci(1) is 1, but you didn't provide anything for fibonacci(0), so again your else would be met and you will have fibonacci(-1) + fibonacci(-2) and this will happen infinitely.

So simply just provide a return value for case of n=0:

def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    ...
Amin
  • 2,605
  • 2
  • 7
  • 15
-1

Look at what your function does when it receives n=2

zoola969
  • 452
  • 2
  • 2