A recursive function is a function that calls itself.

We already saw an example of recursive program when we did the Greatest common divisor algorithm. Another typical example is the factorial of a number. The factorial of a number * n * is the product of 1*2..(n-1)*n. And it is written as * n!*. Mathematically we can see that this definition can also be described as: n!=n*(n-1)!. Here you can see that the function definition uses itself. To be able to do this we need some initial values, or else we could repeat it infinitely. For the factorial function the initial value is that 0! = 1. This base case is very important because it will allow the program to stop.

With this two definitions we can start programming our function.

Although some times the transformation between the recursive definition of a problem and the program itself might look easy, it is not always the best solution. A clear example is the Fibonacci numbers problem . As you can read in the wikipedia article, * by definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two. *

Translated into mathematical notation we get that F_{0}=1, F_{1}=1 and F_{n}=F_{n-1}+F_{n-2} .

And translating this into a program we have:

The main problem with this code is that we compute many times the same values. If we modify a little to see how many operations we use we can understand better what is happening:

If we check how many operations we need to compute the 10th number of Fibonacci the answer is 177 and the 11th requires 287 operations. If we do a table we will see the growth between consecutive numbers.

n | Value | Calls |
---|---|---|

10 | 89 | 177 |

11 | 144 | 287 |

12 | 233 | 465 |

13 | 377 | 753 |

Here we can notice 2 things. First of all the numbers grow in an exponential way (almost double every time). Second if we look closer each number (in the calls column) is the sum of the previous two plus 1. This comes from the fact that to compute the n-th fibonacci number we need to compute also the previous 2, and we have an extra call to sum those results.

But how can we make our program more efficient? This will be seen in the next part called Memoization.

Memoization is a technique in computer science where you store values you have already calculated to be able to access them in future queries. In this way you don't need to compute them twice.

In the previous example we computed Fibonacci numbers and we saw we did an exponential number of operations. If we apply memoization, this number can become linear. This means that a small increase of the input will require a small increase in the operations used. The program will look like this.

As you can see the array * values * will store all the Fibonacci numbers computed until that point. This algorithm is much faster than the previous one. You can try to compute the number of operations it does and study it's growth as in the previous example!

There are many projects that can be done with a little knowledge on recursive programming. Here are some codes of example. Try reading them and change whatever you want to explore! Good Luck!

Fibonacci spiral (using recursion as a substitute of an iterative process)

Plant (based on Lindenmayer Fractals)

Koch Fractal (from our Merry Everything article)