This usually means trying to think of a smaller instance of the problem, assuming that the smaller instance can be solved, and using that solution to solve the bigger problem.
Nevertheless, it's fairly easy to convert a for-loop to recursion, should you choose to do so.
Here's a typical loop.
for ( <init> ; <cond> ; <update> )
<body>
This can be converted to two functions: the main function
and the helper recursive function.
void recFunc() {
int loopVar = <init>
recHelperFunc( loopVar );
}
void recHelperFunc( int loopVar ) {
if ( <cond> ) {
<body>
<update>
recHelperFunc( loopVar ); // recursive call
}
}
The loop has been replaced by an if-statement. The recursive
call at the end replaces the loop. Since the looping variable
is being updated, you can save some memory by passing the variable
by reference.
However, the looping variable can be passed by value as well. Sometimes, it's nicer to pass by value, because if you pass by reference, then you must pass something that looks like a variable. Passing an expression (e.g., i + 1) is not allowed for a non-const reference, but is permitted for a value parameter.
Let's look at how to convert a simple loop.
for ( int i = 0 ; i < n ; i++ )
cout << i << endl;
Suppose that n is a variable, then, you need two
parameters in the recursive helper function.
void recFunc() {
int i = 0 ;
recHelperFunc( i, n ) ; // recursive call
}
void recHelperFunc( int i, int n ) {
if ( i < n ) { // condition of loop
cout << i << endl ;
i++;
recHelperFunc( i, n ) ; // recursive call
}
}
In general, you should avoid using ++ on variables that are
passed as arguments. In particular, don't use post-increment
or post-decrement, since, in principle, the update won't occur
until AFTER the function call, and at that point, you will cause
infinite recursion.
It's better to update the value prior to calling the function, and pass the variable in. Alternately, if you are passing by value, use an expression that is not side-effecting. i++ has a side effect (it updates i), where as i + 1 is not side effecting (it doesn't update i).
Recall that when you pass an argument by value, a copy is created. Thus, every single time recHelperFunc(), a new copy of i and n are created.
Admittedly, this is somewhat of a waste because n never changes, but recursion often does this.
void printIt( int n );The recursive call passes in n.
Now, what would be a smaller recurisve call?
void printIt( n - 1 );
This function would print out 0 up to n - 2. If this
occurred, what would we do to print the rest? You would print
n - 1. The base case is when n == 0.
So, here's how you would write the code in a more traditional
recursive way.
void printIt( int n ) {
if ( n == 0 ) { // base case
cout << 0 << endl;
}
else { // recursive case
printIt( n - 1 ); // recursive call
cout << n - 1 << endl;
}
}
Notice that you pass one fewer parameter this way, although it
doesn't match up with the loop nearly as well. In general, you
would "prefer" to do it this way, because it's more "natural" when
writing recursive functions.
Here's an analogy. There are two ways to learn a foreign language. Either learn a foreign language by learning it like native speakers speak it, or learn to translate every word in your native language to the foreign language. The second method works, somewhat, but isn't as "fluent" as the first.
For coding, of course, it doesn't matter which method, as long as it works, but nevertheless, the second method we looked at it more "fluent" since the problem is solved from the usual methodology of solving smaller problems and using it to solve bigger problems.
Occasionally, you must use the loop method to come up with a recursive call, because not all problems are nearly as easy to break down into smaller cases.