Chapter 3: Recursion
Definition: Recursion is a process in which a module achieves a repetition of algorithmic steps by calling a clone of itself. It does this via a recursive call: a call from within a procedure or function in which its own identifier is used.
There are two forms of recursion:
Form 1
If (terminating condition) then
Do final actions
Else
Take one step closer to terminating condition
Call “clone” of module
Endif
Form 2
If (not(terminating condition)) then
Take a step closer to terminating condition
Call “clone” of module
Endif
Form 1 is generally associated with a Function since a function must always return something (Do final actions).
Form 2 could be either a function and/or a procedure.
A recursive module must have a terminating condition and it is necessary to reach that terminating condition. So some sort of initial condition must also exist or be determined. In the case of Form 1, after the terminating condition is reached, the module still goes on to do something else (but no more recursion) whereas in Form 2, after the terminating condition is reached, the module is exited.
The following is a recursive algorithm that will print the numbers from 1 to 10.
void print_numbers (counter isoftype int)
if (not(counter > 10)) then
print (counter)
print_numbers(counter + 1)
endif
endmethod
Note that this algorithm could be modified to become more general and therefore be applicable in different situations. For example, instead of writing the algorithm to accept only one parameter, we could have written it to accept 3 parameters. One for the counter, another for the ceiling and a third for the increment as shown in the following algorithm:
void print_numbers (counter isoftype int, ceiling isoftype int
step isoftype int)
if (not(counter > ceiling)) then
print (counter)
print_numbers(counter + step)
endif
endprocedure
To solve a problem using recursion, we need to break the problem into 3 steps:
- Reduce the problem to a simple subtask that gets you one step closer to a solution with each step.
- Once you have decomposed the solution into subtasks, express the solution for the
subtask in the form of a recursive instruction.
- Use the recursive subtask solution to build a solution to the original problem.
EXAMPLE: Use this to write the Power function xy
- Note that xy could be broken down into xy * x(y-1) * x(y-2) * .. * x2 * x1 * x0
- Now we can make a recursive call as follows:
Power returns (x * Power(x, y-1))
- Now write the recursive function
if (terminating condition) then
take final step
else
take one step closer, make recursive call
endif
To now define the function:
function Power returnsan int (base, exp isoftype int)
if ( exp = 0) then
Power returns 1
else
Power returns (base * (Power(base , exp – 1)))
endif
endfunction
Stack: A container that is used to hold things (objects, variables, values, etc).
A stack supports two basic operations – push and pop.
To put something into a stack, you must use the push operation. To take something out of a stack, you must use the pop operation.
Very important: You can only put something into a stack at the top of the stack and you can only pop something from the top of the stack. Known as LIFO.
Also when doing recursion, a stack is always used. The function will evaluate until the stop condition is reached pushing each stage into the stack. After the stop condition is reached, the stages that were pushed into the stack will now be popped and evaluated one after the other with the value from the first supplied to the second, etc. until the stack is empty. To see this the following example will demonstrate.
Tracing the execution of the Power function using a stack: Supposing that the Power function is called in the main algorithm with 2 and 3 supplied respectively as the input parameters – looks like this:
A <- Power(2,3)
So we have a stack that the program was using and now we place this call into the stack.
A <- Power (2,3)Now we will execute the Power function so the stack will now look like:
1st call: Power base = 2 exp = 3A <- Power (2,3)
Upon evaluating, we note that exp > 0, therefore we will get a recursive call and thus another push onto the stack which will now look like this:
2nd call: Power base = 2, exp = 21st call : Power base = 2, exp = 3 Power returns 2 * Power (2,2)
A <- Power (2,3)
And again exp > 0, thus another push onto the stack giving the following:
3rd call: Power base = 2, exp = 12nd call: Power base = 2, exp = 2 Power returns 2 * Power(2,1)
1st call : Power base = 2, exp = 3 Power returns 2 * Power(2,2)
A <- Power (2,3)
And finally, when exp = 0, we still push onto stack giving the following:
4th call: Power base = 2, exp = 03rd call: Power base = 2, exp = 1 Power returns 2 * Power(2,0)
2nd call: Power base = 2, exp = 2 Power returns 2 * Power(2,1)
1st call : Power base = 2, exp = 3 Power returns 2 * Power(2,2)
A <- Power (2,3)
Now that the exp = 0, we will be finished – i.e. there are no more recursive step. We will now go through the stack popping from the top and evaluate the expression passing the result to the next item we pop from the stack. This will continue until we reach to the last of the recursive call, which will produce the answer. The execution is now passed back to the main algorithm from where the function was call. The result is passed into the variable A(in this case).
Note: Recursion was not used widely mainly because it takes up a lot of memory. You will always use a stack when using recursion – to store the calls, then popping and solving. But now, memory is cheap, so recursion is used more widely. In fact, by writing a recursive algorithm, the code is more compact and shorter than if you were to use iteration.
1