Java Recursion Examples: Factorial, Fibonacci, and More

📚 Quick Study Guide

🔍 Recursion is a programming technique where a function calls itself within its own definition. 💡 A base case is essential to prevent infinite recursion. Without it, the function will call itself indefinitely, leading to a stack overflow error. 📝 The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. Formula: $n! = n * (n-1)!$ with base case $0! = 1$. ➕ 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. The sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. The formula: $F(n) = F(n-1) + F(n-2)$ with base cases $F(0) = 0$ and $F(1) = 1$. 🔄 Recursion can be less efficient than iteration (loops) due to the overhead of function calls, but it can provide elegant solutions for problems that are naturally recursive. 💾 Be mindful of stack space when using recursion, as each function call adds a new frame to the call stack. Deep recursion can lead to stack overflow errors. 💻 Tail recursion is a specific form where the recursive call is the last operation in the function. Some compilers can optimize tail recursion to avoid stack overflow, but Java does not automatically perform tail call optimization.

🧪 Practice Quiz

1. What is recursion?
   1. A type of loop.
   2. A function calling itself.
   3. A method for defining variables.
   4. A way to handle exceptions.
2. What is the base case in a recursive function?
   1. The starting value of a loop.
   2. The condition that stops the recursion.
   3. The function's return type.
   4. The initial call to the function.
3. What is the factorial of 5 (5!)?
   1. 5
   2. 10
   3. 24
   4. 120
4. What is the 6th number in the Fibonacci sequence (starting with 0, 1)?
   1. 3
   2. 5
   3. 8
   4. 13
5. Which of the following is a potential drawback of using recursion?
   1. It is always faster than iteration.
   2. It can lead to stack overflow errors.
   3. It uses less memory than iteration.
   4. It is easier to debug than iteration.
6. What happens if a recursive function does not have a base case?
   1. The program will crash.
   2. The function will return a default value.
   3. The function will call itself infinitely.
   4. The program will continue executing normally.
7. In the context of recursion, what is tail recursion?
   1. Recursion that occurs at the beginning of a function.
   2. Recursion where the recursive call is the last operation.
   3. Recursion used only for sorting algorithms.
   4. Recursion that avoids using a stack.