Recursion
Recursion is a solution design method that come from solutions that have the following characteristics- The modularization of the solution design reveals that the solution contains a version of itself
- The version of the solution that is contained within the solution will eventually terminate.
The traditional example of recursion is the mathematical definition of the factorial function,
n! = 1 , when n=0 or n=1
= n*(n-1)!, when n is an integer, n > 1
Simply stated, when n > 1, for example 6!, it is defined as n*(n-1)!, 6! = 6*5!. In other words, 6! is defined in terms of the factorial function calculated at 5!, which satisfies rule 1 stated above. But 5! also satisfies rule 2 in that we can see that by reapplying the definition to 5! we have 5*4!, and 4! = 4*3!, and three factorial is 3*2!, 2! = 2*1!, and finally, by the definition 1! = 1. Hence 6! = 6*5*4*3*2*1 = 720.
Representing the factorial function
The advantage of recursive design is that many modern programming languages support the direct implementation of the design into code that directly represents the design. For example, the definition of n! described above translates into the Ada function, function Factorial (n: natural) return natural is
begin -- Factorial
if n > 1 then
return n * Factorial(n-1);
else
return 1;
end if;
end Factorial;
Many students when they see this code they worry about how this is carried out. How does a subprogram recall itself? How does the system handle this? Eventually we will see how this is accomplished. At this point, the issue of how this is accomplished is irrelevant to us. The fact that it is accomplished is sufficient. One way of addressing you concern is to think that the system carries this out by creating a copy of the subprogram and calling the copy with the new parameters.
The Towers of Hanoi
The Towers of Hanoi is a classical recursive problem. The problem is: Given n disks and three spindles, move the stack of disks from the first spindle to the third spindle using the second spindle to help you. The rules for moving disks are:- You may move only one disk at a time.
- A disk may be moved to an empty spindle, or
- A disk may be placed on top of a larger disk
If we refer to the spindles as A, B, and C, the problem of moving n disks from spindle A to spindle B with the help of spindle C is solved with the following solution design:
- Move n-1 disks from spindle A to spindle C with the help of spindle B.
- Move the one remaining disk on A to C.
- Move n-1 disks from spindle B to spindle C with the help of spindle A. Note: This may be accomlished because all of the n-1 disks on B are smaller than the one disks on C, hence they may be placed on top of that disk.
C:\Ada95>The_Towers Move disk from A to B Move disk from A to C Move disk from B to C Move disk from A to B Move disk from C to A Move disk from C to B Move disk from A to B Move disk from A to C Move disk from B to C Move disk from B to A Move disk from C to A Move disk from B to C Move disk from A to B Move disk from A to C Move disk from B to C 22recursive calls