What Is Recursion in Programming?

In computer programming, recursion occurs when a function or procedure -- in other words, a sequence of instructions for performing a particular function -- calls itself, either directly or indirectly. The function or procedure modifies the value of the parameter(s) passed to it the first time it is called and calls itself with the new value(s).

The classic example of recursion involves computing factorials. A factorial is the product of any given positive whole number multiplied by all lesser whole numbers. The factorial of 5 is 5*4*3*2*1, the factorial of 4 is 4*3*2*1 and so on. The factorial of any number is equal to that number multiplied by the factorial of the number immediately below it. In other words, factorial(5) is the same as 5 * factorial(4), factorial (4) is the same as 4 * factorial(3) and so on, so a simple factorial function could be written as:

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

The problem with this simple function, however, is that it has no base case, or condition to tell it when to stop. As it stands, the function would continue to call itself when n reached zero and beyond into negative numbers, returning nonsensical factorials. In reality, a factorial function needs to stop when n = 1, so a real factorial function could be written as:

int factorial(int n)
{
if(n == 1)
{
return 1;
}
else
{
return n * factorial(n - 1);
}
}