Recursion in C and C++
Recursion is a programming technique that allows the programmer to express
operations in terms of themselves. In C++, this takes the form of a function
that calls itself. A useful way to think of recursive functions is to imagine
them as a process being performed where one of the instructions is to "repeat
the process". This makes it sound very similar to a loop because it repeats
the same code, and in some ways it is similar to looping. On the
other hand, recursion makes it easier to express ideas in which the result of
the recursive call is necessary to complete the task. Of course, it must be
possible for the "process" to sometimes be completed without the recursive
call. One simple example is the idea of building a wall that is ten feet
high; if I want to build a ten foot high wall, then I will first build a 9
foot high wall, and then add an extra foot of bricks. Conceptually, this is
like saying the "build wall" function takes a height and if that height is
greater than one, first calls itself to build a lower wall, and then adds one
a foot of bricks. A simple example of recursion would be:
void recurse()
{
recurse(); //Function calls itself
}
int main()
{
recurse(); //Sets off the recursion
}
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 <iostream>
using namespace std;
void recurse ( int count ) // Each call gets its own count
{
cout<< count <<"\n";
// 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
}
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, it is not a function restarting itself, it is hundreds of functions that are each unfinished with the last one calling a new recurse function.
It can be thought of like the Russian dolls that always have a smaller doll inside. Each doll calls another doll, and you can think of the size being a counter variable that is being decremented by one.
Think of a really tiny doll, the size of a few atoms. You can't get any
smaller than that, so there are no more dolls. Normally, a recursive function
will have a variable that performs a similar action; one that controls when
the function will finally exit. The condition where the function will not call itself is termed the base case of the function. Basically, it is an if-statement that checks some variable for a condition (such as a number being less than zero, or greater than some other number) and if that condition is true, it will not allow the function to call itself again. (Or, it could check if a certain condition is true and only then allow the function to call itself).
A quick example: |
