Rucete ✏ AP Computer Science A In a Nutshell
7. Recursion
This chapter introduces the concept of recursion, including recursive methods, writing and analyzing recursion, recursive helper methods, recursion in two-dimensional grids, and sample recursive problems.
Recursive Methods
• A recursive method is one that calls itself to solve a smaller version of the original problem.
• The AP exam requires understanding and tracing recursive methods, but not writing them from scratch.
• Example: stackWords() reads words and prints them in reverse order using recursion and a call stack.
General Form of Recursive Methods
• Every recursive method must have:
• Base case: Condition that ends the recursion (e.g., reaching 0 or finding a key).
• Recursive case: Moves the process closer to the base case.
• Example of tail recursion: drawLine(n) prints stars and ends with no pending statements.
Writing Recursive Methods
• Frame the process recursively by expressing it in terms of a smaller version of itself.
• Example 1: Calculating factorial n! where factorial(n) = n * factorial(n-1).
• Example 2: Reversing digits with revDigs by outputting the last digit and recursively processing the rest.
Analysis of Recursive Methods
• Recursive methods like Fibonacci can be highly inefficient because of repeated calculations (exponential growth).
• Recursive solutions are elegant but may incur extra memory and run time overhead.
• Iterative versions are often more efficient for simple tasks like factorial or Fibonacci numbers.
Guidelines for Using Recursion
• Use recursion when it significantly simplifies code.
• Avoid recursion for simple iterative processes (e.g., linear search, simple sums).
• Recursion is ideal for branching processes (tree traversal) and divide-and-conquer algorithms (e.g., merge sort).
Recursive Helper Methods
• A helper method is a private recursive method used inside a public method to simplify parameter management.
• Public methods often start recursion with default parameters, while private helpers perform the recursive work.
• Example: A public reverseString(String s) method may call a private reverseStringHelper(String s, int index).
Recursion in Two-Dimensional Grids
• Recursion can solve problems involving 2D arrays, such as "flood fill" or "blob erasure."
• Key techniques:
• Base case: Check if indices are out of bounds or cell value is not the target.
• Recursive case: Change the current cell and recursively move in four directions (up, down, left, right).
Common 2D Recursive Problems
• Counting connected regions (e.g., number of islands in a grid).
• Changing connected cells (e.g., converting all connected 1’s to 0’s).
• Tracing paths through mazes.
Example of 2D Recursion
• countCells(x, y): Counts the number of 'on' cells connected to a given (x, y) position in a boolean grid.
• Base case: Return 0 if (x, y) is out of bounds or not 'on.'
• Recursive case: Turn the cell 'off' and recursively explore adjacent cells.
Sample Free-Response Question: Fractal Pattern
• Recursion naturally fits problems involving fractals or self-repeating patterns.
• Example: Drawing nested squares or shrinking triangles through recursive drawing calls.
Tracing Recursive Calls
• Carefully track the call stack: each call adds a new frame to the stack and suspends the previous call.
• Understand order of operations and unwinding of the stack after reaching the base case.
Common Mistakes in Recursion
• Forgetting to include a base case, leading to infinite recursion.
• Incorrectly moving toward the base case, causing stack overflow errors.
• Not properly handling all directions in grid-based recursion.
In a Nutshell
Recursion is a powerful programming technique where a method solves a problem by calling itself on smaller inputs. While recursive methods can simplify solutions to complex problems, careful attention must be given to defining base cases and ensuring progress toward them. In 2D arrays, recursion enables elegant solutions to connected-component problems. Mastery of recursion enhances problem-solving skills in both simple and advanced programming challenges.