intermediate2 hours

Mastering Recursion

A comprehensive guide to understanding and mastering recursion for coding interviews

intermediate2 hours

Mastering Recursion

A comprehensive guide to understanding and mastering recursion for coding interviews

Fundamentals of Recursion

In programming, recursion is a fundamental concept that is used to solve problems that involve repetitive or recursive logic. It is a technique where a function calls itself repeatedly until it meets a predefined condition known as a base case.

Definition of Recursion

Recursion is a technique where a function calls itself repeatedly, breaking down the problem into smaller and smaller sub-problems until a base case is reached, which stops the recursion from continuing indefinitely.

The Basic Principle

The basic principle of recursion is to break down a complex problem into smaller sub-problems that can be easily solved. Each sub-problem is solved by the same function that called it, with the values carried forward to the next recursive call.

Java

1public int factorial(int n) {
2    // Base case: factorial of 0 is 1
3    if (n == 0) {
4        return 1;
5    }
6    // Recursive case: n! = n * (n-1)!
7    return n * factorial(n - 1);
8}
9
10// Example: factorial(5)
11// 5 * factorial(4)
12// 5 * 4 * factorial(3)
13// 5 * 4 * 3 * factorial(2)
14// 5 * 4 * 3 * 2 * factorial(1)
15// 5 * 4 * 3 * 2 * 1 * factorial(0)
16// 5 * 4 * 3 * 2 * 1 * 1 = 120

Step-by-Step Execution

Watch how the code executes line by line, tracking variables and the call stack:

Step-by-Step Execution

Walk through each line of code execution

Java

public int factorial(int n) {

    if (n == 0) {

        return 1;

    return n * factorial(n - 1);

// Call: factorial(4)

Step 1 of 15

Explanation

Starting factorial(4)

Variables

Call Stack (1)

factorial(4)

Understanding the Call Stack

Each recursive call creates a new frame on the call stack. Watch how frames are pushed and popped:

Call Stack Visualizer

Watch how recursive calls build up on the stack

Java

1public int factorial(int n) {
2    if (n == 0) return 1;
3    return n * factorial(n - 1);
4}

Speed:1000ms

Call Stack (Step 0/0)0 frames

Stack is empty. Click Play to start.

↑ Top of stack (most recent call)

Memory Visualization

Understanding how recursion uses memory is crucial for writing efficient code:

Memory Visualization

See how recursion uses the call stack in memory

Speed:

Stack Usage0 / 64 bytes

Step 0/12: Click Play to start

Call Stack0 frames

Stack is empty

Legend

Return Address

Parameter

Local Variable

Stack Overflow

If there's no base case or recursion depth is too deep, the stack will overflow and crash the program. Each function call uses memory!

Java

1public int factorial(int n) {
2    if (n == 0) return 1;
3    return n * factorial(n - 1);
4}

Key Components of Recursion

Base Case

The condition that stops the recursion. Without it, the function would call itself infinitely, causing a stack overflow.

Recursive Case

The part where the function calls itself with a modified argument, moving closer to the base case.

When to Use Recursion

- Problems that can be broken into smaller, similar sub-problems
- Tree and graph traversals
- Divide and conquer algorithms
- When the iterative solution is complex or unclear

Types of Recursion

Recursion comes in different forms, each with its own characteristics and use cases. Understanding these types helps you choose the right approach for your problem.

Types of Recursion

Explore different recursion patterns and when to use them

Direct Recursion

A function calls itself directly. The most common form of recursion.

Java

1public int factorial(int n) {
2    if (n == 0) return 1;
3    return n * factorial(n - 1);
4}
5
6// factorial(4)
7// = 4 * factorial(3)
8// = 4 * 3 * factorial(2)
9// = 4 * 3 * 2 * factorial(1)
10// = 4 * 3 * 2 * 1 * factorial(0)
11// = 4 * 3 * 2 * 1 * 1 = 24

Key Characteristics

•Function calls itself with modified arguments
•Must have a base case to terminate
•Each call waits for the recursive call to return

✓ Advantages

+Simple to understand
+Natural for problems with recursive structure

✗ Disadvantages

−Uses stack space proportional to recursion depth
−Risk of stack overflow

When to Use

Use for problems that naturally break down into smaller versions of the same problem (factorial, tree traversal, binary search).

Summary of Recursion Types

Direct Recursion

A function calls itself directly. The most common form and easiest to understand.

Use case: Factorial, Fibonacci, Tree traversal

Indirect Recursion

Two or more functions call each other in a cycle until a base case is reached.

Use case: Even/odd checks, state machines

Tail Recursion

The recursive call is the last operation. Can be optimized by compilers to O(1) space.

Use case: When stack space optimization is needed

Head Recursion

The recursive call is the first operation. Processing happens during unwinding.

Use case: Reverse order processing

Tree Recursion

Function makes multiple recursive calls, creating a tree of calls. Often exponential.

Use case: Fibonacci (naive), binary tree operations

Mutual Recursion

Functions defined in terms of each other. Common in parsers and compilers.

Use case: Expression parsing, grammar rules

Choosing the Right Type

Direct: Default choice for most recursive problems
Tail: When you need to optimize stack usage
Tree: For divide-and-conquer (but consider memoization)
Mutual: When problem has interdependent parts

Recursion with Numbers

Numbers are often the first domain where we practice recursion. Let's explore classic number-based recursive problems that frequently appear in coding interviews.

Fibonacci Sequence

The Fibonacci sequence demonstrates tree recursion where each call spawns multiple recursive calls.

Recursion Tree Visualizer

See how Fibonacci creates a tree of recursive calls

Speed:

Total Calls

Completed

—

Result

Active

Completed

Pending

f(5)

f(4)

f(3)

f(2)

f(1)

f(0)

f(1)

f(2)

f(1)

f(0)

f(3)

f(2)

f(1)

f(0)

f(1)

Observation: Notice how fib(3) is calculated multiple times? This is called overlapping subproblems — the main reason we use Dynamic Programming to optimize!

Java

1public int fib(int n) {
2    if (n <= 1) return n;
3    return fib(n - 1) + fib(n - 2);
4}
5
6// Optimized with memoization - O(n) time
7public int fibMemo(int n, int[] memo) {
8    if (n <= 1) return n;
9    if (memo[n] != 0) return memo[n];
10    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
11    return memo[n];
12}

Performance Warning

The naive recursive Fibonacci has O(2^n) time complexity. Use memoization or dynamic programming to optimize to O(n).

Power Calculation

Calculate x^n efficiently using recursion with the optimization x^n = (x^(n/2))^2.

Java

1public double power(double base, int exp) {
2    if (exp == 0) return 1;
3    if (exp < 0) return 1 / power(base, -exp);
4
5    // Optimization: x^n = (x^(n/2))^2
6    if (exp % 2 == 0) {
7        double half = power(base, exp / 2);
8        return half * half;
9    }
10    return base * power(base, exp - 1);
11}
12
13// Time: O(log n) instead of O(n)

Sum of Digits

Java

1public int sumDigits(int n) {
2    if (n == 0) return 0;
3    return (n % 10) + sumDigits(n / 10);
4}
5
6// sumDigits(1234)
7// = 4 + sumDigits(123)
8// = 4 + 3 + sumDigits(12)
9// = 4 + 3 + 2 + sumDigits(1)
10// = 4 + 3 + 2 + 1 = 10

GCD (Euclidean Algorithm)

Java

1public int gcd(int a, int b) {
2    if (b == 0) return a;
3    return gcd(b, a % b);
4}
5
6// gcd(48, 18)
7// = gcd(18, 48 % 18) = gcd(18, 12)
8// = gcd(12, 18 % 12) = gcd(12, 6)
9// = gcd(6, 12 % 6) = gcd(6, 0)
10// = 6

Count Digits

Java

1public int countDigits(int n) {
2    if (n == 0) return 0;
3    return 1 + countDigits(n / 10);
4}
5
6// countDigits(12345) = 5

Check Prime (with Helper)

Java

1public boolean isPrime(int n) {
2    if (n <= 1) return false;
3    return isPrimeHelper(n, 2);
4}
5
6private boolean isPrimeHelper(int n, int divisor) {
7    if (divisor * divisor > n) return true;
8    if (n % divisor == 0) return false;
9    return isPrimeHelper(n, divisor + 1);
10}

Practice Problems

1. Calculate n-th triangular number: 1 + 2 + 3 + ... + n
2. Convert decimal to binary recursively
3. Find number of ways to climb n stairs (1 or 2 steps at a time)
4. Calculate modular exponentiation (a^b mod m)

Recursion with Strings

Strings are naturally recursive structures - a string is either empty or a character followed by another string. This makes them perfect for recursive solutions.

Reverse a String

One of the most classic recursive string problems. Watch the step-by-step execution:

Step-by-Step Execution

Walk through each line of code execution

Java

public String reverse(String str) {

    if (str.isEmpty()) {

        return "";

    return reverse(str.substring(1)) + str.charAt(0);

// Call: reverse("hello")

Step 1 of 17

Explanation

Starting reverse("hello")

Variables

str"hello"

Call Stack (1)

reverse("hello")

Java

1public String reverse(String str) {
2    if (str.isEmpty()) return "";
3    return reverse(str.substring(1)) + str.charAt(0);
4}
5
6// reverse("hello")
7// = reverse("ello") + "h"
8// = reverse("llo") + "e" + "h"
9// = reverse("lo") + "l" + "e" + "h"
10// = reverse("o") + "l" + "l" + "e" + "h"
11// = reverse("") + "o" + "l" + "l" + "e" + "h"
12// = "olleh"

Check Palindrome

Java

1public boolean isPalindrome(String str) {
2    if (str.length() <= 1) return true;
3    if (str.charAt(0) != str.charAt(str.length() - 1)) {
4        return false;
5    }
6    return isPalindrome(str.substring(1, str.length() - 1));
7}
8
9// isPalindrome("racecar")
10// 'r' == 'r' -> isPalindrome("aceca")
11// 'a' == 'a' -> isPalindrome("cec")
12// 'c' == 'c' -> isPalindrome("e")
13// length <= 1 -> true

Count Vowels

Java

1public int countVowels(String str) {
2    if (str.isEmpty()) return 0;
3
4    int count = "aeiouAEIOU".indexOf(str.charAt(0)) >= 0 ? 1 : 0;
5    return count + countVowels(str.substring(1));
6}
7
8// countVowels("hello") = 2 (e, o)

Remove Duplicates

Java

1public String removeDuplicates(String str) {
2    if (str.length() <= 1) return str;
3
4    if (str.charAt(0) == str.charAt(1)) {
5        return removeDuplicates(str.substring(1));
6    }
7    return str.charAt(0) + removeDuplicates(str.substring(1));
8}
9
10// removeDuplicates("aabbbcc") = "abc"

String Permutations

Generate all permutations of a string - a common interview problem:

Java

1public void permutations(String str, String prefix) {
2    if (str.isEmpty()) {
3        System.out.println(prefix);
4        return;
5    }
6
7    for (int i = 0; i < str.length(); i++) {
8        String rem = str.substring(0, i) + str.substring(i + 1);
9        permutations(rem, prefix + str.charAt(i));
10    }
11}
12
13// Usage: permutations("abc", "")
14// Output: abc, acb, bac, bca, cab, cba
15// Total: n! permutations

Check if Subsequence

Java

1public boolean isSubsequence(String s, String t) {
2    if (s.isEmpty()) return true;
3    if (t.isEmpty()) return false;
4
5    if (s.charAt(0) == t.charAt(0)) {
6        return isSubsequence(s.substring(1), t.substring(1));
7    }
8    return isSubsequence(s, t.substring(1));
9}
10
11// isSubsequence("ace", "abcde") = true
12// isSubsequence("aec", "abcde") = false

Practice Problems

1. Count occurrences of a character in a string
2. Replace all occurrences of a character
3. Generate all substrings of a string
4. Check if two strings are anagrams

Recursion with Arrays

Arrays can be processed recursively by treating them as a first element plus the rest of the array. This pattern is common in functional programming and divide-and-conquer algorithms.

Find First Occurrence

Java

1public int findFirst(int[] arr, int target, int index) {
2    if (index >= arr.length) return -1;
3    if (arr[index] == target) return index;
4    return findFirst(arr, target, index + 1);
5}
6
7// Usage: findFirst(arr, 5, 0)

Count Occurrences

Java

1public int countOccurrences(int[] arr, int target, int index) {
2    if (index >= arr.length) return 0;
3    int count = arr[index] == target ? 1 : 0;
4    return count + countOccurrences(arr, target, index + 1);
5}
6
7// countOccurrences([1,2,2,3,2], 2, 0) = 3

Check if Array is Sorted

Java

1public boolean isSorted(int[] arr, int index) {
2    if (index >= arr.length - 1) return true;
3    if (arr[index] > arr[index + 1]) return false;
4    return isSorted(arr, index + 1);
5}
6
7// isSorted([1, 2, 3, 4], 0) = true
8// isSorted([1, 3, 2, 4], 0) = false

Array Palindrome Check

Java

1public boolean isPalindrome(int[] arr, int left, int right) {
2    if (left >= right) return true;
3    if (arr[left] != arr[right]) return false;
4    return isPalindrome(arr, left + 1, right - 1);
5}
6
7// Usage: isPalindrome(arr, 0, arr.length - 1)

Binary Search

Classic divide-and-conquer algorithm with O(log n) time complexity:

Java

1public int binarySearch(int[] arr, int target, int left, int right) {
2    if (left > right) return -1;
3
4    int mid = left + (right - left) / 2;
5
6    if (arr[mid] == target) return mid;
7    if (arr[mid] > target) {
8        return binarySearch(arr, target, left, mid - 1);
9    }
10    return binarySearch(arr, target, mid + 1, right);
11}
12
13// Time: O(log n), Space: O(log n) for call stack

Merge Sort

A classic divide-and-conquer sorting algorithm:

Java

1public int[] mergeSort(int[] arr) {
2    if (arr.length <= 1) return arr;
3
4    int mid = arr.length / 2;
5    int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
6    int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
7
8    return merge(left, right);
9}
10
11private int[] merge(int[] left, int[] right) {
12    int[] result = new int[left.length + right.length];
13    int i = 0, j = 0, k = 0;
14
15    while (i < left.length && j < right.length) {
16        if (left[i] <= right[j]) {
17            result[k++] = left[i++];
18        } else {
19            result[k++] = right[j++];
20        }
21    }
22
23    while (i < left.length) result[k++] = left[i++];
24    while (j < right.length) result[k++] = right[j++];
25
26    return result;
27}
28
29// Time: O(n log n), Space: O(n)

Sum of Array

Java

1public int sum(int[] arr, int index) {
2    if (index >= arr.length) return 0;
3    return arr[index] + sum(arr, index + 1);
4}
5
6// sum([1, 2, 3, 4, 5], 0) = 15

Find Maximum

Java

1public int findMax(int[] arr, int index) {
2    if (index == arr.length - 1) return arr[index];
3    int maxRest = findMax(arr, index + 1);
4    return Math.max(arr[index], maxRest);
5}
6
7// findMax([3, 1, 4, 1, 5], 0) = 5

Practice Problems

1. Reverse an array in place using recursion
2. Find the second largest element
3. Rotate array by k positions
4. Implement Quick Sort recursively

Recursion with Data Structures

Data structures like linked lists, trees, and graphs are inherently recursive. A linked list is either empty or a node followed by another linked list. A tree is either empty or a node with subtrees as children.

Linked List Operations

Print List in Reverse

Java

1class ListNode {
2    int val;
3    ListNode next;
4    ListNode(int val) { this.val = val; }
5}
6
7public void printReverse(ListNode head) {
8    if (head == null) return;
9    printReverse(head.next);  // Recurse first
10    System.out.println(head.val);  // Then print
11}
12
13// List: 1 -> 2 -> 3 -> 4
14// Output: 4, 3, 2, 1

Sum of List Values

Java

1public int sumList(ListNode head) {
2    if (head == null) return 0;
3    return head.val + sumList(head.next);
4}

Search in List

Java

1public boolean search(ListNode head, int target) {
2    if (head == null) return false;
3    if (head.val == target) return true;
4    return search(head.next, target);
5}

Reverse Linked List

Java

1public ListNode reverse(ListNode head) {
2    if (head == null || head.next == null) {
3        return head;
4    }
5
6    ListNode newHead = reverse(head.next);
7    head.next.next = head;
8    head.next = null;
9
10    return newHead;
11}

Binary Search Tree Operations

Insert Value

Java

1class TreeNode {
2    int val;
3    TreeNode left, right;
4    TreeNode(int val) { this.val = val; }
5}
6
7public TreeNode insert(TreeNode root, int val) {
8    if (root == null) return new TreeNode(val);
9
10    if (val < root.val) {
11        root.left = insert(root.left, val);
12    } else {
13        root.right = insert(root.right, val);
14    }
15    return root;
16}

Tree Traversals

Java

1// Inorder: Left, Root, Right (sorted order for BST)
2public void inorder(TreeNode root) {
3    if (root == null) return;
4    inorder(root.left);
5    System.out.println(root.val);
6    inorder(root.right);
7}
8
9// Preorder: Root, Left, Right
10public void preorder(TreeNode root) {
11    if (root == null) return;
12    System.out.println(root.val);
13    preorder(root.left);
14    preorder(root.right);
15}
16
17// Postorder: Left, Right, Root
18public void postorder(TreeNode root) {
19    if (root == null) return;
20    postorder(root.left);
21    postorder(root.right);
22    System.out.println(root.val);
23}

Search in BST

Java

1public boolean search(TreeNode root, int target) {
2    if (root == null) return false;
3    if (root.val == target) return true;
4
5    if (target < root.val) {
6        return search(root.left, target);
7    }
8    return search(root.right, target);
9}
10
11// Time: O(h) where h is height of tree

Tree Height

Java

1public int height(TreeNode root) {
2    if (root == null) return 0;
3    int leftHeight = height(root.left);
4    int rightHeight = height(root.right);
5    return 1 + Math.max(leftHeight, rightHeight);
6}

Graph Traversals

Depth-First Search (DFS)

Java

1public void dfs(Map<Integer, List<Integer>> graph,
2                int node, Set<Integer> visited) {
3    if (visited.contains(node)) return;
4
5    visited.add(node);
6    System.out.println("Visiting: " + node);
7
8    for (int neighbor : graph.getOrDefault(node, List.of())) {
9        dfs(graph, neighbor, visited);
10    }
11}

Topological Sort

Java

1public void topologicalSort(Map<Integer, List<Integer>> graph,
2                             int node,
3                             Set<Integer> visited,
4                             Stack<Integer> stack) {
5    if (visited.contains(node)) return;
6    visited.add(node);
7
8    for (int neighbor : graph.getOrDefault(node, List.of())) {
9        topologicalSort(graph, neighbor, visited, stack);
10    }
11
12    stack.push(node);  // Add after all descendants
13}
14
15// Pop stack for topological order

Detect Cycle in Graph

Java

1public boolean hasCycle(Map<Integer, List<Integer>> graph,
2                        int node,
3                        Set<Integer> visited,
4                        Set<Integer> inStack) {
5    if (inStack.contains(node)) return true;  // Back edge found
6    if (visited.contains(node)) return false;
7
8    visited.add(node);
9    inStack.add(node);
10
11    for (int neighbor : graph.getOrDefault(node, List.of())) {
12        if (hasCycle(graph, neighbor, visited, inStack)) {
13            return true;
14        }
15    }
16
17    inStack.remove(node);
18    return false;
19}

Key Takeaways

Linked lists: Think of it as head + rest of list
Trees: Process current node, then recurse on children
Graphs: Track visited nodes to avoid infinite loops
Most tree/graph problems have elegant recursive solutions

🎉

You've completed this article!

Ready to explore more topics?

Browse More Articles

Tags:RecursionFundamentalsInterview Prep