Let's try to explain this with an example.  Computing a number to the power of another number can be viewed as a recursive process.  We will look at the process for computing 2⁴.
        2⁴ is the same as 2*2³, so we need to find the answer to 2³
        2³ is the same as 2*2², so we need to find the answer to 2²,
        2² is the same as 2*2¹, so we need to find the answer to 2¹,
        2¹ is the same as 2*2⁰ and we know the answer to 2⁰ which is 1.  This is our base.

Let's use the base to go up and find the answer to others above it:
       2¹ = 2*2⁰ = 2*1 = 2, this will help us find:
       2² = 2*2¹,  which now becomes 2.2 = 4, We move up to find:
       2³ = 2*2² which then becomes 2*4 = 8, and at last, we will compute:
       2⁴ = 2*2³ = 2*8 = 16.

This process is shown below. Follow the black fonts until you reach the end, then follow the red font to come back up.

2⁴ = 2*2³ = 2*8 = 16                                        Forward Step 1/Backward Step 4
            2³ = 2*2² = 2*4 = 8                              Forward Step 2/Backward Step 3
                        2² = 2*2¹ = 2*2 = 4                  Forward Step 3/Backward Step 2
                                    2¹ = 2*2⁰ = 2*1 =2       Forward Step 4/Backward Step 1
                                                2⁰ = 1                Base (use it to go up)

When you write a function to solve a task, you may break the task into subtasks.  Sometimes, one of the subtasks is a smaller version of the same task and can be accomplished by calling itself multiple times.  In such cases the function is said to be recursive.

Let's look at an example.  Suppose you want to write a C++ program that takes an array of characters and displays 1/2 of the array (string) on a line until there is only one character left.  In order to do this, we split the initial stream in half, then the remaining in half, and so forth until we get to the point that there is only one character left.  Once there, we display the single character, then double that, ... until we reach the top.

// P13_1.cpp - This program demonstrates the recursive process
// It takes a string and displays 1/2 of it on a line until there is only
// one character left

#include<iostream>
#include<string>
#include<cstring>

using namespace std;
void display_half(string s);

int main( )
{
      string my_string;
      cout << "Enter a string \n";
      cin >> my_string;

      display_half(my_string);  // Call to get a task done

      return 0;
}

void display_half(string s)
{
       int length;
       string temp;

       length = strlen(s.c_str( ))/2;
       temp = s.substr(0, length);

       if(length != 1)
       {
              display_half(temp);     // call to get a subtask done
       }
       cout << temp << endl;
}

As you may have noticed the call to terminate the recursion process was at:
       if(length != 1)
       {
              display_half(temp);     // call to get a subtask done
       }

The display_half is called until length is equal to 1.  Then from that point on, we start displaying the half strings.  If you try a string with 7 characters, you will notice that a very interesting thing will happen. Here is how the output looks like for the given input:

input: *******

output:
*
***

As you can see, the first time you displayed one *, then for the second time, you displayed ***.  You may have expected the second row to be **.  Why didn't you have **?

If you pay attention to the recursion process, the first string had 7 characters (*) in it.  That string divided by 2, results in 3 characters (*).  Then 3 divided by 2 will result in one *.  While we go through this process a stack will remember what was going on in the previous stage. Thus, when we come back from the last call after displaying a single *, we execute the one with three characters.  So instead of doubling the last number, as we go up, we still remember the actual number of asterisks.

There are two things you need to have in mind for having a successful recursive function:
    1) In completing a task, the function should include call(s) to itself to accomplish one or more smaller versions of the task.
    2) The function should include one or more cases without recursive calls, which are known as the base cases or stopping cases.

A recursive function without a base case will end up in an infinite recursion.

Exercise 13.1
Factorial of a number is defined as:
            n! = n(n-1)(n-2)(n-3)...(2)(1)

For example, 4! = 4*3*2*1

The n! can be written in terms of (n-1)! as:

n! = n* (n-1)!

(n-1)! = (n-1)*(n-2)!

and so forth.

Thus, in order to compute n!, we need (n-1)!, to have (n-1)!, we need (n-2)! and so forth.  As you may immediately notice, the base case for factorial is 1 because 1! = 1.  Write a program that uses a recursive function called factorial that takes an integer n as its argument and returns n! to the main.