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

Visualization: https://www.educative.io/courses/recursion-for-coding-interviews-in-java/xl7GjENLLvE

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