Recursion

What is recursion? 

Sometimes a problem is too difficult or too complex to solve because it is too big. If the problem can be broken down into smaller versions of itself, we may be able to find a way to solve one of these smaller versions and then be able to build up to a solution to the entire problem. This is the idea behind recursion; recursive algorithms break down a problem into smaller pieces which you either already know the answer to, or can solve by applying the same algorithm to each piece, and then combining the results.

Identify the 3 parts of the recursive algorithm :

All recursive algorithm must have the following three stages:

1. Base Case: if ( actualResult() == 2 ) result = a + b;
2. "Work toward base case": a+b becomes the first parameter
   This reduces the number of parameters to the function from 3 to 2, and 2 is the base case!
3. Recursive Call: add_numbers(a+b, c);

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:

package com.algorithm;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Recursion {

    static private final String INPUT = System.getProperty("user.dir") + "\\src\\data\\recursionInput.txt";
    static Scanner sc;

    public static void main(String[] args) {
        FileInputStream instream = null;
        try {
            instream = new FileInputStream(INPUT);
            System.setIn(instream);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; ++test_case)
        {
            int num = sc.nextInt();

            long value = factorial(num);

            System.out.println("#" + test_case + " " + num + "! = " + value);
        }

        sc.close();
    }

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