🔁 This lecture introduces recursion — methods that call themselves. It covers the concept, base cases, termination, recursive tree search, factorial, and the Fibonacci pitfall that demonstrates when recursion becomes dangerously inefficient.

At-a-glance Checklist

• [ ] Define recursion: a method that calls itself on a modified argument
• [ ] Understand the two essential parts: base case and recursive case
• [ ] Know why recursion must make progress toward the base case (termination)
• [ ] Trace through a simple recursive function (foo) by hand
• [ ] Understand recursion vs iteration — pros and cons in Java
• [ ] Know how binary trees work: root, children, leaves, complete tree
• [ ] Implement and trace containsNegative() on a binary tree
• [ ] Understand short-circuit evaluation (||) and how it affects recursive tree traversal
• [ ] Implement and trace recursive factorial(n)
• [ ] Understand the Fibonacci problem — why naive recursion causes exponential blowup
• [ ] Write the efficient iterative (for-loop) Fibonacci solution using a sliding window
• [ ] Connect recursion to the JVM stack: each recursive call = new frame

What Is Recursion?

Recursion = defining a method through calling itself.

• A recursive method calls itself on a different (smaller) argument
• A recursive data structure is defined in terms of itself (e.g., a linked list)

Two Essential Parts

Every recursive method needs: