Recursion

Recursion

Definition

  • Recursion is a method of solving a problem by breaking it down into smaller, simpler subproblems. In other words, it is a way of defining a problem in terms of itself.

  • When a function calls itself.

  • Recursion is often used in data structures, such as linked lists and trees, to traverse and manipulate the data in those structures.

  • To solve a recursion problem identify the following things:

    • What are the subproblems i.e choices?

    • What is the recursion state?

    • What is the base case?

public static int fibo(int n) { //state
    if (n <= 1) { // Base case or terminating condition
        return n;
    }
    return fibo(n-1) + fibo(n-2);
}

When is a recursion applicable?

  • Problems can be broken down into smaller problems.

  • There is a terminating condition/base case.

  • N is very small (N <= 24).

What is a Recurrence Relation?

  • Mathematical description of a recursion

  • fibo(n) = fibo(n-1) + fibo(n-2), n >= 2

              1, n &lt; 2
    

What is a Recursion Tree?

  • Recursion creates a DFS tree when executing.

  • Visualisation: https://visualgo.net/bn/recursion

  • For every recursion, you should be able to visualise the recursion tree.

How to find the time complexity of a recursion?

  • No of nodes in the recursion tree * No of operations per node. Try drawing a small recursion tree to estimate.

  • For fibo: 2^N * 1

  • https://www.interviewbit.com/problems/reccmpl2/ [Draw recursion tree]

  • Generally, it is of the form: (X^Y)*P where X = no of choices, Y = total states, P = No of operations per state

How to find the Space complexity of a recursion?

So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.

Thank you, Have a nice day !!