+ 1

# Fibonacci on Python

can someone explaine me how this works " return (fib(n-1)+fib(n-2))" the code works but I want to understand how. def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return (fib(n-1)+fib(n-2))

3 Answers

+ 5

Let's try the classic analogy
You are standing in a line and you want to know your position from the front. You ask the person in front of you, but they don't know either. So they ask the person in front of them, this continues until you reach the front of the line with a position 1
Then each person responds to the question by taking the answer they got and adding 1. Until it gets back to you with your position.
Recursion naturally has a zip down to the base case and then zip back up to the original function call with the returned values.

+ 2

And don't forget to stop at the "base case".
http://ryepup.unwashedmeme.com/blog/wp-content/uploads/2007/11/infinite-recursion.jpg
In this Fibonacci sequence the base case is n=0 and n=1, because the rest of the series is calculated from these two values.

+ 2

Thank you!