Welcome guest! Click here to register or login.
logo



<< Tutorial 5
Tutorial 7 >>

Recursion

***Please register FREE to rate this tutorial***


Examples
Basics
Tracing
Examples
Example 1

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.

Each time a recursive call is made, it is placed on a runtime stack. More details will be given on stacks later on in tutorial 11.

Recursive tracing

In order to see what recursion is doing, it is a good practice to trace the calling from the stack. There is a great example of tracing and recursive functions in general: The factorial function.

Example 1:
Factorial recursion

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

Below is the actual program with the recursive factorial function: 

//  for loop to print out index
#include <iostream>
using namespace std;

int fact( int n ){

	//base case:
	if( n == 1 || n == 0 ) return 1;

	return n * fact(n-1);
}

int main(){
	int n = 0;
	cout << "Enter a number to find the factorial: ";
	cin >> n;

        cout << fact(n) << endl;
	return 0;
}

The program will request an integer from the user and try to find it's factorial (within range of an int type).

In the function itself, the base case is when the parameter n is equal to 0 or 1. The reason for this is because according to the mathematical rule of factorials, when trying to find 0 or 1 factorial, the answer is 1. The function will return to it's most recent call point, the value 1.

Below is a step by step trace of the program: 

fact(4)
    |
   4* fact(3)
        |
       3* fact(2)
            |
	   2* fact(1)
	        |
	        1

When the initial call is made [ fact(4) ], the base case is checked. Since it is false, the recursive call is made and therefore returns 4 * fact(3). Now, the base case is also false when trying to find the fact of 3 so the function will return 3 * fact(2). The same applies for the fact(2) call so we will return 2 * fact(1). With this, the base case is true since the n == 1.

Below is the "backwards" trace of the example:

fact(4)
    |
   4* fact(3)
        |
       3* fact(2)
            |
	   2* 1

fact(4)
    |
   4* fact(3)
        |
       3* 2

fact(4)
    |
   4* 6

The answer for the fact(4) is 24.

<< Tutorial 5
Tutorial 7 >>