# A Taste of Recursion

*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 pointe**r**,* 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.