Recursive definitions help us to define large finite and infinite sets. Recursive definitions are frequently used to define functions and sequences of numbers.
Recursive definitions have two parts. The first part, the ground or base case, contains the basic elements that are the building blocks for the other elements in the defined set. The second part allows for the construction of new objects using the elements defined in the first part. A trivial example is a list of the natural numbers, which begins with 0 and adds one from there, such that any number is the previous number plus one, going all the way back to 0.
#include
using namespace std;
int main(){
int iNumber;
cout iNumber;
while(iNumber > 0){
cout << iNumber << " = ";
cout << --iNumber << " + 1" << endl;
}
cout << "Base Case: " << iNumber << endl;
return 0;
}
Recursive definitions have two purposes: creating new elements, and testing whether or not an element belongs to a set. With testing, we reduce a complex problem to a simpler problem, and if that isn’t simple enough, we reduce it to a still simpler problem, again and again as needed, until we reach the base case. Being able to decompose big problems into smaller, more manageable problems is the essence of constructing algorithms, recursive or not.
The most famous basic example of recursion is the factorial, represented as !. A factorial function defines a base case of N equaling 0, which returns the value of 1. For each value N greater than 0, the value returned is N * (N – 1) . Thus, 5! = 5 * 4 * 3 * 2 * 1.
#include
using namespace std;
int fact(int n);
int main(){
int iNum;
while(true){
cout iNum;
if(iNum < 0){
break;
} else {
cout << fact(iNum) << endl;
}
}
return 0;
}
Functions are allocated on the run-time stack in a stack frame. Each function contains its own state, including the contents of all automatic variables, the values of the function’s parameters, and by the return address indicating where to restart its caller. Stack frames typically have a short lifespan as they are allocated when the function is called and deallocated when the function exits.
Because the system creates a new stack frame whenever a function is called it can handle recursion, as each function invocation is represented internally by a different stack frame storing a different state.
A good example of a recursive function is a function that raises a number x to an integer power. The function is defined as 1, if n equals 0, and x * x ^ (n – 1) if n is greater than 0. The base case produces a value of 1, which is passed back to the previous recursive call that has been waiting for this result. This previous recursive call then calculates its own return value, which is passed onto its previous recursive call, which has been waiting for the result, and so on.
#include
using namespace std;
int exp(int iNum, int iExp){
if(iExp == 0) {
cout << "1" << endl;
return 1;
} else {
cout << iNum << " * ";
return iNum * exp(iNum, --iExp);
}
}
int main(){
int iNum, iExp;
cout << iNum;
cout << iExp;
cout << exp(iNum, iExp) << endl;
return 0;
}
A fun example of something that can be easily implemented using recursion is printing an input line in reverse order. It’s actually very simple to do in C++.
#include
using namespace std;
void reverse(){
char ch;
cin.get(ch);
if(ch != '\n'){
reverse();
cout.put(ch);
}
}
int main(){
cout << "Enter a line to have it written backwards: ";
reverse();
return 0;
}
The reverse() function up above works because each call to reverse() has its own local ch variable.
Simple C++ Tutorials 