Recursion vs Iteration: When to Use Each and Why It Matters

public class CountdownComparison {

    // ITERATIVE approach — one stack frame, counter decrements in a loop
    public static void countdownIterative(int startNumber) {
        System.out.println("--- Iterative Countdown ---");
        // The same 'current' variable is reused each iteration — no new memory allocated
        for (int current = startNumber; current >= 1; current--) {
            System.out.println(current);
        }
        System.out.println("Blast off! (iterative)");
    }

    // RECURSIVE approach — each call gets its own stack frame with its own 'current'
    public static void countdownRecursive(int current) {
        // BASE CASE: when we reach zero, stop calling ourselves
        // Without this, the function would call itself forever → StackOverflowError
        if (current < 1) {
            System.out.println("Blast off! (recursive)");
            return;
        }

        System.out.println(current);

        // RECURSIVE CASE: solve a smaller version of the same problem
        // We trust that countdownRecursive(current - 1) will handle the rest
        countdownRecursive(current - 1);
    }

    public static void main(String[] args) {
        countdownIterative(5);
        System.out.println();

        System.out.println("--- Recursive Countdown ---");
        countdownRecursive(5);
    }
}

public class BinaryTreeInOrder {

    // A single node in the binary search tree
    static class TreeNode {
        int value;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int value) {
            this.value = value;
        }
    }

    // In-order traversal: left subtree → current node → right subtree
    // This visits nodes in ascending order for a valid BST
    public static void traverseInOrder(TreeNode currentNode) {
        // BASE CASE: if this node doesn't exist, there's nothing to visit
        if (currentNode == null) {
            return;
        }

        // Go as far left as possible first (smaller values)
        traverseInOrder(currentNode.leftChild);

        // Print this node's value — we're at the 'bottom' of the left dive
        System.out.print(currentNode.value + " ");

        // Now handle everything to the right (larger values)
        traverseInOrder(currentNode.rightChild);
    }

    public static void main(String[] args) {
        // Build a small BST manually:
        //        4
        //       / \
        //      2   6
        //     / \ / \
        //    1  3 5  7

        TreeNode root = new TreeNode(4);
        root.leftChild = new TreeNode(2);
        root.rightChild = new TreeNode(6);
        root.leftChild.leftChild = new TreeNode(1);
        root.leftChild.rightChild = new TreeNode(3);
        root.rightChild.leftChild = new TreeNode(5);
        root.rightChild.rightChild = new TreeNode(7);

        System.out.print("In-order traversal: ");
        traverseInOrder(root);
        System.out.println();

        // Compare: what would iterative look like?
        // You'd need an explicit Stack<TreeNode> and a while loop — 20+ lines
        // to produce the exact same output. Recursion wins on clarity here.
    }
}

import java.util.HashMap;
import java.util.Map;

public class FibonacciComparison {

    // NAIVE RECURSIVE — O(2^n) time. Catastrophically slow for large n.
    // fib(50) would take minutes. fib(100) would outlive the universe.
    public static long fibNaive(int position) {
        if (position <= 1) return position; // base cases: fib(0)=0, fib(1)=1
        return fibNaive(position - 1) + fibNaive(position - 2); // overlapping subproblems!
    }

    // MEMOISED RECURSIVE — O(n) time. Each position calculated exactly once.
    // The cache stores results so we never redo work.
    private static Map<Integer, Long> memo = new HashMap<>();

    public static long fibMemoised(int position) {
        if (position <= 1) return position;

        // Check cache before doing any work
        if (memo.containsKey(position)) {
            return memo.get(position); // already computed — return instantly
        }

        long result = fibMemoised(position - 1) + fibMemoised(position - 2);
        memo.put(position, result); // store result before returning
        return result;
    }

    // ITERATIVE — O(n) time, O(1) space. No stack growth. The pragmatic choice.
    public static long fibIterative(int position) {
        if (position <= 1) return position;

        long previous = 0;  // represents fib(n-2)
        long current = 1;   // represents fib(n-1)

        // Walk forward from position 2, building up the answer
        for (int step = 2; step <= position; step++) {
            long next = previous + current; // fib(n) = fib(n-1) + fib(n-2)
            previous = current;             // slide the window forward
            current = next;
        }
        return current;
    }

    public static void main(String[] args) {
        int target = 45;

        // Naive is dangerously slow — only safe for very small numbers
        long naiveStart = System.currentTimeMillis();
        System.out.println("Naive fib(" + target + ")     = " + fibNaive(target));
        System.out.println("Naive time: " + (System.currentTimeMillis() - naiveStart) + "ms");

        long memoisedStart = System.currentTimeMillis();
        System.out.println("Memoised fib(" + target + ")  = " + fibMemoised(target));
        System.out.println("Memoised time: " + (System.currentTimeMillis() - memoisedStart) + "ms");

        long iterativeStart = System.currentTimeMillis();
        System.out.println("Iterative fib(" + target + ") = " + fibIterative(target));
        System.out.println("Iterative time: " + (System.currentTimeMillis() - iterativeStart) + "ms");
    }
}