tutorialsPythonBasic.basic.recursion.recursion_examples module¶

A function is recursive when it calls itself (on a smaller piece of the problem). We need to provide a ‘stopping criterion’ or else the function will call itself indefinitely (therefore hanging the program).

Wikipedia link on Recursion:: http://en.wikipedia.org/wiki/Recursion_(computer_science)

You can find some simple examples of recursion below, but recursion will also be used in other examples (for instance in some sorting algorithms).

tutorialsPythonBasic.basic.recursion.recursion_examples.factorial(n)[source]¶

A factorial of n (n!) is defined as the product of all positive integers less then or equal to n. According to the convention for an empty product, the value of factorial(0) (0!) is 1.

>>> [factorial(i) for i in range(11)]
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

tutorialsPythonBasic.basic.recursion.recursion_examples.fibonacci(n)[source]¶

Find the n-th fibonacci number - the first two numbers are 1, the third one is the sum of the first two, the fourth one is the sum of the second and the third, ... meaning that fibonacci(n) = fibonacci(n-1) + fibonacci(n-2).

This example also shows one of the possible problems with recursion - we calculate the same things over and over again! For instance, if we call fibonacci(5), we get a tree like this:

        5
       3
 2     2   1
1

As you can see, we called fibonacci(1) 2 times, fibonacci(2) 3 times and fibonacci(3) 2 times. Of course this can grow very fast, so if you call something like fibonacci(50), it can take a very long time to calculate the result.

>>> [fibonacci(i) for i in range(1, 11)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

tutorialsPythonBasic.basic.recursion.recursion_examples.fibonacci_smarter(n)[source]¶

A smarter implementation of fibonacci - when we calculate a value, we save it inside the ‘fibonacci_smarter_helper’, so we do not have to calculate it again if (when) we need it again, we just get it from the helper.

>>> [fibonacci_smarter(i) for i in range(1, 11)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> fibonacci_smarter(75)
2111485077978050

tutorialsPythonBasic.basic.recursion.recursion_examples.gcd(a, b)[source]¶

Find the greatest common divisor using Euclid’s algorithm.

>>> gcd(1, 3)
1
>>> gcd(2, 10)
2
>>> gcd(6, 9)
3
>>> gcd(17, 289)
17
>>> gcd(2512561, 152351)
1