 A Taste of Recursion - dummies

Recursion is a big, scary word that you hear often about programming, especially the frustrating kind of programming that they teach at university. Though it’s an easy concept to describe, it’s really a mind-blower when it comes to understanding how recursion works. Most folks just accept it and move on. Not here!

Recursion is basically the process of a function calling itself. For example:

```void funct(int x)
{
funct(x);
}```

In this chunk of code, you see a terrible example of a recursive function, but it serves illustrative purposes here: The funct() function calls itself. That’s recursion. Now what happens in this example is basically an endless loop, and, thanks to a technical something-or-other, called the stack pointer, the computer eventually crashes. But it’s just an illustration.

For recursion to work, the function must have a bailout condition, just like a loop. Therefore, either the value passed to the recursive function or its return value must be tested. Here’s a better example of a recursive function:

```void recursion(int x)
{
if(x==0)
return;
else
{
puts("Boop!");
recursion(--x);
}
}```

The recursion() function accepts the value x. If x is equal to zero, the function bails. Otherwise, the function is called again, but the value of x is reduced. The decrement prefix operator is used so that the value of x is reduced before the call is made.

The sample recursion() function basically spits out the text Boop! a given number of times. So if recursion() is called with the value 10, you see that text displayed ten times.

The insane part about recursion is that the function continues calling itself, wrapping itself tighter and tighter, as though it’s in a spiral. In the preceding example, the condition x==1 finally unwinds that twisty mess, increasingly pulling back until the function is done.

The following code shows a full program using the sample recursion() function.

```#include <stdio.h>
void recursion(int x);
int main()
{
recursion(10);
return(0);
}
void recursion(int x)
{
if(x==0)
return;
else
{
puts("Boop!");
recursion(--x);
}
}```

A common demonstration of recursion is a factorial function. The factorial is the result of multiplying a value by each of its positive integers. For example:

4! = 4 × 3 × 2 × 1

The result of this factorial is 24. The computer can also make this calculation, by either implementing a loop or creating a recursive function. Here’s such a function:

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

As with the other recursive functions, the factorial() function contains an exit condition: x==1. Otherwise, the function is called again with one less than the current value of x. But all the action takes place with the return values.