Review: functions
void foo(void) { cout << "In foo(), before bar()" << endl; bar(); cout << "In foo(), after bar()" << endl; }With bar() defined as follows:
void bar(void) { cout << "In bar()" << endl; }Then we would see the following output:
In foo, before bar() In bar() In foo, after bar()
Review: objects
Remember that an object must be declared before it can be used.
void foo(void) { int a; int b; a = 5; b = 7; bar(20); baz(37, 49); } void bar(int a) { int b; b = a; } void baz(int a, int b) { int c; int d; c = a + b; d = a - b; }If all of this makes sense, you will have no problem with recursion.
Recursion is what we call it when a function calls itself
Example: Computing factorials
Remember that the factorial of n, written n! is the product n * n-1 * ... * 2 * 1
The iterative version:
int factorial(int n) { int i; int fact = 1; for(i = 1; i <= n; i++) fact = fact*i; return(fact); }The recursive version:
int factorial(unsigned int n) { int fact; if(n == 0) // the anchor case fact = 1; else // the inductive case fact = n * factorial(n-1); return(fact); }It's obvious that this computes the correct value, since n! = n * (n-1)!
It's also clear that the second version is much easier to understand and more closely matches the mathematical definition of factorial.
What happens without the anchor case?
What happens with the stack if we execute factorial(3)? (Picture)
Example: computing exponentials
int power(int n, int pow) { if(pow == 1) // anchor case return(1); else // inductive case return(n * power(n, pow-1)); }
Example: printout out a binary number without leading zeroes
void print_binary(unsigned int n) { int binary_digit; if(n > 0) { binary_digit = n & 1; print_hex(n >> 1); cout << binary_digit; } return(); }
Fibonacci numbers revisited
Remember from quiz 2 that Fibonacci numbers are a sequence of numbers defined as follows: the first and second Fibonacci numbers are 1. Every other Fibonacci number is defined to be the sum of the previous two Fibonacci numbers. So, the sequence begins 1, 1, 2, 3, 5, 8, 13, 21, ...
Iterative solution:
int fibonacci(unsigned int n) { int fib; int last; int temp; switch(n) { case 0: fib = 0; break; case 1: fib = 1; break; case 2: fib = 1; break; default: // initialize fib fib = 1; last = 1; for(i = 2; i < n; i++) { temp = fib; fib += last; last = temp; } break; } return(fib); }Recursive solution:
int fibonacci(unsigned int n) { switch(n) { case 0: return(0); break; case 1: return(1); break; case 2: return(1); break; default: return( fibonacci(n-1) + fibonacci(n-2) ); break; } }
Binary Search
If we know that the list is in sorted order, then we can do binary search, which has better average and worst case behaviour than linear search.
int binary_search(int list[], int start, int end, int m) { int i; int N = end - start; int midval; // anchor case if(N == 0) { if(list[N] == m) return(N); else return(-1); } // inductive cases midval = list[N/2]; if( midval == m ) return( N/2 ); else if( midval > m) return( binary_search(list, start, N/2, m) ); else return( binary_search(list, N/2 + 1, end, m) ); }Example:
Quicksort
Quicksort is an extremely efficient sorting method that is a natural for implementation using recursion
void quicksort(int list[], int start, int end) { int mid; if(start != end) { mid = split(list, start, end); quicksort(list, start, mid-1); quicksort(list, mid+1, end); } } int split(int list[], int start, int end) { int left = start; int right = end; int pivot = list[start]; int temp; while(left < right) { // scan to the right looking for a value smaller than the pivot while(list[right] > pivot) right--; // scan to the left, looking for a value larger than the pivot while( (left < right) && (list[left] <= pivot) ) left++; if(left < right) { // swap list[left] and list[right] temp = list[left]; list[left] = list[right]; list[right] = temp; } } list[start] = list[right]; list[right] = pivot; return(right); }