0 1 (from 0 + 1) 2 (from 1 + 1) 3 (from 2 + 1) ... etc.We can test whether a number is a natural number by showing that it is possible to generate the number:
4 is a natural number because 4 = 3 + 1 and
3 is a natural number because 3 = 2 + 1 and
2 is a natural number because 2 = 1 + 1 and
1 is a natural number because 1 = 0 + 1 and
0 is a natural number by definition.
The factorial of a number n is the product of all integers from 1 to n (i.e., 1 * 2 * ... * n-1 * n ). The factorial of 0 is defined to be 1.
There is nothing mysterious about recursion. We use function calls to accomplish various things, and it is no different if what we want to accomplish happens to be handled by the function that we are writing. We just need to be sure that the recursion terminates!
int Factorial (int n) {
if (n ==0)return 1;
else return n * Factorial (n - 1);
}
void Reverse () {
char ch;
cin.get(ch);
if (ch != '\n\') {
Reverse();
cout.put(ch);
}
}
How does the compiler arrange to keep track of the value of n?
It is inefficient, and it does not support recursion. Instead, the compiler arranges to dynamically allocate the memory needed to store this information. New memory is allocated temporarily when a function is called, and released when it returns.
What data structure is appropriate for organizing this dynamically allocated memory?
The compiler arranges to store the information on a runtime stack. Each function's record on the stack is called an activation record or stack frame.
In addition to storing the information listed in the previous section (parameters, local values, and return address), each activation record also has the following.
void CountDownRecursive (int i) {
if (i >= 0) {
cout << i << ' ';
CountDownRecursive(i - 1);
}
}
The
information in the activation record for the current call is not needed when
the recursive call is made. Thus it can be written over in the recursive call,
saving memory. It is straightforward to rewrite tail recursive code as a loop. For example:
void CountDownIterative (int i) {
for ( ; i >= 0; i--)
cout << i << ' ';
}
This
leads the textbook author to say that there is no advantage of tail recursion
in C++. However ... A good compiler can translate tail recursive code into iterative code. (Many Lisp compilers do this.) With such a compiler, there is an advantage to using tail recursion for some functions. Recursive definitions are sometimes much clearer than iterative ones. However recursive calls are more expensive than iteration. With tail recursion we can have readable recursive code and an efficient iterative implementation at the same time.
void Reverse () {
char ch;
cin.get(ch);
if (ch != '\n\') {
Reverse();
cout.put(ch);
}
}
(Time permitting, we will trace the execution of this to see why it
works.) Definitions that are inherently non-tail recursive are more difficult to write iteratively. This is because one must implement an explicit stack to do the job that the runtime stack did in the recursive form. For example, using an array:
void IterativeReverse() {
char stack[80];
register int top = 0;
cin.get(stack[top]);
while(stack[top] != '\n')
cin.get(stack{++top]);
for (top -= 2; top >= 0; cout.put(stack[top--]));
}
or
using a stack ADT:
void IterativeReverse2() {
int ch;
stack.Clear();
cin.get(ch);
while (ch != '\n') {
stack.Push(ch);
cin.get(ch);
}
while (!stack.IsEmpty())
cout.put(stack.Pop());
}
In
C++ the IterativeReverse implementation is the most efficient, but is more
difficult to understand and maintain than the recursive one.
A(n,m) = m+1 if n = 0
A(n-1,m) if n > 0 and m = 0
A(n-1, A(n,m-1)) otherwise.
This
is an example of a function that is much easier to write recursively: It has
been proven that no equivalent definitions using arithmetical operators +, -,
*, /, and ^ exits. Unfortunately a straightforward recursive computation is not
even O(2^n) in time or space.
Nested recursion is a special kind of double recursion, where a recursive definition refers to itself more than once.
The Fibonacci numbers are a sequence of numbers where the nth number in the sequence is defined as follows:
Fib(n) = n if n < 2.
Fib(n-2) + Fib(n-1) otherwise.
This
definition can be written in C++ as follows:
int Fib (int n) {
if (n < 2)
return n;
else
return Fib(n-2) + Fib(n-1);
}
This definition is very inefficient. (In class we'll make this point with
figure 5.6 from the text.) A more efficient iterative definition is:
int InterativeFib (int n) {
if (n < 2)
return n;
else {
register int i = 2, tmp, current = 1, last = 0;
for ( ; i <= n; ++i) {
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
(A register declaration tells the compiler that the variables
will be heavily used, so should be allocated in registers if possible.)
Sometimes there are different ways to write recursive definitions, one being more efficient than the other. This is the point of the extra credit problem in the homework.
The solution to many problems consist of a number of interacting (mutually dependent) choices. Some example problems include:
Backtracking is this process of backing up and trying other choices. It is easily implemented with recursion because:
1. Problem 1 of page 131.
2. Problem 2 of page 131. You may write pseudocode, C++, or another language.
3. Problems 3 and 4 of page 131. (A static variable is allocated just one permanent location in memory, i.e., is not on the runtime stack. Hence the same memory location is used each call.) Use the input line "abc\n" (that's the character a, followed by b, followed by c, and a newline). In addition to the information asked for in the textbook, write a paragraph comparing the results of problems 3 and 4, and indicating the significance.
4. Problem 9 of page 133. The "binomial coefficient" gives the number of combinations of n things chosen k at a time. You may write pseudocode, C++, or another language.
About "n choose k" notation. In case you are not familiar with the notation of problem #9 page 133 (our problem 4 of HW 3): The parentheses with an "n" on top and a "k" on the bottom stands for a number -- in particular the number of different ways in which you can choose k things out of a set of n things. Your job is to write a recursive function that computes this number. n and k will be the two arguments to the function.
Example: 3 things {a, b, c}, taken 2 at a time: there are 3 ways to do it: {a, b}, {a, c}, {b, c}. (Order does not matter.)
Try drawing the recursive call tree for this computation. If your function is BC then
->BC(3,2) --->BC(2,1) ----->BC(1,0) <-----1 ----->BC(1,1) <-----1 <---2 --->BC(2,2) <---1 <-3
Extra credit: Do 18 p. 133, writing the program.