Recursion- The basics

Recursion is the process in which a function or sub-routine calls itself. It is similar to looping, except that for each iteration (calling) a new set of local data is created. Like looping, recursion must start somewhere, and must at some point stop recursing.

1 #include <stdio.h>
2 #include <stdlib.h>
3
4 int AddEm( void )
5 {
6 		int Sum=0, Value;
7 		printf("Enter value, or 0 to stop: ");
8 		scanf( "%d", &Value );
9 		if( Value != 0 ) /* 'If' decision may start new level of recursion, or terminate it */
10 			Sum = Value + AddEm(); /* Into recursion */
11 		return( Sum ); /* Returning from recusrion */
12 }
13 void main( void )
14 {
15 		int i;
16 		i=AddEm();
17 		printf("Total: %d\n", i);
18 }

In the example program above, AddEm is a recursive function, it calls itself in line 10 if the user entered a value other than 0. Every time the AddEm function is called, even if called by itself, a brand new Sum and Value are created. This re-creation of local variables is a key element of recursion.

Line 17 calls the recursive function, but this is not the start of recursion. In line 9, the AddEm function determines if the user entered a non-zero value. If they did, then recursion is entered be calling AddEm calling itself, and using the return value from that call.

However, once the user enters a zero value, then AddEm will not call itself again, it will simply return 0 to the caller. Depending on the data input by the user, Recursion may never be entered at all. The following represents the lines executed for a user's input:

User input: 0 Program lines: 13-16, 4-9, 11, 17

User Input: 1, 0 Program lines: 13-16, 4-10, 4-9, 11, 11, 17

User Input: 1, 2, 0 Program lines: 13-16, 4-10, 4-10, 4-9, 11, 11, 11, 17

Note how lines 4-10 are repeated, then the return of each recursive call (line 11) is performed. Each copy of local variables is still in existence at each level of recursion. And line 11 of each call is not reached unless the entered 0, of the call to AddEm in line 11 has returned.

Think of the call in line 10 as another function other than AddEm. Of course this function will not resume until after the called function has returned, the same operation holds true for this example of recursion. The realization that a new copy of local data for each function call may help clarification of recursion.

The Example above is actually an academic demonstration of recursion. The actual code would be better performed in a simple loop. In actual practice, recursion is often used as goal-find of problem-solving algorithms. Binary tree searches, data retrieval, maze searches, pattern matches, and other high-level applications are more practical of recursion in action.