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