Recursion

Stack and heap

A program can be run by executing a file such as:

./a.out

The operating system will allocate some area in the RAM for the program to be run. The code of the exe ( machine language instructions ) will occupy some space and 2 sections in the RAM will be reserved ; the stack and the heap.

When a program is run the CPU will fetch an instruction from the RAM and process it and then fetch another instruction from the RAM and process it . Complications arise when there is a function to be called.

Assume the following are machine language instructions loaded in the RAM .

int sum( int x1 , int x2 ) //A

return ( x1 + x2 ) //B

int main()

int result ; //C

result = sum( 4 + 6 ) ; //D

Assume the current instruction is at "C". Now we need to execute the function "sum" but the "sum" is another section of the code. Somehow we need to tell that function that once we are done we need to come back to the main function. So we store this location on the stack.

Stack

---------

//D Store this location

Now we also need to pass the values 4 and 6 to the function . So let's store those also in the stack.

Stack

---------

6

4

//D Store this location

Now we tell the CPU that the next instruction is A and we store 4 and 6 on the stack. Now the CPU starts executing the code at the location "sum" and the sum function grabs the numbers 4 and 6 and has the result 10 that it needs to give back to where the function was called in the "main" function. How does it do that ? Again it puts it on the stack:

Stack

---------

10

It uses the //D location and control is transferred to the main function where the code picks up the result 10 from the stack and and assigns it to the variable "result" . The area for storing this information for a particular function is called a stack frame. Local variables are also created and stored on the stack.

Ex:

void function1()

{

int x1 ;

int x2 ;

int x3 ;

}

Stack

---------

x3

x2

x1

The requirement is that the size of the variables must be known at compile time of the variables to be allocated on the stack.

The "heap" is used to store memory that has been created dynamically when the program is run. The size of the memory can be dynamic. There are 2 functions that can be used to do this:

"malloc" and "new"

Memory allocated in any other way will be allocated on the stack.

File: "stack1.cpp"

#include <iostream> using namespace std ; int recursiveError( int x1 ) { //int arr1[1000000] ; int arr1[100000] ; //00 cout << "x1:" << x1 << endl ; return recursiveError(x1+1) ; } int recursiveError1( int x1 ) { //int arr1[1000000] ; int arr1[100000] ; //00 cout << "x1:" << x1 << endl ; return x1 ; } int main() { recursiveError( 1 ) ; /* for( int i1=0 ; i1<1000000; i1++ ) { recursiveError1( i1 ) ; } */ }

The function:

int recursiveError( int x1 ) { //int arr1[1000000] ; int arr1[100000] ; //00 cout << "x1:" << x1 << endl ; return recursiveError(x1+1) ; }

introduces an out of memory error for the stack. When we enter it for the first time we have some memory in the first stack frame for the function that has the array variable "arr1" .. It then calls it;s own function again with "recursiveError(x1+1)" . This causes another stack frame to be created. The first stack frame cannot be released because the first invocation of this function is going to wait for the second invocation. Every time the function is called a stack frame gets created. Eventually the stack runs out of stack space.

How about the second function.

int recursiveError1( int x1 ) { //int arr1[1000000] ; int arr1[100000] ; //00 cout << "x1:" << x1 << endl ; return x1 ; }

for( int i1=0 ; i1<1000000; i1++ ) { recursiveError1( i1 ) ; }

The function recursiveError1 does not call any other function. We run a loop a million times calling this function every time. For "i1=0" the function gets invoked.

Sample Recursive Functions

File: "r1.cpp"

#include <iostream> using namespace std ; int factorialIterative( int x1 ) { int result = 1 ; for( int i1=2 ; i1<=x1 ; i1++ ) { result = result * i1 ; } return result ; } int factorialRecursive(int n) { if (n <= 1) return 1; else return ( n * factorialRecursive(n - 1) ) ; } //The Fibonacci series is : //0 1 1 2 3 5 8 13 21 //0th 1st 2 3 4 5 6 7 8 int fibonacciNumberIterative( int nth ) { if ( nth == 0 ) return 0 ; if ( nth == 1 ) return 1 ; int fib1 = 0 ; int fib2 = 1 ; for( int i1=2 ; i1 <= nth ; i1++) { int temp = fib1 + fib2 ; fib1 = fib2 ; fib2 = temp ; } return ( fib2 ) ; } int fibonacciNumberRecursive( int nth ) { if ( nth == 0 ) return 0 ; if ( nth == 1 ) return 1 ; //TO DO Write code that will return the fibonacci value of nth number return ( fibonacciNumberRecursive(nth-1) + fibonacciNumberRecursive(nth-2) ) ; } int recursiveError( int x1 ) { //int arr1[1000000] ; int arr1[100000] ; //00 cout << "x1:" << x1 << endl ; return recursiveError(x1+1) ; } int recursiveError1( int x1 ) { //int arr1[1000000] ; int arr1[100000] ; //00 cout << "x1:" << x1 << endl ; return x1 ; } void towerOfHanoi( int n1, char from_rod, char aux_rod, char dest_rod ) { if ( n1 == 1 ) { cout << "Move disk 1 from rod " << from_rod << " to rod " << dest_rod << endl ; return ; } towerOfHanoi(n1-1, from_rod, dest_rod, aux_rod); cout << "Move disk " << n1 << " from rod " << from_rod << " to rod " << dest_rod << endl ; towerOfHanoi(n1-1, aux_rod, from_rod, dest_rod ) ; } int recursive1( int x1 , int x2 ) { if ( x1 < 2 ) return 1 ; if ( x2 < 3 ) return ( 2) ; return ( recursive1( x1 - 1, x2 -1 ) + recursive1( x1 - 1, x2 ) ) ; }int recursive2( int x1, int x2 ) { if ( x1 == 1 ) return x2 ; x1 = x1-1 ; x2 = x2 * x1 ; return( recursive2( x1, x2 ) ) ; } int recursive( int x1 ) { int sum = x1-1 ; if ( x1 < 2 ) return 1 ; sum = sum + recursive( x1 - 2 ) ; return ( sum ) ; } int main() { //towerOfHanoi( 2, 'A' , 'B' , 'C' ) ; }

Case Study 1

Given an array of denominations and a sum; determine the number of ways the different coins can be selected to make the sum. You are allowed to select any number of coins .

File: "count1.cpp"

#include <iostream> using namespace std ; // Returns the count of ways we can // sum S[0...m-1] coins to get sum n int count( int array_of_coins[], int lengthOfArray, int sumDesired ) { // If n is 0 then there is 1 solution // (do not include any coin) if (sumDesired == 0) return 1; // If n is less than 0 then no // solution exists if (sumDesired < 0) return 0; // If there are no coins and n // is greater than 0, then no // solution exist if (lengthOfArray <=0 && sumDesired >= 1) return 0; // count is sum of solutions (i) // including S[m-1] (ii) excluding S[m-1] return count( array_of_coins, lengthOfArray - 1, sumDesired ) + count( array_of_coins, lengthOfArray, sumDesired - array_of_coins[lengthOfArray-1] ); } int main() { // 2 coins int arr1[] = { 1 , 2 } ; cout << count( arr1, 2 , 3 ) << endl ; }

Case Study 2

Find the combinations of the numbers in the array. The array will always contain an ascending sequential numbers starting from number 1. For n= 3 and m = 2 we get.

1 2 3

Combinations are

1 2

1 3

2 3

For n= 5 and r = 4 we get

1 2 3 4 5

1 2 3 4

1 2 3 5

2 3 4 5

1 3 4 5

File: "r2.cpp"

#include <iostream>using namespace std;void comb(int n, int r, int *arr, int sz){ for (int i = n; i >= r; i --) { // choose the first element arr[r - 1] = i; if (r > 1) { // if still needs to choose // recursive into smaller problem comb(i - 1, r - 1, arr, sz); } else { // print out one solution for (int i = 0; i < sz; i ++) { cout << arr[i] << " "; } cout << endl; } }}int main(){ const int N = 2; const int M = 1; int *arr = new int[M]; comb(N, M, arr, M); delete []arr; return 0;}

Case Study 3

Reversing a linked list.

File: "linked1.cpp"

// Recursive C++ program to reverse// a linked list#include <iostream>using namespace std;/* Link list node */class Node { public: int data; class Node* next; Node(int data) { this->data = data; next = NULL; }};class LinkedList { public: Node* head; LinkedList() { head = NULL; } /* Function to reverse the linked list */ Node* reverse(Node* node) { if (node == NULL) return NULL; if (node->next == NULL) { head = node; return node; } Node* node1 = reverse(node->next); node1->next = node; node->next = NULL; return node; } /* Function to print linked list */ void print() { Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void push(int data) { Node* temp = new Node(data); temp->next = head; head = temp; }};/* Driver program to test above function*/int main(){ /* Start with the empty list */ LinkedList ll; ll.push(20); ll.push(4); ll.push(15); ll.push(85); cout << "Given linked list\n"; ll.print(); ll.reverse ( ll.head ) ; cout << "\nReversed Linked list \n"; ll.print(); return 0;}

Case Study 4

File: "permute.cpp"

#include <iostream>using namespace std ;void permute(int *arr, int start, int end){ if (start == end)//print { for (int i1 = 0; i1 <= end; i1++) { cout << arr[i1] << " "; } cout << "\n"; } else { for (int i = start; i <= end; i++) { // swap 2 elements to create tree brances. int temp = arr[i]; arr[i] = arr[start]; arr[start] = temp; permute(arr, start + 1, end); //revert back to go back up a tree branch temp = arr[i]; arr[i] = arr[start]; arr[start] = temp; } }}//-------------------------------------------int main(){ int x1; int arr3[3] = { 1, 2, 3 }; permute(arr3, 0, 2);}//-------------------------------------------

Exercises

1)

int recursive( int x1 ) { int sum = x1-1 ; if ( x1 < 2 ) return 1 ; sum = sum + recursive( x1 - 2 ) ; return ( sum ) ; } int recursive1( int x1 , int x2 ) { if ( x1 < 2 ) return 1 ; if ( x2 < 3 ) return ( 2) ; return ( recursive1( x1 - 1, x2 -1 ) + recursive1( x1 - 1, x2 ) ) ; } int recursive2( int x1, int x2 ) { if ( x1 == 1 ) return x2 ; x1 = x1-1 ; x2 = x2 * x1 ; return( recursive2( x1, x2 ) ) ; } int recursive4( int x1 ) { if ( x1 < 2 ) return 1 ; return (recursive( x1 - 2 ) + recursive( x1 - 1 ) ) ; } int recursive5( int x1 ) { if( x1 == 1 ) return 1 ; return ( 2 * recursive5( x1-1 ) + recursive5( x1 - 1 ) ) ; } int recursive6( int x1, int x2 ) { if ( x1 == 1 ) return x2 ; x1 = x1 - 1 ; x2 = x2 + x1 ; return( recursive6( x1, x2 ) ) ; }

void main(String[] args) { // System.out.println( recursive6( 4 , 3 ) ) ; // System.out.println( recursive6( 4 , 3 ) ) ; // TODO Auto-generated method stub // System.out.println( recursive1( 4,5 ) ) ; // System.out.println( recursive1( 5,2 ) ) ; System.out.println( recursive2( 4 , 5 ) ) ; System.out.println( recursive2( 5 , 2 ) ) ; // System.out.println( recursive( 5) ) ; // System.out.println( recursive5(2 ) ) ; //System.out.println( recursive6( 3, 3 ) ) ; }