Unit 8: Recursion Flashcards
What is recursion in programming?
A technique where a method calls itself to solve a smaller version of the same problem.
What is the recursive solution to “how many people are behind me in a column”?
Ask the person behind you how many are behind them. If none, return 0; else, return their answer + 1.
What are the two essential components of any recursive algorithm?
Base case – a simple condition that stops the recursion.
Recursive case – breaks the problem into smaller subproblems.
Why is recursion useful?
Provides elegant, simple solutions
Can solve problems better than iteration
What does getArea(4) return using recursion?
getArea(1) → 1
getArea(2) → 1 + 2 = 3
getArea(3) → 3 + 3 = 6
getArea(4) → 6 + 4 = 10
What is the recursive formula for Fibonacci numbers?
public static long fib(int n) {
if (n <= 2) return 1;
else return fib(n - 1) + fib(n - 2);
}
Why is the recursive Fibonacci function inefficient?
it recalculates the same values multiple times (e.g., fib(3) is called 3 times in fib(6)).
What are the main differences between loops and recursion?
Loops use repetition explicitly
Recursion uses repeated method calls
What happens in memory during recursion?
Each call gets its own local variables and parameters. Memory is freed when the method returns.
What is infinite recursion and why is it bad?
It’s when no base case is met, leading to endless method calls and eventual stack overflow.
When should recursion be avoided?
When performance is critical or the problem is easily solved iteratively.
