Recursion occurs when a procedure calls itself. The following, for example, is a recursive procedure:
procedure Recursive;
begin Recursive;
Recursive();
end Recursive;Of course, the CPU will never return from this procedure. Upon entry into Recursive, this procedure will immediately call itself again, and control will never pass to the end of the procedure. In this particular case, runaway recursion results in an infinite loop.[78]
Like a looping structure, recursion requires a termination condition in order to stop infinite recursion. Recursive could be rewritten with a termination condition as follows:
procedure Recursive;
begin Recursive;
dec( eax );
if( @nz ) then
Recursive();
endif;
end Recursive;This modification to the routine causes Recursive to call itself the number of times appearing in the EAX register. On each call, Recursive decrements the EAX register by 1 and then calls itself again. Eventually, Recursive decrements EAX to 0 and returns from each call until it returns to the original caller.
So far, however, there hasn't been a real need for recursion. After all, you could efficiently code this procedure as follows:
procedure Recursive;
begin Recursive;
repeat
dec( eax );
until( @z );
end Recursive;Both examples would repeat the body of the procedure the number of times passed in the EAX register.[79] As it turns out, there are only a few recursive algorithms that you cannot implement in an iterative fashion. However, many recursively implemented algorithms are more efficient than their iterative counterparts, and most of the time the recursive form of the algorithm is much easier to understand.
The quicksort algorithm is probably the most famous algorithm that usually appears in recursive form. An HLA implementation of this algorithm appears in Example 5-9.
Example 5-9. Recursive quicksort program
program QSDemo;
#include( "stdlib.hhf" );
type
ArrayType: uns32[ 10 ];
static
theArray: ArrayType := [1,10,2,9,3,8,4,7,5,6];
procedure quicksort( var a:ArrayType; Low:int32; High:int32 );
const
i: text := "(type int32 edi)";
j: text := "(type int32 esi)";
Middle: text := "(type uns32 edx)";
ary: text := "[ebx]";
begin quicksort;
push( eax );
push( ebx );
push( ecx );
push( edx );
push( esi );
push( edi );
mov( a, ebx ); // Load BASE address of "a" into ebx.
mov( Low, edi); // i := Low;
mov( High, esi ); // j := High;
// Compute a pivotal element by selecting the
// physical middle element of the array.
mov( i, eax );
add( j, eax );
shr( 1, eax );
mov( ary[eax*4], Middle ); // Put middle value in edx.
// Repeat until the edi and esi indexes cross one
// another (edi works from the start towards the end
// of the array, esi works from the end towards the
// start of the array).
repeat
// Scan from the start of the array forward
// looking for the first element greater or equal
// to the middle element).
while( Middle > ary[i*4] ) do
inc( i );
endwhile;
// Scan from the end of the array backwards looking
// for the first element that is less than or equal
// to the middle element.
while( Middle < ary[j*4] ) do
dec( j );
endwhile;
// If we've stopped before the two pointers have
// passed over one another, then we've got two
// elements that are out of order with respect
// to the middle element, so swap these two elements.
if( i <= j ) then
mov( ary[i*4], eax );
mov( ary[j*4], ecx );
mov( eax, ary[j*4] );
mov( ecx, ary[i*4] );
inc( i );
dec( j );
endif;
until( i > j );
// We have just placed all elements in the array in
// their correct positions with respect to the middle
// element of the array. So all elements at indexes
// greater than the middle element are also numerically
// greater than this element. Likewise, elements at
// indexes less than the middle (pivotal) element are
// now less than that element. Unfortunately, the
// two halves of the array on either side of the pivotal
// element are not yet sorted. Call quicksort recursively
// to sort these two halves if they have more than one
// element in them (if they have zero or one elements, then
// they are already sorted).
if( Low < j ) then
quicksort( a, Low, j );
endif;
if( i < High ) then
quicksort( a, i, High );
endif;
pop( edi );
pop( esi );
pop( edx );
pop( ecx );
pop( ebx );
pop( eax );
end quicksort;
begin QSDemo;
stdout.put( "Data before sorting: " nl );
for( mov( 0, ebx ); ebx < 10; inc( ebx )) do
stdout.put( theArray[ebx*4]:5 );
endfor;
stdout.newln();
quicksort( theArray, 0, 9 );
stdout.put( "Data after sorting: " nl );
for( mov( 0, ebx ); ebx < 10; inc( ebx )) do
stdout.put( theArray[ebx*4]:5 );
endfor;
stdout.newln();
end QSDemo;Note that this quicksort procedure uses registers for all nonparameter local variables. Also note how quicksort uses text constant definitions to provide more readable names for the registers. This technique can often make an algorithm easier to read; however, one must take care when using this trick not to forget that those registers are being used.