Recursion -
IMP Links -
- Striver Recursion YT
- Aditya Verma - Recursion / good playlist on recursion
- awesome-leetcode-resources
- Become Master In Recursion
- Recursion LC problems
When a function calls itself until a specified condition is met, it is called recursion.
Recursion Example-
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
In the above example, the function factorial() calls itself until n is equal to 0. When n is equal to 0, the function returns 1 and the recursion stops.
Dryrun -
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1
So, factorial(3) = 3 * 2 * 1 * 1 = 6
Dryrun with stack diagram-
factorial(3) -> 3 * factorial(2) -> 3 * 2 * factorial(1) -> 3 * 2 * 1 * factorial(0) -> 3 * 2 * 1 * 1
factorial(2) -> 2 * factorial(1) -> 2 * 1
factorial(1) -> 1
factorial(0) -> 1
- In recursion, the function calls are stored in a stack. When the base condition is met, the function calls are popped from the stack and the final result is calculated.
- Base condition is very important in recursion, otherwise the function will keep calling itself infinitely and will lead to stack overflow error.
Base condition example -
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
here base condition is n == 0, when n is 0, the function returns 1 and recursion stops.
Recursion vs Iteration -
Recursion is a powerful tool, but it is not always the best choice. Recursion can be slow and uses more memory than iteration. In some cases, recursion can lead to a stack overflow error. In general, recursion is best suited for problems that can be broken down into smaller, similar subproblems.
Iterative solutions are often more efficient and easier to understand than recursive solutions. However, there are some problems that are more naturally solved using recursion.
Basics Recursion Problems -
1. print name n times
public static void printName(String name, int n) {
if (n == 0) {
return;
}
System.out.println(name);
printName(name, n-1);
}
dryrun -
printName("John", 3) -> John
printName("John", 2) -> John
printName("John", 1) -> John
printName("John", 0) -> return
Tc = O(n)
Sc = O(n) // why? because n function calls are stored in stack.
2. print numbers from 1 to n
public static void printNumbers(int n) {
if (n == 0) {
return;
}
printNumbers(n-1);
System.out.println(n);
}
dryrun -
printNumbers(3) -> printNumbers(2) -> printNumbers(1) -> printNumbers(0) -> return
1
2
3
3. print numbers from n to 1
public static void printNumbers(int n) {
if (n == 0) {
return;
}
System.out.println(n);
printNumbers(n-1);
}
dryrun -
printNumbers(3) -> 3
printNumbers(2) -> 2
printNumbers(1) -> 1
printNumbers(0) -> return
4. print linearly from 1 to n but by backtracking
public static void printNumbers(int n) {
if (n == 0) {
return;
}
printNumbers(n-1);
System.out.println(n);
printNumbers(n-1);
}
dryrun -
printNumbers(3) -> printNumbers(2) -> printNumbers(1) -> printNumbers(0) -> return
1
printNumbers(1) -> printNumbers(0) -> return
2
printNumbers(2) -> printNumbers(1) -> printNumbers(0) -> return
1
printNumbers(1) -> printNumbers(0) -> return
3
printNumbers(3) -> printNumbers(2) -> printNumbers(1) -> printNumbers(0) -> return
1
printNumbers(1) -> printNumbers(0) -> return
2
printNumbers(2) -> printNumbers(1) -> printNumbers(0) -> return
1
printNumbers(1) -> printNumbers(0) -> return
Output - 1 2 1 3 1 2 1
5. print numbers from n to 1 but by backtracking
public static void printNumbers(int n) {
if (n == 0) {
return;
}
System.out.println(n);
printNumbers(n-1);
System.out.println(n);
}
dryrun -
printNumbers(3) -> 3
printNumbers(2) -> 2
printNumbers(1) -> 1
printNumbers(0) -> return
2
3
Output - 3 2 1 2 3
6. sum of n natural numbers
- This can done using two ways
- parametrized recursion - where we pass the sum so far as a parameter.
- non-parametrized recursion - where we don't pass the sum so far as a parameter.
Non-Parametrized Recursion
public static int sum(int n) {
if (n == 0) {
return 0;
}
return n + sum(n - 1);
}
dryrun -
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1 + sum(0)
sum(0) = 0
Output - 6
Parametrized Recursion
public static int sum(int n) {
return sumHelper(n, 0);
}
private static int sumHelper(int n, int acc) {
if (n == 0) {
return acc;
}
return sumHelper(n-1, acc + n);
}
dryrun -
Let's dry run the provided recursive method sum(int n)
with an example input of n = 3
. This method calculates the sum of all numbers from 1 to n
using a helper function sumHelper(int n, int acc)
where n
is the current number and acc
is the accumulator that holds the sum so far.
Initial Call
-
sum(3)
- This calls
sumHelper(3, 0)
- This calls
First Call to sumHelper
-
sumHelper(3, 0)
-
n
is not0
, so it callssumHelper(n-1, acc + n)
which issumHelper(2, 3)
-
Second Call to sumHelper
-
sumHelper(2, 3)
- Again,
n
is not0
, so it callssumHelper(n-1, acc + n)
which issumHelper(1, 5)
- Again,
Third Call to sumHelper
-
sumHelper(1, 5)
-
n
is still not0
, so it callssumHelper(n-1, acc + n)
which issumHelper(0, 6)
-
Fourth Call to sumHelper
-
sumHelper(0, 6)
- This time,
n
is0
, so it returnsacc
which is6
- This time,
Conclusion
The recursive calls build up as follows:
-
sumHelper(3, 0)
callssumHelper(2, 3)
-
sumHelper(2, 3)
callssumHelper(1, 5)
-
sumHelper(1, 5)
callssumHelper(0, 6)
-
sumHelper(0, 6)
returns6
Thus, the sum of numbers from 1 to 3 is 6
.
7. Reverse an array using recursion
First we will see how to reverse an array using iteration and then we will see how to reverse an array using recursion.
Iterative Approach
void reverse (int arr[], int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
Recursive Approach
public static void revArr(int[] arr, int i, int j) {
if (i >= j)
return;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
revArr(arr, i + 1, j - 1);
}
Dryrun -
revArr([1, 2, 3, 4, 5], 0, 4) -> 5 2 3 4 1
revArr([1, 2, 3, 4, 5], 1, 3) -> 5 4 3 2 1
revArr([1, 2, 3, 4, 5], 2, 2) -> return
Output - 5 4 3 2 1
Reverse array using single pointer -
public static void revArr(int[] arr, int i) {
if (i >= arr.length / 2)
return;
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
revArr(arr, i + 1);
}
8. Check if a string is a plaindrome
Iterative Approach
public static boolean palindromeStr(String str) {
int i = 0;
int j = str.length() - 1;
while (j > i) {
if (str.charAt(i) == str.charAt(j)) {
i++;
j--;
} else {
return false;
}
}
return true;
}
Recursive Approach
public static boolean palindromeStr(String str, int i, int j) {
if (j <= i)
return true;
if (str.charAt(i) != str.charAt(j))
return false;
return palindromeStr(str, i + 1, j - 1);
}
Dryrun -
palindromeStr("madam", 0, 4) -> true
palindromeStr("madam", 1, 3) -> true
palindromeStr("madam", 2, 2) -> true
Output - true
Recursive Approach - Single Pointer
public static boolean palindromeStr(String str, int i) {
if (i >= str.length() / 2)
return true;
if (str.charAt(i) != str.charAt(str.length() - i - 1))
return false;
return palindromeStr(str, i + 1);
}
TC = O(n) // why? because we are iterating through the string only once.
SC = O(n) // why? because n function calls are stored in stack.
9. Fibonacci Series
What is fibonacci series -
- The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.
Iterative Approach
public static void fibonacci(int n) {
int a = 0;
int b = 1;
for (int i = 0; i < n; i++) {
System.out.print(a + " ");
int sum = a + b;
a = b;
b = sum;
}
}
Recursive Approach
public static int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Dryrun -
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)
Top comments (0)