Skip to content

Instantly share code, notes, and snippets.

@JoaoGFarias
Forked from SpotlightKid/fibonacci.py
Last active August 29, 2015 13:56
Show Gist options
  • Save JoaoGFarias/8968958 to your computer and use it in GitHub Desktop.
Save JoaoGFarias/8968958 to your computer and use it in GitHub Desktop.
cpdef int fib(int n):
cpdef fibAux(int n, int a, int b):
if n == 0:
return a
else:
return fibAux(n-1,a+b,a)
if n == 2 or n == 1:
return n
elif n > 0:
return fibAux(n,0,1)
else:
raise ValueError('Fibonacci need be a natural number.')
if __name__ == '__main__':
print(fib(992))
@JoaoGFarias
Copy link
Author

Here, you can see Fibonacci with tail-call recursion.
It allows the compiler to do tail-call optimization and don't blow up
the call stack when dealing with deep recursions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment