How the recursive calls are maintained in a computer system? Explain with suitable examples.
Answers
Answer:
Explanation:
A recursive function (DEF) is a function which either calls itself or is in a potential cycle of function calls. As the definition specifies, there are two types of recursive functions. Consider a function which calls itself: we call this type of recursion immediate recursion.
One can view this mathematically in a directed call graph.
A ---|
^ |
| |
|----|
void A() {
A();
return;
}
A() is a recursive function since it directly calls itself.
The second part of the defintion refers to a cycle (or potential cycle if we use conditional statements) which involves other functions.
Consider the following directed call graph
A ---------> B
^ |
| |
| |
|---- C <----|
This can be viewed in the following three functions:
void C() {
A();
return;
}
void B() {
C();
return;
}
void A() {
B();
return;
}
Recursive functions are an inefficient means of solving problems in terms of run times but are interesting to study nonetheless. For our purposes we will only consider immediate recursion since this will cause enough difficulty.
Writing Recursive Functions
A recursive function has the following general form (it is simply a specification of the general function we have seen many times):
ReturnType Function( Pass appropriate arguments ) {
if a simple case, return the simple value // base case / stopping condition
else call function with simpler version of problem
}
For a recursive function to stop calling itself we require some type of stopping condition. If it is not the base case, then we simplify our computation using the general formula.
Example: n!
Compute n! Recursively.
We are given the mathematical function for computing the factorial:
n! = n * (n - 1)!
Why this is a recursive function? To compute n! we are required to compute (n - 1)!.
We are also given the simple case. We define mathematically 0!
0! = 1
To undersatnd factorial in a recursive sense, consider a few simple cases:
1! = 1 * 0! = 1 * 1 = 1
2! = 2 * 1! = 2 * 1 = 2
3! = 3 * 2! = 3 * 2 = 6
4! = 4 * (3 * 2 * 1) = 4 * 3! = 24
Consider a more complicated instance:
12! = 12 * 11! = 12 * (11 * 10 * ... * 1) = = ?
Now let us write the C++ function which will calculate the factorial of a given integer. Apply the simple case and the general factorial function to the general recursive function established previously.
int Factorial(int n) {
if (n == 0) return 1; // Simple case: 0! = 1
return (n * Factorial(n - 1)); // General function: n! = n * (n - 1)!
}
Here, 0! = 1 is the base case and our general recursive function forms the simplification of the original problem.
Stepping Through Recursive Functions (Be stupid like a computer)
Example 1: Fibonacci Sequence
Consider the following program which contains a recursive function. What is the complete output?
#include <iostream.h>
int Fibonacci(int x) {
if (x == 0) return 0; // Stopping conditions
if (x == 1) return 1;
return Fibonacci(x - 1) + Fibonacci(x - 2);
}
int main() {
int num;
cin >> num;
cout << Fibonacci(num) << endl;
return 0;
}
Let's input the value 5 for this program.
The following recursive calls are made. Notice the (upside-down) tree structure created by the recursive calls.
Fibonacci(5)
/ \
/ \
/ \
/ \
/ \
F(4) + F(3)
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
F(3) + F(2) F(2) + F(1)
/\ /\ | \ \
/ \ / \ | \ \
/ \ / \ | \ \
/ \ / \ | \ \
F(2) + F(1) F(1) + F(0) F(1) + F(0) 1
/\ | | | | |
/ \ | | | | |
/ \ | | | | |
/ \ | | | | |
F(1) + F(0) 1 1 0 1 0
| |
| |
| |
| |
1 0
If we evaluate these recursive calls we have
(((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1) = 5
Thus, Fibonacci(5) = 5.
Input:
5
Output:
5
You may have noticed the name of the function and recognized it as a well-known mathematical function: the fibonacci sequance.
Working backward, we could have formulated the function given the mathematical equations:
General form:
Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)
Stopping conditions:
Fibonacci(0) = 1
Fibonacci(1) = 1