Simply put, recursion is when a function calls itself. That is, in the course of the function definition there is a call to that very same function. At first this may seem like a never ending loop, or like a dog chasing its tail. It can never catch it. So too it seems our function will never finish. This might be true is some cases, but in practice we can check to see if a certain condition is true and in that case exit (return from) our function. The case in which we end our recursion is called a base case . Additionally, just as in a loop, we must change some value and incremently advance closer to our base case.
For Example :-
void myFunction( int counter)
{
if(counter == 0)
return;
else
{
cout <<counter<<endl;
myFunction(--counter);
return;
}
}
Every recursion should have the following characteristics.
- A simple base case which we have a solution for and a return value. Sometimes there are more than one base cases.
- A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
- A recursive call which passes the simpler problem back into the function.