Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow # Recursion

Geeky Girl
·Dec 10, 2022·

## 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?

• Recursion uses a stack to come back to the calling function i.e it stores meta information like memory address, state etc. So we use at least O(Size of stack memory).

• Example: fact(n) = n*fact(n-1)

• If we define extra variables at states then that memory is added up.

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 !!