All recursive algorithm must have the following three stages:

Why recursion works?

In a recursive algorithm, the computer "remembers" every previous state of the problem. This information is "held" by the computer on the "activation stack" (i.e., inside of each functions workspace).
Every function has its own workspace PER CALL of the function.

As an example we will discuss about computing Factorial of a number. What is the factorial of number X?
*** factorial(X) = X * (x-1) * (x-2) * ... * 2
But "(x-1) * (x-2) * ... * 2" is the equal of factorial(X-1)
So combine definition would be factorial(X) = X * factorial(X-1);



[Problem] 
Find the factorial value of the given number, X (1 <= x <= 20) and print as shown below: 
The given number is greater than or equal to 1 and less than or equal to 20. 

[Input] 
The first input line contains the number of test cases, T. 
Then, T number of input will be given. 

[Output] 
For each given test case, print the factorial value. 


 INPUT                 =============                                                   
3 // number of Test cases 
9 // Test case index 
12 20

OUTPUT 
===============================
#1 9! = 362880 
#2 12! = 479001600 

#3 20! = 2432902008176640000


Solution for C++: 

#include
using namespace std;

long long factorial(int num);

int main(void)
{
    int test_case;
    int T;
    int num;
    long long value;

    freopen("CreateRecursion.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &num);
        value = factorial(num);
        printf("#%d %d! = %lld\n", test_case, num, value);
    }
}

long long factorial(int num)
{
    if (num == 0)
    {
        return 1;
    }
    else
    {
        return num * factorial(num - 1);
    }
}

Solution for Java: