A little reminder about recursion

Calcul of the factorial of a number

This time, we change a bit the organization of the problem and we first recall the principle of the recursion. If you know very well this technique then go directly to the problem statement and try to solve it using the recursion.

The principle of the recursion is illustrated with the calculation of the factorial of a number. Let see the following famous recursive program to calculate the factorial of a number n:

   int factorial(int n)
            return 1;
            return n * factorial(n-1);

Let suppose than n = 5 and let see how it works:

This step is called the top-down execution and represents the first step of the recursion. The second step consists of the bottow-up execution and returns the final result by unstacking the intructions:

which returns 120.

Recursion in programming may be a very elegant way to solve some problems and turns out to be efficient provided that the depth of the recursion is not important. In this situation, the number of intructions in the stack can be large and it may be impossible to store it in memory. Recursion has to be used with caution.

Is this integer a palindrome ?

Problem statement

Write a function using recursion to determine if an integer is a palindrome. For example 123 is not a palindrome since the reverse of 123 is 321 which is not equal to 123. However 13931 is a palindrome since the reverse of 13931 is still 13931.