-2

So here is the 2 python codes of Fibonacci series using recursive function. I wanted to know the difference between these code and why code(1) is not working, and code(2) works without any error?

This is not working and shows error of maximum recursion limit:

def f(n):
   return f(n-1) + f(n-2)

n=8
f(n)

whereas this works:

def f(n):
   if n == 0:
      return 0
   if n == 1:
      return 1
   else:
      return f(n-1) + f(n-2)

f(4)
natn2323
  • 1,983
  • 1
  • 13
  • 30
logic bomb
  • 11
  • 1
  • 1
    because your recursion has no break condition and it recurses into infinity – Patrick Artner Oct 30 '18 at 20:39
  • questions like this are easily answered by debugging the code yourself - read about it here: [python debugging tips](https://stackoverflow.com/questions/1623039/python-debugging-tips) – Patrick Artner Oct 30 '18 at 20:43
  • See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. – Prune Oct 30 '18 at 20:48

1 Answers1

2

Your first code has no way of stopping. It does not have the base cases for n == 0 or n == 1, so it will continue infinitely downwards with negative numbers.

If you add:

  if n <= 1:
      return 0

you're golden. (allthough it is a very inefficient implementation of fibonacci).

Why is it inefficient, well because each subtree are calculated many times over. f(8) calls f(7) and f(6), but f(7) also call f(6), so you get an exponential recursive tree. Your running time will be O(2^n). This is really bad, normally you will not be able to calculate fib for n even as low as 50.

You can do better if you include memoization:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib2(n):
    if n <= 1:
        return n
    else:
        return fib2(n-1) + fib2(n-2)

This will remember if you have called f(n) before and return the answer you did last time. The issue now is that you need to remember previous called numbers, so while your running time has decreased to O(n), your space requirement is now O(n) too.

You can improve on this again, by abandoning recursive functions all together and go 

def fib3(n):
if n == 0:
    return 0
f1 = 0
f2 = 1

for i in range(n-1):
    f1,f2 = f2, f1+f2
return f2

This is better, since you are only remembering two numbers at any time.

Christian Sloper
  • 7,440
  • 3
  • 15
  • 28