<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:
• Theoretical
• Provides a mathematical proof of a solution
• Practical
• Fits with modular, incremental software development
• Use less computing resources for larger problems  ### Recursion is used in many common electronic products 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 ends when all copies of the recursive functions ends #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;
} #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

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), 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
}

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:
• The elements on the left side of the partitioning item are scanned from left to right until an item is found that is greater than the partitioning item.
• Similarly, the right side is scanned from right to left until an item is found that is less than the partitioning item.
• If the position of the elements have not crossed each other, then, swap the elements between the left and right side.
• Repeat until the elements have crossed each other.
• Once the elements have crossed each other, then, quicksort is recursively applied to the left side and right side.

Sample implementation
#include <stdio.h>

#define DEBUG_ON 1
#define NUMERIC_ARRAY_LENGTH(x) sizeof(x) / sizeof(x)

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 );
}
}