Recursions

Q1. Sum of first 'n' natural numbers using recursion :

My method:

#include<iostream>
using namespace std;

int sum (int n)
{
    static int sum2=0;
    if (n>0)
    {
        sum2+=n;
        sum(n-1);
    }
    return sum2;
}

int main()
{

    cout << sum(5);
    return 0;
}

Sir's Method:

#include<iostream>
using namespace std;

int sum (int n)
{
    if (n==0) 
        return 0;
    else
        return n + sum(n-1);
}

int main()
{

    cout << sum(5);
    return 0;
}

Q2. Factorial using Recursion:

#include<iostream>
using namespace std;

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

int main()
{
    cout << factorial(5);
    return 0;
}

Q3. Power using Recursion:

#include<iostream>
using namespace std;

int power (int m, int n)
{
    if (n==0)
        return 1;
    else
        return power(m, n-1)*m;
}

int main()
{
    cout << power(5, 2);
    return 0;
}

Another Method (n/2)

#include<iostream>
using namespace std;

int power (int m, int n)
{
    if (n==0)
        return 1;
    else if (n%2==0)
        return power(m*m, n/2);
    else
        return power(m, n-1)*m;
}

int main()
{
    cout << power(10, 3);
    return 0;
}

Q4. Taylor Series e^x using recursion :

Pasted image 20231212102043.png

Simple Recursion :

#include<iostream>
using namespace std;

double e(int x, int n)
{
    static double p=1, f=1;
    double r;
    if(n==0)
        return 1;
    else
    {
        r = e(x, n-1);
        p=p*x;
        f=f*n;
        return r + p/f;
    }
}

int main()
{
    cout << e(4, 50);
    return 0;
}

Horner's Rule :

Pasted image 20231212114309.png

#include<iostream>
using namespace std;

double e(int x, int n)
{
    static double r = 1;
    if(n==0)
        return 1;
    else
    {
        r = 1 + (r*x)/n;
        e(x, n-1);
        return r;
    }
}

int main()
{
    cout << e(4, 60);
    return 0;
}

Using Iterative / Loop :

#include<iostream>
using namespace std;
int main()
{

    int n=60;
    int x=4;
    double sum = 1;
    double calc=1;

    for (int i=1; i <=n; i++)
    {
        calc = (double)x/i*calc;
        sum += calc;
    }
    cout << sum;
    return 0;
}

Q5. Fibonacci Series using Recursion :

Pasted image 20231212134904.png

#include<iostream>
using namespace std;

int fib(int n)
{
    if (n==0)
        return 0;
    else if (n==1)
        return 1;
    else
    {
        return fib (n-2) + fib (n-1);
    }
}

int main()
{
    cout << fib(7) << " ";

    return 0;
}

Memoization :

Pasted image 20231212135748.png
Storing the results of different function calls so as to reduce the number of function call is called memoization :

#include <stdio.h>

int F[10];
int mfib(int n)
{
    if (n <= 1)
    {
        F[n] = n;
        return n;
    }
    else
    {
        if (F[n - 2] == -1)
            F[n - 2] = mfib(n - 2);
        if (F[n - 1] == -1)
            F[n - 1] = mfib(n - 1);
        F[n] = F[n - 2] + F[n - 1];
        return F[n - 2] + F[n - 1];
    }
}
int main()
{
    int i;
    for (i = 0; i < 10; i++)
        F[i] = -1;
    printf("%d \n", mfib(7));
    return 0;
}

Q6. ⁿC_r (ncr) : (Pascal Triangle) Using Recursion

Pasted image 20231212164835.png

Here the function is calculating ncr using pascal's triangle concept.

#include<iostream>
using namespace std;

int ncr(int n, int r)
{
    if (r==0 || n==r)
        return 1;
    else
    {
        return ncr(n-1, r-1) + ncr(n-1, r);
    }
}

int main()
{

    cout << ncr(4, 2);

    return 0;
}

Without Recursion :

#include<iostream>
using namespace std;

int fact(int n)
{
    if (n==0 || n== 1)
        return 1;
    else
    {
        return n*fact(n-1);
    }
}

int ncr(int n, int r)
{
    return  fact(n)/(fact(r)*fact(n-r));
}

int main()
{
    cout << ncr(4, 2);
    return 0;
}

Q7. Tower of Hanoi :

Pasted image 20231213103845.png
Pasted image 20231213120144.png

#include<iostream>
using namespace std;

int TOH(int n, int A, int B, int C)
{
    if(n>0)
    {
        TOH(n-1, A, C, B); //A C B
        printf("%d to %d\n", A, C );
        TOH(n-1, B, A, C);
    }
}

int main()
{
    TOH(3, 1,2,3);
    return 0;
}