Objectives
Important Definitions
|
There are 2 different kinds of people in the world... those who do not use
recursion and those who believe that:
| ||||||||
void countdown( int n ) {
if( n == 0 ) { // This is the situation when recursion stops.
cout << "Blastoff!" << endl;
}
else { // call the function recursively with n-1
cout << n << endl;
countdown (n-1);
}
}
|
countdown(...) and it takes a single
integer as an argument.
If the parameter value is zero, it outputs the word "Blastoff."
Otherwise, it outputs the value in the parameter and then calls
countdown (itself) with the value of one minus the original
parameter as the argument (indicated in red).
Suppose we called the function like this:
void main () {
countdown (3);
}
|
n=3 and because it is not zero, the function outputs the
value 3 to the console and then calls itself with the value
n-1 = 2
n=2 and because it is not zero, the function outputs the
value 2 to the console and then calls itself with the value
n-1 = 1
n=1 and because it is not zero, the function outputs the
value 1 to the console and then calls itself with the value
n-1 = 0
n=0 and because it is zero, the function outputs
the string "Blastoff" and returns (ends).
n=1 ends and returns.
n=2 ends and returns.
n=3 ends and returns.
main() function now ends.
Therefore, the total output looks like:
3 2 1 Blastoff! |
| Warning: | Not having a base case or a poorly designed one can result in an infinite recursion, which is VERY BAD! |
|---|
main() function when it starts, and space
is made on the stack for this function; at this point, it is the only thing
on the stack:
|
This space is used to store the temporary variables that main()
needs, a space to store the return value when it finishes and other information.
Each time a function is called, the memory area for that funtion is placed
on the top of the stack, and then taken off again when the execution of the
call is completed.
Therefore, when main() calls countdown(3), a new
memory area is created to for this function on top of the stack.
countdown calls itself three times until the base case is
reached when n=0, at which point the stack has five function calls
stored in it.
|
countdown(3)
|
countdown(2)
|
countdown(1)
|
countdown(0)
|
As the functions end, they are at the top and are "popped" off the stack. A stack is an example of a "last in/first out" structure (as opposed to, for example, a queue, which is a "first in/first out" structure).
By repeatedly using the definition of factorial, we can work out that
We can code this recursive Factorial function in C++ as follows:
int Factorial(int n) {
if (n == 0) // base case
return 1;
else // recursive call
return n*Factorial(n-1);
}
|
print_backwards() that (1) inputs a series of characters
from the keyboard until it encounters a period, and then (2) prints them
backwards on the screen.
The one on the right, print_forwards(), inputs characters from the
input stream and outputs each one until the user types in a period.
#include<iostream>
using namespace std;
void print_backwards(); // function prototype
int main() {
print_backwards();
cout << "\n";
return 0;
}
void print_backwards() {
char character;
cout << "Enter a character ('.' to end program): ";
cin >> character;
if (character != '.') {
// output the character after the recursive call returns.
print_backwards();
cout << character;
}
}
|
#include<iostream>
using namespace std;
void print_forwards(); // function prototype
int main() {
print_backwards();
cout << "\n";
return 0;
}
void print_forwards() {
char character;
cout << "Enter a character ('.' to end program): ";
cin >> character;
if (character != '.') {
// output the character, and then do recursive call
cout << character;
print_forwards();
}
}
|
cout
statement relative to the recursive call.
The function print_backwards() waits until the recursive call
returns before outputing the character input from the keyboard, while
print_forward() outputs the character first.
A typical run of print_backwards() might look like:
Enter a character ('.' to end program): H
Enter a character ('.' to end program): i
Enter a character ('.' to end program): .
iH
|
Factorial(...) function can look like:
// Iterative version of the Factorial function
//precondition: n is positive
int Factorial(int n) {
int product = 1;
if (n == 0) { // do nothing because product is already the factorial
}
else { // calculate the factorial
for (int i=n ; i > 0 ; i--)
product *= i;
}
return product;
}
|
print_forwards() function is relatively simple:
void print_forwards() {
char chars;
do {
cout << "Enter a character ('.' to end program): ";
cin >> chars;
if( chars != '.' )
cout << chars;
}
while( chars != '.' ) ;
}
|
print_backwards() function is more involved because
we need more data structures to hold temporary data... In this case, we use
an array:
void print_backwards() {
char chars[MAX_ARRAY_LENGTH];
int no_of_chars_input = 0;
// Note that unlike print_forwards(), we cannot ask the user for infinite
// number of characters.
do {
cout << "Enter a character ('.' to end program): ";
cin >> chars[no_of_chars_input];
no_of_chars_input++;
}
while( chars[no_of_chars_input - 1] != '.'
&& no_of_chars_input < MAX_ARRAY_LENGTH);
for (int count = no_of_chars_input - 2 ; count >=0 ; count--)
cout << chars[count];
}
|
print_backwards() example above, and the integer variable
product in the Factorial(...) function.
Temporary memory allocation is made explicit in the iterative versions of the
functions by declaring variables, whereas it is implicit in the recursive
definitions (the variable n has a different value depending on which
recursive call of countdown(...) it is local to).
This extra stack manipulation comes at a price, and recursive versions of functions sometimes run slower and definately use more memory than their iterative counterparts. However, a function using recursion can sometimes be easier to understand and run faster than the iterative version.
Why have different sorting algorithms? It turns out that some algorithms perform much faster than others as the number of elements in an array one needs to sort increases. There is little difference in how long each of the sorting algorithms takes to sort an array of small size (such as a single element). However, this is not true as the number of elements in an array increases. Both insertion and selection sort algorithms are substantially slower than quick sort as the number of elements increases. We will cover in CSC 320 this topic of comparing the relative speeds of one algorithm versus another.
Suppose we start with the following array of 10 integers
(int a[10]):
14 3 2 11 9
8 1 12 10 7
a[0]
a[9]
The idea of quick sort is to separate the array into two parts by using an element in the array called a pivot. The left portion contains only values less than or equal to the pivot, and the other will contain only values greater than or equal to the pivot. Suppose we pick the pivot element 9. The resulting parts are:
7 3 2 1 8
9 11 12 10 14
We can then reapply exactly the same process to the left-hand and right-hand parts separately. This re-application of the same quick sort procedure leads to a recursive definition.
We create this arrangement as follows:
P = (first + last)/2
|
P = (0+9)/2 = 4.
14 3 2 11 9
8 1 12 10 7
|
P
|
lft
rht
Move the rht index to the left until the element it indexes is less than or equal to the value of the pivot; the opposite applies the lft. This is already true.
a[lft]>a[rht] swap the two values, which produces:
7 3 2 11 9
8 1 12 10 14
|
P
|
lft
rht
7 3 2 11 9
8 1 12 10 14
|
P
|
lft
rht
a[lft]>a[rht] swap the two values, which produces:
7 3 2 1 9
8 11 12 10 14
|
P
|
lft
rht
7 3 2 1 9
8 11 12 10 14
|
|
lft
rht
7 3 2 1 8
9 11 12 10 14
|
|
lft
rht
lft >= rht is true, this part of the process stops.
Here is the quick sort procedure encoded as a C++ function:
//precondition: left < right.
void quick_sort(int list[], int left, int right) {
int pivot, lft, rht;
lft = left;
rht = right;
pivot = (left + right)/2; // integer division
do {
while( list[rht] > list[pivot] )
rht--;
while( list[lft] < list[pivot] )
lft++;
if( lft <= rht ) {
swap( list[lft], list[rht] );
lft++;
rht--;
}
}
while( rht >= lft );
if( left < rht )
quick_sort(list, left, rht);
if( lft < right )
quick_sort(list, lft, right);
}
|
An interesting original problem that Fibonacci investigated in the year
1202 was about how quickly rabbits could breed in ideal circumstances.
Suppose we start with a newly-born pair of rabbits, one male and one
female that are put in a field.
There are several assumptions we make about these rabbits:
|
|
How many pairs will there be in one year?
The number of pairs of rabbits in the field at the start of each month is 1, 1, 2, 3, 5, 8, 13, 21, 34, ... |
|
// Course: CSC 306 Introduction to Programming with C++
// Name: Your Name
// Assignment #17: <Put a brief sentence about your program here.>
/*
Purpose: <Put a more in-depth description of the program here.>
*/