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.
Consider this function.
void myFunction( int counter)
{
if(counter == 0)
return;
else
{
cout <<
myFunction(--counter);
return;
}
}
This recursion is not infinite, assuming the function is passed a positive integer value. What will the output be?
Consider this function:
void myFunction( int counter)
{
if(counter == 0)
return;
else
{
cout<<"hello"<<
myFunction(--counter);
cout<<
return;
}
}
If the function is called with the value 4, what will the output be? Explain.
The above recursion is essentially a loop like a for loop or a while loop. When do we prefer recursion to an iterative loop? We use recursion when we can see that our problem can be reduced to a simpler problem that can be solved after further reduction.
Every recursion should have the following characteristics.
A simple base case which we have a solution for and a return value.
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.
The key to thinking recursively is to see the solution to the problem as a smaller version of the same problem. The key to solving recursive programming requirements is to imagine that your function does what its name says it does even before you have actually finish writing it. You must pretend the function does its job and then use it to solve the more complex cases.
