Recursion Objectives:
- What is Recursion?
- Why do we need Recursion?
- The Logic behind the Recursion
- Recursive vs Iterative Solutions
- How to Write Recursion in 3 Steps?
- Find Fibonacci Series using Recursion
What is Recursion?
Recursion is a programming technique where a function calls itself directly or indirectly. A recursive function contains a base case, which is the condition that stops the recursion, and a recursive case, which is the condition that allows the function to call itself again.
Recursion is often used to solve problems that have a recursive structure, such as finding the factorial of a number, calculating the Fibonacci sequence, or traversing a tree data structure.
- Performing the same operation multiple times with different inputs
- In every step we try smaller inputs to make the problem smaller.
- Base condition is needed to stop the recursion, otherwise infinite loop will occur.
Why do we need Recursion?
1. Recursive thinking is really important in programming and it helps you break down big problems into smaller ones and easier to use
when to choose recursion?
- If you can divine the problem into similar sub problems
- Design an algorithm to compute nth…
- Write code to list the n…
- Implement a method to compute all.
- Practice
2. The prominent usage of recursion in data structures like trees and graphs.
3. It is used in many algorithms (divide and conquer, greedy and dynamic programming)
The Logic behind the Recursion
1. A method calls it self
2. Exit from infinite loop
static string recursionMethod(String[] parameters) {
if (exit from condition satisfied) {
return some value;
} else {
recursionMethod(modified parameters);
}
}Recursive vs Iterative Solutions
| Recursive | Iterative |
| static int powerOfTwo(int n) { if (n==0) { return 1; } else { var power = 2*powerOfTwo(n-1); return power; } } | static int powerOfTwoIT(int n) { var i = 0; var power = 1; while (i < n) { power = power * 2; i = i + 1; } return power; } |
| Points | Recursion | Iteration | |
| Space efficient? | No | Yes | No stack memory required in case of iteration. |
| Time efficient? | No | Yes | In case of recursion system needs more time for pop and push elements to stack memory which makes recursion less time efficient |
| Easy to code? | Yes | No | We use recursion especially in the cases we know that a problem can be divided into similar sub problems. |
When to Use/Avoid Recursion?
When to use it?
- When we use memorization in recursion
- When we can easily breakdown a problem into similar subproblem
- When we are fine with extra overhead (both time and space) that comes with it
- When we need a quick working solution instead of efficient one
- When traverse a tree
– preorder tree traversal : 15, 9, 3, 1, 4, 12, 23, 17, 28
When should we avoid it?
- If time and space complexity matters for us.
- Recursion uses more memory. If we use embedded memory. For example an application
- that takes more memory in the phone is not efficient
- Recursion can be slow
Happy Learning!!
