Recursive problems

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.

     
       function factorial(n) {
	  if (n == 0) {
		return 1
	  }
   	  return n * factorial(n - 1)
        }

        var num = input()
        output(factorial(num))
     
    

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₀=1, F₁=1 and F_n=F_n-1+F_n-2 .

And translating this into a program we have:

     
        function Fibonacci(n) {
	   if (n == 0 || n == 1) {
		return 1
	   }
	   return Fibonacci(n - 1) + Fibonacci(n - 2)
        }

        var num = input()
        output(Fibonacci(num))

     
    

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:

     
        function Fibonacci(n) {
	       output("Computing Fibonacci of " + n)
	       calls++
	       if (n == 0 || n == 1) {
		    return 1
	        }
	        return Fibonacci(n - 1) + Fibonacci(n - 2)
         }

         var calls = 0
         var num = input()
         output(Fibonacci(num))
         output(calls)


     
    

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.

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.