Recursion

Recursion is a technique where a function calls itself to solve a problem. It breaks a big problem into smaller subproblems, until reaching a base condition.

1type fun(params) {
2	if(<base_condition>){
3		...
4		fun(params)
5		...
6	}
7}

Recursion with static variable

A static variable inside a function:

Is created only once
Maintains its value between function calls
Lives for the entire program duration
Initialized only once (default = 0)

In recursive functions:

Normal/local variables reset every call
Static variables remember previous values
This changes the logic and output of recursion

1int recursion_with_static_variable(int n)
2{
3    static int x = 0;  // created once
4    if (n > 0)
5    {
6        x++;           // increments every recursive call
7        return recursion_with_static_variable(n - 1) + x;
8    }
9    return 0;
10}

Types of Recursion

Tail Recursion

A recursive function where the recursive call is the last statement in the function.
No work is done after the recursive call.

1void tail_recursion(int n)
2{
3    if (n > 0)
4    {
5        cout << n << endl;
6        tail_recursion(n - 1);
7    }
8}

Head Recursion

A recursive function where the recursive call happens before any processing.

1void head_recursion(int n)
2{
3    if (n > 0)
4    {
5        head_recursion(n - 1);
6        cout << n << endl;
7    }
8}

Tree Recursion

A function that makes more than one recursive call.

1void tree_recursion(int n)
2{
3    if (n > 0)
4    {
5        cout << n;s
6        tree_recursion(n - 1);
7        tree_recursion(n - 1);
8    }
9}

Indirect Recursion

When a function calls another function, and that function calls the first one again.

1void A(int n);
2void B(int n);
3
4void A(int n) {
5    if(n > 0) {
6        cout << n << " ";
7        B(n - 1);     // calls B
8    }
9}
10
11void B(int n) {
12    if(n > 0) {
13        cout << n << " ";
14        A(n / 2);     // calls A again
15    }
16}

Nested Recursion

When the argument of a recursive function is another recursive call.

1int nested(int n) {
2    if(n > 100) return n - 10;
3    return nested(nested(n + 11));
4}
5// this is called - - McCarthy 91 function

Recursion practice questions

1int sum_of_first_n_natural_number(int n)
2{
3    if (n <= 0)
4        return 0;
5    return sum_of_first_n_natural_number(n - 1) + n;
6}

1int factorial_of_number(int n)
2{
3    if (n == 0 || n == 1)
4        return 1;
5    return factorial_of_number(n - 1) * n;
6}

1int power_of_number(int element, int power)
2{
3    if (power == 0)
4        return 1;
5    return power_of_number(element, power - 1) * element;
6}

1int power_of_number_optamized(int element, int power)
2{
3    if (power == 0)
4        return 1;
5    if (power % 2 == 0)
6        return power_of_number_optamized(element * element, power / 2);
7    else
8        return power_of_number_optamized(element * element, (power - 1) / 2) * element;
9}

1// e^x = 1 + x + x^2/2! + x^3/3! + .... + n terms
2double taylor_series_ePowerx(int x, int n)
3{
4    static double power = 1, factorial = 1;
5    double resultOfTerm;
6    if (n == 0)
7        return 1;
8    else
9    {
10        resultOfTerm = taylor_series_ePowerx(x, n - 1);
11        power = power * x;
12        factorial = factorial * n;
13        return resultOfTerm + power / factorial;
14    }
15}

1double taylor_series_ePowerx_using_horner_rule(int x, int n)
2{
3    static double term;
4    if (n == 0)
5        return term;
6    term = 1 + ((x * term)/ n);
7    return taylor_series_ePowerx_using_horner_rule(x, n-1);
8}

1int nth_term_fibonacchi_series(int n)
2{
3    if (n <= 1)
4    {
5        return n;
6    }
7    return nth_term_fibonacchi_series(n - 1) + nth_term_fibonacchi_series(n - 2);
8}

1int nth_term_fibonacchi_series_optamized(int n)
2{
3    static int *fibonacchi_series = nullptr;
4    
5    // Allocate ONCE — only during the first function call
6    if (fibonacchi_series == nullptr)
7    {
8        fibonacchi_series = new int[n + 1];
9        // initialize all to -1
10        for (int i = 0; i < n + 1; i++)
11            fibonacchi_series[i] = -1;
12    }
13    
14    if (n <= 1)
15    {
16        fibonacchi_series[n] = n;
17        return n;
18    }
19
20    if(fibonacchi_series[n] != -1) {
21        return fibonacchi_series[n];
22    }
23
24    fibonacchi_series[n] = nth_term_fibonacchi_series_optamized(n-1) + nth_term_fibonacchi_series_optamized(n-2);
25    return fibonacchi_series[n];
26}

1int calculate_nCr(int n, int r)
2{
3    int t1, t2, t3;
4    t1 = factorial_of_number(n);
5    t2 = factorial_of_number(r);
6    t3 = factorial_of_number(n - r);
7    return t1 / (t2 * t3);
8}
9
10int calculate_nCr_recursion(int n, int r)
11{
12    if (r == 0 || n == r)
13    {
14        return 1;
15    }
16    return calculate_nCr_recursion(n - 1, r - 1) + calculate_nCr_recursion(n - 1, r);
17}

1void tower_of_hanoi(int n, int a, int b, int c)
2{
3    if (n > 0)
4    {
5        tower_of_hanoi(n - 1, a, c, b);
6        cout << "from " << a << " to " << c << endl;
7        tower_of_hanoi(n - 1, b, a, c);s
8    }
9}