224: Recursions

1. Calculate base ^ pow through recursions:

#include <iostream>

using namespace std;

int power(int base, int pow)

{

    if (pow == 0)

    {

        return 1;

    }

    int prevAns = power(base, pow - 1);

    return base * prevAns;

}

int main()

{

    int base = 2;

    int pow = 5;

    cout << base << '^' << pow << ": " << power(base, pow) << endl;

}

/*

2 * 2 * 2 * 2 * 2

base ^ pow = base * (base ^ power - 1)

*/

 

2: Calculate factorial through recursion:

#include <iostream>

using namespace std;

int factorial(int num)

{

    if (num == 1)

    {

        return 1;

    }

    int prev = factorial(num - 1);

    return num * prev;

    // or return num * factorial(num - 1)

}

int main()

{

    int num = 5;

    cout << num << "!: " << factorial(num) << endl;

    return 0;

}

// 5! = 5 * 4 * 3 * 2 * 1

// num! = num * (num - 1)!

3. Write a program to print n number of fibonacci sequence numbers:

In this program, we are printing every fibonacci number and returning the last fibonacci number so that it can be printed when returned to the main.

#include <iostream>

using namespace std;

int fibonacci(int target, int term1 = 0, int term2 = 1)

{

    cout << term1 << " ";

    if (target == 0)

    {

        return term1 + term2;

    }

    else

    {

       return fibonacci(target - 1, term2, term1 + term2);

    }

}

int main()

{

    cout << "Fibonacci Series: " << fibonacci(5);

    return 0;

}