Recursion

Definition

1. Function calling itself.

2. A problem is broken into smaller problem(subproblem) and the solution is generated using the subproblems.

Example

Here's an example of how recursion can be used to calculate the sum of the first N natural numbers:

sum(N) = 1 + 2 + 3 + 4 + ..... + N-1 + N
sum(N) = sum(N-1) + N

Here, sum(N-1) is smaller instance of same problem that is sum(N).

sum(N-1) is known as a subproblem.

How to write a recursive code?

We can solve any recursive problem using below magic steps:

1. Assumptions: Decide what the function does for the given problem.

2. Main logic: Break the problem down into smaller subproblems to solve the assumption.

3. Base case: Identify the inputs for which we need to stop the recursion.

Problem Statement

Given a positive integer N, find the factorial of N.

Solution :

Assumptions: Create a function which -

• Takes an integer value N as parameter.

• Calculates and returns N!

• return type should be integer.

Main logic:

• The factorial of N is equal to N times the factorial of (N-1)

• We made assumption that sum(N) calculates and return factorial of N natural number. Similarly, sum(N-1) shall calculate and return the factorial of N-1 natural number.factorial(N) = N * factorial(N-1)

Base case: The base case is when N equals 0, i.e., 0! = 1

For example,

When we perform, factorial(N) = N * factorial(N-1), value of N keeps on decreasing by 1.

N -> (N-1) -> (N-2) ........ 2 -> 1

for N = 1 as well as 0, the factorial is 1.

So, we can write base case for N = 0 which will also cover for N = 1.

Pseudocode

int factorial(int N) {
    // base case
    if (N == 0) {
        return 1;
    }
    // recursive case
    return N * factorial(N-1);
}

Dry Run

Problem Statement

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding numbers.

The sequence goes like this:

Given a positive integer N, write a function to compute the Nth number in the Fibonacci sequence using recursion.

Example

Input = 6 Output = 8

Solution

Assumptions: Create a function which -

• Takes an integer value N as parameter.

• calculates and returns N number in the fibonacci sequence.

  th

• return type should be integer.

Main logic: Recursively compute the (N-1)th and (N-2)th numbers in the sequence and add them together to get the nth number.

fibonacci(N) = fibonacci(N - 1) + fibonacci(N - 2)

Base case: If N is 0 or 1, return the corresponding value in the Fibonacci sequence.

• Since, according to the definition of fibonacci sequence, the smallest two possible values of N are N = 1 & N = 2, therefore, stop recursion as soon as N becomes 0 or 1.

Pseudocode

int fibonacci(int N) {
    // base case
    if (N == 0 || N == 1) {
        return N;
    }

    // recursive case
    return fibonacci(N - 1) + fibonacci(N - 2);
}

Function Call Tracing

Problem Statement

Given two integers a and n, find a n using recursion.

Input

a = 2
n = 3

Output

8

Explanation

23 i.e, 2 2 2 = 8.

Brute Force Approach

The above problem can be redefined as:

a ^ n = a * a * a......* a (n times).

The problem can be broken into subproblem as:

a ^ n = a ^ (n-1) * a

So we can say that pow(a,n) is equivalent to

pow(a,n) = pow(a,n-1) * a

Here, pow(a,n) is the defined as a^n.

We have seen how the problem is broken into subproblems. Hence, it can be solved using recursion.

Below is the algorithm:

• Assumption step:

  • Define a recursive function pow(a,n).

• Main Logic:

  • Define a recursive case: if n > 0, then calculate the pow(a,n-1).

  • Return a * pow(a,n-1).

• Base Case:

  • Base condition: if n = 0, then return 1.

Pseudocode

function pow(int a, int n){
    if(n == 0) return 1;
    return a * pow(a,n-1);
}

Optimized Approach

We can find pow(a,n) by one more relation :

an = an/2 * an/2 (when n is even)

an = an/2 an/2 a (when n is odd)

Below is the algorithm:

• Assumption Step:

  • Define a recursive function pow(a,n).

• Main Logic:

  • Calculate pow(a,n/2) and store it in a variable p.

  • if n is odd, then return p p a.

  • else return p * p.

• Base Condition:

  • if n = 0, then return 1.

Pseudocode

Function pow(int a, int n){
    if(n == 0) return 1;

    int p = pow(a, n/2);

    if(n % 2 == 0) {
        return p * p;
    }
    else {
        return p * p * a;
    }
}

Please do a dry run, recursion is more about dry run than code.