Fibonacci numbers not getting printed beyond F(996)

Question

I wrote this small snippet to calculate Fibonacci numbers. It works well for numbers up to 996 and from 997 a trace back is being printed. I can't figure out what the problem is. Does it has something to do with maximum_recursion_count?

def fib(n):
 if n==0:
  return 0
 elif n==1:
  return 1
 else:
  return fib(n-1)+n

Answer 1

There is a wonderful Fibonnaci function implementation here that doesn't use recursion.

Answer 2

Your code may come up against stack call limits.

Answer 3

Probably. Take a look at sys.getrecursionlimit(). The default value is 1000, which sounds like it just might be causing the problem you're seeing: once there are 1000 frames on the stack (i.e. slightly less than 1000 recursive function calls), you'll get an error on the next function call.

You can set the recursion limit to a larger value using sys.setrecursionlimit, but there is a maximum value which is platform-dependent (which means you might have to figure out what it is by trial and error).

Answer 4

You have reached the maxmimum recursion depth limit. As far as I know its default value is about 1000. You can change it sys.setrecursionlimit() and see it using sys.getrecursionlimit()

Answer 5

You say "It works well for numbers up to 996" ... No, it doesn't, it generates the wrong results. The last line should be:

return fib(n - 1) + fib(n - 2)