<http://lib.cnfolio.com/ENG421RecursiveAlgorithms>
Introduction to Algorithms and Programming

Recursive algorithms



Recursion


Recursion is an algorithm whose definition uses smaller instances of itself. There are theoretical and practical advantages for using recursive algorithms:


Star fractal using recursion



Fern using recursion





Recursion is used in many common electronic products



Products that use recursion





How are recursive algorithms used in the electronic products displayed above?





Recursive functions


A recursive function has the following general format:

void recursiveFunction()
{
  if ( not terminating condition )
    general step;
  else
    final step;
}


#include <stdio.h>

void diagonal( int );

int main( void )
{
  diagonal( 5 );
}

void diagonal( int n )
{
  int i;

  if ( n > 1 )
  {
    diagonal( n - 1 );

    for (i = 1; i < n; i++)
      printf( " " );

    printf( "X\n" );
  }
  else
  {
    printf( "X\n" );
  }
}






Each recursive step creates a new copy of the recursive function



Recursion steps down





Recursion ends when all copies of the recursive functions ends



Recursion steps up


#include <stdio.h>

void diagonal( int );

int main( void )
{
  diagonal( 5 );
}

void diagonal( int n )
{
  int i;

  if ( n > 0 )
  {
    for (i = 1; i < n; i++)
      printf( " " );

    printf( "X\n" );

    diagonal( n - 1 );
  }
}






The general recursive step could also have a pre-rececursion and post-recursion step


void recursiveFunction()
{
  if ( not terminating condition )
  {
    pre-recursion step;
    recursive step;
    post-recursion step;
  }
  else
    final step;
}


Recursion steps


#include <stdio.h>

void diagonal( int );

int main( void )
{
  diagonal( 5 );
}

void diagonal( int n )
{
  int i;

  if ( n > 0 )
  {
    for (i = 1; i < n; i++)
      printf( " " );

    printf( "X\n" );

    diagonal( n - 1 );

    for (i = 1; i < n; i++)
      printf( " " );

    printf( "X\n" );
  }
}






Steps to to use recursive functions


  1. Define the base cases which do not require recursion.
  2. Define the terminating condition
    • Better for index to decrease and end at zero
    • Be careful of complex terminating conditions
    • Test condition must always occur before the recursive step in order to prevent an endless loop
  3. Define the final step
    • Final step is optional
    • Depends on the problem definition and scope
  4. Define the general step





Identify each part of the recursive function displayed below.

  1. #include <stdio.h>
  2.  
  3. void diagonal( int );
  4.  
  5. int main( void )
  6. {
  7.   diagonal( 5 );
  8. }
  9.  
  10. void diagonal( int n )
  11. {
  12.   int i;
  13.  
  14.   if ( n > 1 )
  15.   {
  16.     for (i = 1; i < n; i++)
  17.       printf( " " );
  18.  
  19.     printf( "X\n" );
  20.  
  21.     diagonal( n - 1 );
  22.  
  23.     for (i = 1; i < n; i++)
  24.       printf( " " );
  25.  
  26.     printf( "X\n" );
  27.   }
  28.  
  29.   if ( n == 1 )
  30.     printf( "X\n" );
  31. }





Recursive calculation of exponential power


(base b)(power n)

Examples:
23 = 8
26 = 64
53 = 125

Sample implementation
#include <stdio.h>

int exponentialPower( int, int );

int main( void )
{
   printf( "= %d", exponentialPower( 2, 4 ) );
}

int exponentialPower( int base, int exponent )
{
   printf( "%d, %d\n", base, exponent );

   if ( exponent > 0 )
   {
      return base * exponentialPower( base, exponent - 1 );
   }
   else return 1;
}





Recursive calculation of modulo operation


dividend % divisor

Examples:
6 % 4 = 2
15 % 6 = 3
21 % 5 = 1

Sample implementation
#include <stdio.h>

#define DIVISION_BY_ZERO_ERROR          -1
#define UNDEFINED_NEGATIVE_INPUT_ERROR  -2

int findRemainder( int, int );

int main( void )
{
   printf( "= %d", findRemainder( 15, 6 ) );
}

int findRemainder( int dividend, int divisor )
{
   if ( divisor == 0 )
      return DIVISION_BY_ZERO_ERROR;

   if ( dividend < 0 || divisor < 0 )
      return UNDEFINED_NEGATIVE_INPUT_ERROR;

   printf( "%d, %d\n", dividend, divisor );

   if ( dividend >= divisor )
   {
      return findRemainder( dividend - divisor, divisor );
   }
   else return dividend;
}





Recursive evaluation of word palindromes


A palindrome is a word which looks the same when it is spelled backwards.

Examples:
civic
kayak
radar

Sample implementation
#include <stdio.h>
#include <string.h>

#define IS_A_PALINDROME 1

int isPalindrome( char[], int );

int main( void )
{
   char inputString[] = "civic";
   printf( "= %d", isPalindrome( inputString, strlen(inputString) ) );
}

int isPalindrome( char targetString[], int targetStrLength )
{
   char firstCharacter, lastCharacter;
   
   if ( targetStrLength > 1 )
   {
      firstCharacter = targetString[ 0 ];
      lastCharacter = targetString[ targetStrLength - 1 ];
     
      return ( (firstCharacter == lastCharacter ) &&
               isPalindrome( &(targetString[1]), targetStrLength - 2 ) );
   }
   else return IS_A_PALINDROME;
}





Binary search using recursion


Given a list of data that has been sorted, a binary search is performed by repeatedly dividing the list and inspecting the middle value until the search is successful or the data cannot be divided any further.

Sample implementation
#include <stdio.h>

#define MAX_NUMBER_OF_INPUTS  20
#define MATCH_NOT_FOUND       -1

int search( int[], int, int, int );

int main( void )
{
   int inputNumbers[ MAX_NUMBER_OF_INPUTS ] = { MATCH_NOT_FOUND };
   int targetValue, searchResultPosition, numberOfInputs = 0;

   scanf( "%d", &targetValue );
   printf( "\nTarget value is %d\nInput list is [ ", targetValue );

   while ( scanf( "%d", &(inputNumbers[ numberOfInputs ]) ) == 1 )
   {
      printf( "%d ", inputNumbers[ numberOfInputs ] );
      if ( ++numberOfInputs == MAX_NUMBER_OF_INPUTS )
         break;
   }
   printf( "]\n\n" );

   searchResultPosition = search( inputNumbers,targetValue,0,numberOfInputs );
   if ( searchResultPosition != MATCH_NOT_FOUND )
      printf( "Found at position %d", searchResultPosition + 1 );
      /* adjust output display for array index starting at zero */
   else
      printf( "Match not found" );
}

int search( int numbersList[], int targetNumber, int lowIndex, int highIndex )
{
   int midPointIndex = (lowIndex + highIndex) / 2;
   printf( "Using midpoint %d\n", numbersList[ midPointIndex ] );
 
   if ( targetNumber == numbersList[ midPointIndex ] )
      return midPointIndex; /* successful search */
   else
   {
      if ( lowIndex <= highIndex )
      {
         if ( targetNumber < numbersList[ midPointIndex ] )
            return search(numbersList,targetNumber,lowIndex,midPointIndex-1);
         else
            return search(numbersList,targetNumber,midPointIndex+1,highIndex);
      }
      else return MATCH_NOT_FOUND;
   }
}





Quicksort using recursion


The quicksort algorithm works by partitioning an array into two parts, then recursively sort each part. To partition the array, one element is selected to be the partitioning item. Once an item has been selected as the partitioning item:

Sample implementation
#include <stdio.h>

#define DEBUG_ON 1
#define NUMERIC_ARRAY_LENGTH(x) sizeof(x) / sizeof(x[0])

void quickSort( int[], int );

int main( void )
{
   int numbersList[] = { 20, 12, 23, 21, 5, 9, 19, 20, 4, 20, 29, 40, 20, 31 };
   int numbersLength = NUMERIC_ARRAY_LENGTH( numbersList );
   int counter;

   quickSort( numbersList, numbersLength );

   for ( counter = 0; counter < numbersLength; counter++ )
      printf( "%d ", numbersList[ counter ] );
}

void quickSort( int list[], int listLength )
{
   int leftIndex = 0;
   int rightIndex = listLength - 1;
   int pivotIndex = listLength / 2;
   int pivotValue, tempValue, counter;

#ifdef DEBUG_ON
   printf( "==> " );
   for ( counter = 0; counter < listLength; counter++ )
      printf( "%d ", list[ counter ] );

   printf( "\n" );
#endif

   if ( listLength > 1 )
   {
      pivotValue = list[ pivotIndex ];

#ifdef DEBUG_ON
      printf( "pivot=%d\n", pivotValue );
#endif

      while ( leftIndex < rightIndex )
      {
         while ( list[ leftIndex ] < pivotValue )
            leftIndex++;

         while ( list[ rightIndex ] > pivotValue )
            rightIndex--;

         if ( leftIndex >= rightIndex )
            break;

#ifdef DEBUG_ON
         printf( "swap %d with %d\n", list[ leftIndex ], list[ rightIndex ] );
#endif

         tempValue = list[ leftIndex ];
         list[ leftIndex ] = list[ rightIndex ];
         list[ rightIndex ] = tempValue;

         leftIndex++;
         rightIndex--;

#ifdef DEBUG_ON
         for ( counter = 0; counter < listLength; counter++ )
            printf( "%d ", list[ counter ] );

         printf( "\n" );
#endif

         if ( leftIndex == rightIndex )
            rightIndex++;
      }

      quickSort( list, leftIndex );
      quickSort( &( list[leftIndex] ), listLength - leftIndex );
   }
}