This program will not continue forever, however. The computer keeps function calls on a stack and once too many are called without ending, the program will crash. Why not write a program to see how many times the function is called before the program terminates?
#include <stdio.h>
void recurse ( int count ) /* Each call gets its own copy of count */
{
printf( "%d\n", count );
/* It is not necessary to increment count since each function's
variables are separate (so each count will be initialized one greater)
*/
recurse ( count + 1 );
}
int main()
{
recurse ( 1 ); /* First function call, so it starts at one */
return 0;
}
This simple program will show the number of times the recurse function has been called by initializing each individual function call's count variable one greater than it was previous by passing in count + 1. Keep in mind that it is not a function call restarting itself; it is hundreds of function calls that are each unfinished.
The best way to think of recursion is that each function call is a "process" being carried out by the computer. If we think of a program as being carried out by a group of people who can pass around information about the state of a task and instructions on performing the task, each recursive function call is a bit like each person asking the next person to follow the same set of instructions on some part of the task while the first person waits for the result.
void count_to_ten ( int count )
{
/* we only keep counting if we have a value less than ten
if ( count < 10 )
{
count_to_ten( count + 1 );
}
}
int main()
{
count_to_ten ( 0 );
}
This program ends when we've counted to ten, or more precisely, when count is no longer less than ten. This is a good base case because it means that if we have an input greater than ten, we'll stop immediately. If we'd chosen to stop when count equaled ten, then if the function were called with the input 11, it would run out of memory before stopping.
void printnum ( int begin )
{
printf( "%d", begin );
if ( begin < 9 ) /* The base case is when begin is no longer */
{ /* less than 9 */
printnum ( begin + 1 );
}
/* display begin again after we've already printed everything from 1 to 9
* and from 9 to begin + 1 */
printf( "%d", begin );
}
This function works because it will go through and print the numbers begin to 9, and then as each printnum function terminates it will continue printing the value of begin in each function from 9 to begin.