cstutoringcenter.com logo
E-mail:Password:

Become a premier member today to gain access to exclusive
member benefits! Just $5.00 to join FOR LIFE!






<< Tutorial 5
Tutorial 7 >>

Recursion

***Please register FREE to rate this tutorial***
Current rank: / 5 stars with 19 votes.


Examples
Basics
Tracing
Factorial Function
Examples
Example 1
Example 2
Example 3

Recursion basics

By definition, a recursive function is a function that calls itself until a certain condition is met. That condition is called the base case.

The best practice of recursion is to see a lot of examples and practice. Let’s see an example that will recursively print out the numbers from 1 to 5.

Example 1:
Recursive print

Download source code here (Right click - Save Target As...) 

#include <iostream>
using namespace std;

void Print(int n){

	if(n < 1) return;

	Print(n-1);

	cout << n << endl;

};

int main(){

	Print(5);
	return 0;
}

The print recursive function in the above program will accept an integer argument. The base case of the function will be when the argument is 0 since we want a number from 1 to 5. It will simply return to the last function call.

Then, if the base case is false, the function is called again with 1 less for the argument value. If you did not do this, the recursion would be infinite.

Finally, it will simply output that current value of the argument when the recursive calls are finished.

Recursive tracing

When recursive functions are being called, they are placed on what is called the runtime stack of a program. Just the same as a stack of dishes, the item on the top is the item that is accessed. With a program, it is the same idea that the most recent call to the stack is the currently active function call.

Here is the trace for the above printing example. It shows the call of the function and the value of n. 

Print(5)
  Print(4)
    Print(3)
      Print(2)
        Print(1)
          Print(0) <-- base case here.
        Print(1) <-- prints 1
      Print(2) <-- prints 2
    Print(3) <-- prints 3
  Print(4) <-- prints 4
Print(5) <-- prints 5

Another example is to print out a triangle of stars recursively:

Example 2:
Triangle of Stars Recursion

Download source code here (Right click - Save Target As...) 

#include <iostream>
using namespace std;

void Triangle(int x) {
   if (x <= 0) return;
   Triangle(x - 1);
   
   for (int i = 1; i <= x; i++) 
        cout << "*";
   cout << endl;
}

int main() {
   Triangle(7);
   return 0;
}

The trace of the program will be as follows: 

Triangle(7)
  Triangle(6)
    Triangle(5)
      Triangle(4)
        Triangle(3)
          Triangle(2)
            Triangle(1)
              Triangle(0) <-- base case
            Triangle(1) <-- prints 1 star & new line
          Triangle(2) <-- prints 2 stars & new line
        Triangle(3) <-- prints 3 stars & new line
      Triangle(4) <-- prints 4 stars & new line
    Triangle(5) <-- prints 5 stars & new line
  Triangle(6) <-- prints 6 stars & new line
Triangle(7) <-- prints 7 stars & new line

The output will be:

*
**
***
****
*****
******
*******

The factorial function

In math, the factorial of an integer is defined as the product of the numbers less than the given integer up to 1. So say we wish to find the factorial of 4 (written as 4!) it is written out as follows: 

4! = 4 x 3 x 2 x 1 = 24

In C++, we can write a recursive function to do the same thing. Below is a short program containing that function and a proof that it works:

Example 3:
Factorial recursion

Download source code here (Right click - Save Target As...) 

#include <iostream>
using namespace std;

int fact( int n ){

	//base case:
	if( n <= 1 ) return 1;
		
	return n * fact(n-1);
}

int main(){
	cout << fact(4) << endl;
	return 0;
}

Proof Recursively:

In the above main function, we are trying to find the factorial of the integer 4. Using the rule of the factorials, the answer should be 24 since 4x3x2x1 = 24. Applying the function and passing in 4 as the parameter, here is the tree: 

Fact(4)
	4* Fact(3)
		3* Fact(2)
			2* Fact(1)
			2* 1 <-- 2
		3* 2 <-- 6
	4* 6 <-- 24

The recursive function runs and works properly.

The Iterative Factorial function

(No recursion). This is obviously one of many ways to solve this problem. 

long fact( long n ){

	long ans = 1;

	for(long i = n; i > 1; i--)
		ans *= i;

	return ans;

}

<< Tutorial 5
Tutorial 7 >>