5.9 Recursion

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.^[9]

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 one and calls itself again. Eventually, Recursive decrements EAX to zero and returns. Once this happens, each successive call returns back to Recursive until control returns to the original call to Recursive.

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.^[10] 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 (see a textbook on data structures and algorithms for a discussion of this algorithm). An HLA implementation of this algorithm appears in Listing 5-9.

Listing 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 indicies cross one      // another (EDI works from the start toward the end      // of the array, ESI works from the end toward 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 backward 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 indicies           // greater than the middle element are also numerically           // greater than this element. Likewise, elements at           // indicies 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 non-parameter 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.

^[9]Well, not really infinite. The stack will overflow and Windows or Linux will raise an exception at that point.

^[10]Although the latter version will do it considerably faster because it doesn't have the overhead of the CALL/RET instructions.