Recursion

Introduction

A recursive function is one that can call itself. Most modern languages support this technique. Many problems in computer science can be solved elegantly using recursion. Many graph , sorting problems can be solved by recursive algorithms.

Usually this is when a problem can be broken down into smaller problems that are similar to the original problem. However recursion can place a large burden on resources like the stack than non-recursive ( iterative ) approaches. Even though a recursive approach may express and solve a problem in an elegant manner; the analysis of a recursive algorithm may be prove to be very complex and not that intuitive. Tracing through a recursive algorithm ( line by line ) is not very intuitive and involves keeping track of more things . The recursion technique takes some time to learn and become familiar with.

Recall that when a program is run it is given a block in RAM to run under. Stack is part of the memory that is allocated for functions and can store things like address of where the function should give control once it is done and store the argument parameters and local variables.

A function can call another function and that function could call another function and so on. With a recursive function the function can call itself. Internally the process is similar to calling another function in the sense the arguments will obtain new values and the local variables will have a new stack frame. Below is a simple example.

Ex:

//------------------------------------------------------------------------------------------------------

#include <iostream>

using namespace std ;

void recursiveFunction()

{

cout << "Inside the recursive function." << endl ;

recursiveFunction() ;

}

int main()

{

recursiveFunction() ;

}

//------------------------------------------------------------------------------------------------------

Output:

Inside the recursive function.

Inside the recursive function.

Inside the recursive function.

Inside the recursive function.

Inside the recursive function.

Segmentation fault (core dumped)

//------------------------------------------------------------------------------------------------------

The function calls itself . The first time we enter the recrusiveFunction: lets say entry1 and then we call it again but the first function has not ended . Now the function is called again and let's say that is entry 2 and it will call the function again. So we keep having the stack frame allocated every time we call the function and eventually we will run out of the stack space that has been allocated for us. We can speed up the usage of the stack by defining a local variable that takes some space.

Ex:

//------------------------------------------------------------------------------------------------------

#include <iostream>

using namespace std ;

void recursiveFunction()

{

int array1[1000000] ;

cout << "Inside the recursive function." << endl ;

recursiveFunction() ;

}

int main()

{

recursiveFunction() ;

}

//------------------------------------------------------------------------------------------------------

Output:

[amittal@hills inter]$ ./a.out

Inside the recursive function.

Inside the recursive function.

Segmentation fault (core dumped)

//------------------------------------------------------------------------------------------------------

It is essential that a recursive function have a condition that stops this infinite calling of functions.

Ex:

//------------------------------------------------------------------------------------------------------

#include <iostream>

using namespace std ;

void recursiveFunction(int noOfTimesToRun)

{

if ( noOfTimesToRun == 0 )

return ;

cout << "Inside the recursive function." << endl ;

noOfTimesToRun-- ;

recursiveFunction(noOfTimesToRun) ;

}

int main()

{

recursiveFunction(5) ;

}

//------------------------------------------------------------------------------------------------------

Output:

Inside the recursive function.

Inside the recursive function.

Inside the recursive function.

Inside the recursive function.

Inside the recursive function.

//------------------------------------------------------------------------------------------------------

Let's examine some simple problems that we can solve using recursion. Many of these problems have simple iterative solutions whereas for others the iterative solutions are not that obvious.

Examples

Factorial

A factorial of a number n is defined as a product of all numbers less than or equal to n. So factorial of 4 is

4*3*2*1 = 24

We also think of the solution as the number 4 multiplied by the factorial of 3 . Also factorial of 0 is 1 and factorial of 1 is 1 .

Ex:

//------------------------------------------------------------------------------------------------------

#include <iostream>

using namespace std ;

int factorial(int number)

{

int result ;

if ( number == 0 || number == 1 )

return 1 ;

result = number * factorial ( number - 1 ) ;

return result ;

}

int main()

{

cout << factorial( 4) << endl ;

}

Output:

[amittal@hills inter]$ ./a.out

24

//------------------------------------------------------------------------------------------------------

Iterative Solution to the factorial problem.

//------------------------------------------------------------------------------------------------------

#include <iostream>

using namespace std ;

int factorial(int number)

{

int result = 1 ;

if( number == 0 )

return 1 ;

for( int i1=1 ; i1<=number ; i1++ )

result = result*i1 ;

return result ;

}

int main()

{

cout << factorial( 4) << endl ;

}

//------------------------------------------------------------------------------------------------------

Output:

[amittal@hills inter]$ ./a.out

24

//------------------------------------------------------------------------------------------------------

Fibonacci Sequence

//------------------------------------------------------------------------------------------------------

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std ;

int fibonacci( int nth )

{

if( nth <=0 )

return -1 ; //error condition

if ( nth == 1 || nth == 2 )

return 1 ;

return fibonacci( nth-1) + fibonacci( nth-2) ;

}

int main()

{

cout << fibonacci(4) << endl ;

}

//------------------------------------------------------------------------------------------------------

Reverse an array

Ex:

//------------------------------------------------------------------------------------------------------

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std ;

void reverse(char* ptr , int leftIndex, int rightIndex )

{

char tempChar ;

if ( rightIndex <= leftIndex )

return ;

tempChar = *(ptr+leftIndex ) ;

*(ptr+leftIndex) = *(ptr+rightIndex) ;

*(ptr+rightIndex) = tempChar ;

leftIndex++ ; rightIndex-- ;

reverse( ptr, leftIndex, rightIndex ) ;

}

int main()

{

//char ptr[] = "some" ;

char ptr[] = "table" ;

//char ptr[] = "A string to be reversed." ;

reverse( ptr, 0, strlen(ptr) -1 ) ;

cout << ptr << endl ;

}

//------------------------------------------------------------------------------------------------------

Find Prime Factors

The problem is to find out all the prime factors ( print the ones that occur more than once also).

Ex:

//------------------------------------------------------------------------------------------------------

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std ;

void printPrimeFactors(int num)

{

static int divisor = 2; // 2 is the first prime number

if ( num == 1 ) //if num = 1 we finished

{

divisor = 2; //restore divisor, so it'll be ready for the next run

return;

}

else if ( num % divisor == 0 ) //if num divided by divisor

{

cout << divisor << " "; //print divisor

printPrimeFactors( num / divisor ); //call the function with num/divisor

}

else //if num not divided by divisor

{

divisor++; //increase divisor

printPrimeFactors( num );

}

}

void printPrimeFactorsIter(int num)

{

int divisor = 2; // 2 is the first prime number

while ( num > 1 )

{

if ( num % divisor == 0 )

{

cout << divisor << " "; //print divisor

num = num / divisor ;

}

else

divisor++ ;

} //while

}

int main()

{

//printPrimeFactors(12) ;

printPrimeFactorsIter(12) ;

cout << endl ;

}

//------------------------------------------------------------------------------------------------------

Hanoi Towers

There are 3 poles and disks of varying sizes. Initially the disks are stacked on 1 pole ( we can call it the source ). The problem is to transfer all the disks to another pole ( call it the destination ) so that the destination contains the stack of disks. However when transferring the disks the larger disk cannot be placed on top of a smaller disk.

If we play around with this problem we can break the problem down. If we have n disks first move the top n-1 disks to the spare pole and then move the nth ( largest disk) to the destination and then move the n-1 disks from the spare pole to the destination. We can do this easily for 2 disks and the below diagram shows how this is done for 3 disks.

The pseudocode looks something like:

MoveTower(disk, source, dest, spare):

IF disk == 1, THEN: move disk from source to dest

ELSE:

MoveTower(disk - 1, source, spare, dest) // Step 1 above

move disk from source to dest // Step 2 above

MoveTower(disk - 1, spare, dest, source) // Step 3 above

END IF

The iterative solution pseudocode looks like below:

. Calculate the total number of moves required i.e. "pow(2, n)

- 1" here n is number of disks.

2. If number of disks (i.e. n) is even then interchange destination

pole and auxiliary pole.

3. for i = 1 to total number of moves:

if i%3 == 1:

legal movement of top disk between source pole and

destination pole

if i%3 == 2:

legal movement top disk between source pole and

auxiliary pole

if i%3 == 0:

legal movement top disk between auxiliary pole

and destination pole

We move the number of steps as 2 to the power n - 1 . The iterative solution is not very intuitive at all and is kind of hard to figure out as to how it solves the problem.

Case Study ( Sort a large file using merge sort )

Regular merge sort

Source code:

//------------------------------------------------------------------------------------------------------

#include<stdlib.h>

#include<stdio.h>

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = l; // Initial index of merged subarray

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of L[], if there

are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of R[], if there

are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* l is for left index and r is right index of the

sub-array of arr to be sorted */

void mergeSort(int arr[], int l, int r)

{

if (l < r)

{

// Same as (l+r)/2, but avoids overflow for

// large l and h

int m = l+(r-l)/2;

// Sort first and second halves

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

void printArray(int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", A[i]);

printf("\n");

}

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);

return 0;

}

//------------------------------------------------------------------------------------------------------