After factorial, the most common example of a recursively deﬁned mathematical function is fibonacci, which has the following deﬁnition (see http://en.wikipedia.org/ wiki/Fibonacci_number):):
ﬁbonacci(0)= 0 ﬁbonacci(1)= 1 ﬁbonacci(n)= ﬁbonacci(n − 1)+ ﬁbonacci(n − 2)
Translated into Python, it looks like this:
def fibonacci (n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2)
If you try to follow the ﬂow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if you assume that the two recursive calls work correctly, then it is clear that you get the right result by adding them together.