Recursion Made Easy: A Beginner's Guide

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)

First Call to sumHelper

• sumHelper(3, 0)
  • n is not 0, so it calls sumHelper(n-1, acc + n) which is sumHelper(2, 3)

Second Call to sumHelper

• sumHelper(2, 3)
  • Again, n is not 0, so it calls sumHelper(n-1, acc + n) which is sumHelper(1, 5)

Third Call to sumHelper

• sumHelper(1, 5)
  • n is still not 0, so it calls sumHelper(n-1, acc + n) which is sumHelper(0, 6)

Fourth Call to sumHelper

• sumHelper(0, 6)
  • This time, n is 0, so it returns acc which is 6

Conclusion

The recursive calls build up as follows:

1. sumHelper(3, 0) calls sumHelper(2, 3)
2. sumHelper(2, 3) calls sumHelper(1, 5)
3. sumHelper(1, 5) calls sumHelper(0, 6)
4. sumHelper(0, 6) returns 6

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)

TC = O(2^n) // exponential time complexity // why? because for each n, we are calling two recursive calls.

SC = O(n) // why? because n function calls are stored in stack.