A popular function that is defined recursively is the factorial function:
This function assumes that N >= 1 and by definition 0! = 1. This function is recursive because it is defined in terms of itself. The traditional way of writing recursive definitions is like this:N! = N · (N - 1)!
For example, 5! is defined like this:0! = 1 base case N! = N · (N - 1)! recursive case
And 4! is defined like this:5! = 5 · 4!
And so on:4! = 4 · 3!
Which ultimately gives us:3! = 3 · 2! 2! = 2 · 1! 1! = 1 · 0! 0! = 1 this is the base case
5 · 4 · 3 · 2 · 1 · 1 = 120
Another popular function that is defined recursively is the power function:
This function assumes that N >= 2 and by definition X1 = X. We would write the recursive definition like this:XN = X · X(N - 1)
Some terminologyX1 = X base case XN = X · X(N - 1) recursive case
Recursive call - A function call in which the function begin called
is the same as the one making the call
Recursive definition - A definition in which something is defined
in terms of smaller versions of itself
Base case - The case for which the solution can be stated non-recursively
General case (recursive case) - The case for which the solution is
expressed in terms of a smaller version of itself
Recursive algorithm - A solution that is expressed in terms of
(a) a base case and (b) a recursive case
Infinite recursion - The situation in which a function calls
itself over and over endlessly
Tail recursion - A recursive algorithm in which no statements
are executed after returning from the recursive call
Factorial Examples
The factorial function can be written non-recursively in C++:
The factorial function can also be written recursively:int iterativeFact(int number) { int factor = 1; int count; for (count = 2; count <= number; count++) factor = factor * count; return factor; }
Client code would call them in the normal fashion:int recursiveFact(int number) { if (number == 0) return 1; else return number * recursiveFact(number - 1); }
Tracing Function Callscout << iterativeFact(5) << endl; cout << recursiveFact(5) << endl; Output: 120 120
Given 3 functions as defined below:
What does the following program print?int f1(int a, int b); int f2(int x); int f3(int x); int f1(int a, int b) { int x, y; x = f2(a); y = 4 + b; return x + y; } int f2(int x) { int a, b, c; a = x; b = 5; c = f3(a + b); return c; } int f3(int x) { int a; a = x * 3; // snapshot taken before this executes return a; }
This is a "snapshot" of what the runtime stack looks like just before the statement a = x + 3 is executed in f3:void main(void) { int x; float f; f = 2.7; x = f1(2, 3); cout << x << endl << f << endl; }
Tracing Function Calls - 3
Given this definition of the factorial function fact:
Trace the function calls of this program:int fact(int number) { if (number == 0) return 1; else return number * fact(number - 1); }
Given this definition of Print:void main(void) { int x; x = fact(4); cout << x << endl; }
Trace the function calls of from this statement:int Print(const int list, int first, int last) { if (first <= last) { cout << list[first] << endl; Print(list, first + 1, last); } }
Tracing Function Calls - 4Print(list, 0, 2)
This displayReverse function accepts input from the user. Assume that the user types:void displayReverse(int charCount) { char inchar; if (charCount == 1) { cin >> inchar; cout << inchar; } else if (charCount > 1) { cin >> inchar; displayReverse(charCount - 1); cout << inchar; } }
after the program is started. The output from the program isABC
This is what a trace of the program looks like:CBA