Hey guys, this is part 12 of my programming tutorials! This tutorial is in C++. If you want to catch up on any of my tutorials, here they are:

Part 1: Hello World!

Part 2: Variables

Part 3: Functions

Part 4: if(), else, else if()

Part 5: Loops

Part 6: Arrays

Part 7: Basic Input/Output

Part 9: Sorting Arrays

Part 10: Random Numbers

Part 11: Colored Text in your Terminal

This tutorial is about recursion. A recursive function is a function that calls itself! This can get confusing, but we will walk through a simple example.

Factorial

The factorial function is one of the easiest recursive functions to write. Here is the algorithm:

If you didn't know already, you simply multiply an integer by all of the positive integers less than it.

1! = 1
2! = 2 * 1
3! = 3 * 2 * 1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1

Let's look at the program I wrote and decipher it:

#include
using namespace std;

unsigned int fact(unsigned int num)
{
    if(num == 1)
        return 1;

    return num * fact(num - 1);
}

int main()
{
    unsigned int num;
    cout << "Enter a integer from 1 to 33: ";
    cin >> num;
    if(num < 1 || num > 33)
        cout << "Invalid number.\n";
    else
        cout << "The factorial of " << num << " is: " << fact(num) << endl;

    return 0;
}

main():

• "num" is an unsigned int (no negatives) to hold the number we are taking the factorial of
• prompt the user and scan for the number
• if the number is less than 1 or greater than 33, print an error message (max unsigned int is smaller than 34!)
• if it is within the correct range, then print "The factorial of (num) is: (num!)" -- I called the function "fact()" on this line also

fact()

• if "num" is 1, then simply return 1 (1! = 1)
• for every other number, call fact() again, except with one less than "num" and multiply it by "num"

You may still not see how this works, so here is a more thorough example:

• Say we enter 3.
• fact(3) is called
• 3 does not equal 1
• "return num * fact(num - 1);"
• The function needs to calculate "fact(2)" before it can return a number
  • fact(2) is called
  • 2 does not equal 1
  • "return num * fact(num - 1);"
  • The function needs to calculate "fact(1)" before it can return a number
    • fact(1) is called
    • 1 equals 1, so return 1
  • return 2 * 1 (= 2)
• return 3 * 2 (= 6)

3! = 6
... Each tab represents the scope of each function call (what "fact(3)" sees, one tab for what fact(2) sees, and two tabs for what fact(1) sees).

Here is some sample output of the program (user input in bold):

[cmw4026@omega test]$ g++ fact.cpp
[cmw4026@omega test]$ ./a.out
Enter a integer from 1 to 33: 4
The factorial of 4 is: 24
[cmw4026@omega test]$ ./a.out
Enter a integer from 1 to 33: 7
The factorial of 7 is: 5040
[cmw4026@omega test]$ ./a.out
Enter a integer from 1 to 33: 1
The factorial of 1 is: 1
[cmw4026@omega test]$ ./a.out
Enter a integer from 1 to 33: 34
Invalid number.
[cmw4026@omega test]$ ./a.out
Enter a integer from 1 to 33: 0
Invalid number.
[cmw4026@omega test]$ ./a.out
Enter a integer from 1 to 33: 33
The factorial of 33 is: 2147483648
[cmw4026@omega test]$

I hope this was helpful! Leave any suggestions in the comments!