Chapter 12 Flashcards
(19 cards)
What is recursion in programming?
Recursion is a technique where a method calls itself to solve a smaller instance of the same problem, with a base case to stop the calls.
What is a recursive definition?
It’s a definition that uses itself in the explanation, like defining a list as a number or a number followed by another list.
What is the base case and recursive case in recursion?
Base case stops recursion with a known answer. Recursive case reduces the problem and calls the function again.
How do you think recursively?
Break the problem into smaller instances of the same problem until you reach a trivial case.
How is sum from 1 to n computed recursively?
sum(n) = n + sum(n-1), with base case sum(1) = 1.
Can a recursive function using if-else?
Yes, it uses conditionals. An if-statement checks the base case and returns; the else is implied by code following the if.
How does recursion compare to iteration?
Iteration builds from bottom up using loops; recursion breaks down the problem top-down with stack frames.
What is the call stack in recursion?
Each function call adds a new stack frame. The program unwinds them once a base case is reached.
What causes a stack overflow in recursion?
Infinite recursion without a base case leads to memory overflow due to unending stack frames.
How does recursion solve Towers of Hanoi?
Move n-1 disks to auxiliary peg, move largest to destination, then move n-1 disks from auxiliary to destination.
How is factorial defined recursively?
n! = n * (n-1)!, with base case 1! = 1.
When is recursion preferred over iteration?
When the problem has a naturally recursive structure like trees or divide-and-conquer algorithms.
What are flowcharts and pseudocode used for?
To plan algorithms with diagrams and plain English before writing actual code.
How can a list like [24, 88, 40, 37] be defined recursively?
By expressing it as a number followed by a comma and another list, repeatedly, until the last element becomes the base case.
Why might recursion be less efficient than iteration?
Each recursive call adds a new stack frame, increasing memory usage and method call overhead.
When should you avoid recursion?
Avoid recursion when an iterative approach is clearer, faster, or when the recursion doesn’t simplify the problem.
What is recursive tracing?
It means tracking each recursive call and return to understand how inputs shrink and outputs build back up.
What are the parts of a recursive Java method?
A base case that ends recursion and a recursive case that reduces the input and calls the method again.
How does recursion differ from iteration in memory usage?
Recursion consumes stack space for each call; iteration typically uses a single frame.
