Recursion is a programming method where a function calls itself until it solves a problem by breaking it down into smaller instances of the same problem.

Imagine you have a set of nesting dolls. Each doll can have a smaller doll inside. Recursion is like when you open a doll, and you find another doll inside, and then you open that one to find an even tinier doll inside, and so on until you find the tiniest doll.

Use Cases and Real-Life Examples

• Russian nesting dolls

• Infinite Mirrors

• Fibonacci sequence

• Traversing tree data structures

Base Case

recursiveFunction(parameter) {
    if condition is met:  // The base case. If something special happens
        return special_value

    call recursiveFunction(parameter altered or new value)  // Otherwise, keep trying with a slightly changed value
}

The base case is important because if you just keep calling the function over and over again, you're not going to solve anything. You're going to get a stack overflow exception. You need to know what the base case is so that you can finally solve the problem and stop the function.

Using Recursion to Solve Fibonacci Number - Leetcode Problem

Fibonacci Number(easy)

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. So, the sequence goes like this:

0 + 1 = 1; 1 + 1 = 2; 2 + 1 = 3; 3 + 2 = 5; 5 + 3 = 8; 8 + 5 = 13, ...

 public int fib(int n) {
       if(n == 0 || n == 1) return n; //base case

        return fib(n-1) + fib(n-2); //recursion    
    }
}

Using Recursion for Binary Tree Inorder Traversal

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();

        inorder(ans, root);
        return ans;
    }

    public void inorder(List<Integer> ans, TreeNode root) {
       if(root == null) return; //base case

       inorder(ans, root.left); //recursion
       ans.add(root.val);
       inorder(ans, root.right); //recursion
    }

Leetcode Problems that Use Recursion

• Power of Two(easy)

• Reverse String (easy)

• Binary Tree Inorder Traversal (easy)

• Generate Parentheses(medium)

• Palindrome Partitioning(medium)

• N-Queens(Hard)

And that concludes this article. What are some problems you have solved or are trying to solve that require recursion? Can you think of any other real-life use cases and examples that use recursion?