- The basic idea of recursion is that you try to break down a big problem into similar but smaller subproblems.
In turn, each similar smaller subproblem is broken down into similar, even smaller subsubproblems. - You keep breaking problems down further and further until all the subsubsubsubproblems are small enough that you know how to solve them without breaking them down any further.
Because the smaller subproblems are "similar", you can make the function call itself with the smaller subproblem as input. But if it keeps calling itself indefinitely, that's like an infinite loop (and will eat up all the computer's memory), so you have to do two things: (1) make absolutely sure that every time the function calls itself, it's calling itself on a STRICTLY SMALLER subproblem, (2) make absolutely sure that the method the function uses to break things down is guaranteed to eventually produce a problem it can answer without calling itself.
Practically speaking, there's one other important consideration: at each step, the procedure for breaking a big problem down into smaller subproblems should not generate too many smaller subproblems. If the breakdown procedure at each step generates 10 subproblems, EACH of those subproblems may in turn generate 10 subsubproblems, EACH of which may generate 10 subsubsubproblems, etc. etc. This will rapidly eat up computer memory. Ideally, the breakdown procedure at each step should not generate more than 2 or 3 subproblems (3 is already a lot).
The basic conceptual outline of a recursive function is like this:
Code:
answertype recursive_function (problemtype problem)
{
answertype result;
if (problem is "bigger" than some level) {
do something to break the problem down into (hopefully only 1 or 2) smaller subproblems
result = some combination of recursive_function(subproblem1) and recursive_function(subproblem2)
}
else if (problem is "smaller" than some level) {
result = something that doesn't require having the function call itself
}
return result;
}
The factorial example is one where the problem is broken down into ONE smaller subproblem:
Code:
long factorial(int n)
{
long result;
if (n > 0) //"problem" is than some level
result = n * factorial(n-1); //note that the input to the subproblem is SMALLER now
else if (n==0) //"problem" is less than or equal to some level
result = 1; //note that function is not calling itself
else /* n < 0, invalid */
result = -1;
return result;
}
If you tried to pretend being the computer, here's what you would do for factorial(5):
Code:
factorial(5) = 5 * factorial(4) //break down factorial(5) into 5 * factorial(4)
= 5 * (4 * factorial(3)) //break down factorial(4) into 4 * factorial(3)
= 5 * (4 * (3 * factorial(2))) //break down factorial(3) into 3 * factorial(2)
= 5 * (4 * (3 * (2 * factorial(1)))) //break down factorial(2) into 2 * factorial(1)
= 5 * (4 * (3 * (2 * (1 * factorial(0))))) //break down factorial(1) into 1 * factorial(0)
= 5 * (4 * (3 * (2 * (1 * (1))))) //factorial(0) is easy: return 1
= 5 * (4 * (3 * (2 * (1)))) //factorial(1) now returns 1*1 = 1
= 5 * (4 * (3 * (2))) //factorial(2) now returns 2*1 = 2
= 5 * (4 * (6)) //factorial(3) now returns 3*2 = 6
= 5 * (24) //factorial(4) now returns 4*6 = 24
= 120 //factorial(5) now returns 5*24= 120
Your ruler function is an example where the problem is broken down into TWO smaller subproblems. I've rewritten it to conform to the conceptual outline above:
Code:
void subdivide(char ar[], int low, int high, int level)
{
if (level > 0) { //if "problem" is bigger than some level (i.e., level>0)
int mid = (high + low) / 2; //then do something to break it down into smaller subproblems
ar[mid] = '|'; //namely, draw a line in the middle of the ruler
subdivide(ar, low, mid, level - 1); //then subdivide the left half; problem is smaller because LEVEL is smaller
subdivide(ar, mid, high, level - 1); //and subdivide the right half; problem is smaller because LEVEL is smaller
return;
}
else if (level == 0) //eventually reaches LEVEL where function doesn't have to break down any more
return; //just returns without calling itself
}
If you tried to pretend being the computer, here's what you would do for subdivide(ar, 0, 8, 2):
Code:
0 1 2 3 4 5 6 7 8 //level==2>0, so do the stuff for level>0
//calculate mid=(8+0)/2==4
| //draw a line at ar[4]
//now subdivide(ar,0,4,1) (left subarray of 0,8). level==1>0, so do stuff for level>0
//calculate mid=(4+0)/2==1
| //draw a line at ar[2]
//now subdivide(ar,0,2,0) (left subarray of 0,4). level==0, so just return
//now subdivide(ar,2,4,0) (right subarray of 0,4). level==0, so just return
//now subdivide(ar,4,8,1) (right subarray of 0,8). level==1>0, so do stuff for level>0
//calculate mid=(8+4)/2==6
| //draw a line at ar[6]
//now subdivide(ar,4,6,0) (left subarray of 4,8). level==0, so just return
//now subdivide(ar,6,8,0) (right subarray of 4,8). level==0, so just return
//return
You can see that even though the subdivide function breaks problems down into only two subproblems (subdivide the left subarray, subdivide the right subarray), each of those subproblems is broken into 2 subsubproblems before level==0 and we could stop breaking down and just return.
This can rapidly get very hairy. Had we set level=3, there would have been 1 big problem, 1x2 subproblems, 1x2x2 subsubproblems, and 1x2x2x2 subsubsubproblems. Had we set level=6, there would have been 1x2**6 subsubsubsubsubsubproblems.
Recursion is conceptually elegant once you can understand it, but in practice it can rapidly eat up a lot of resources, even with not very big input.
What a waste of my valuable sugar molecules that went toward typing that explanation up.
