Unit 10: Recursion

Overview of Recursion

• Definition: Recursion is defining an operation in terms of itself, solving a problem by solving smaller parts of the same problem.
• Recursive Programming: Writing methods that call themselves to solve problems.
  • Can replace iteration (loops) in some cases.
  • Suitable for specific types of problems.

Why Learn Recursion?

• Cultural Experience: Offers a different approach to problem-solving.
• Advantages:
  • Solves certain problems more efficiently than iteration.
  • Leads to elegant, simplistic, and short code when properly used.
• Functional Languages: Languages like Scheme, ML, and Haskell use recursion exclusively.

Components of Recursive Algorithms

• Base Case: A simple occurrence that can be solved directly.
• Recursive Case: A complex occurrence that cannot be solved directly but can be described in terms of smaller problems.
• Identifying base and recursive cases is crucial.

Example: Finding Position in a Line

• Scenario: Determining your position in a line without leaving it.
  • Base Case: Person at the front returns position 1.
  • Recursive Case: Each person asks the one in front of them, reducing the problem by one person each time.

Recursion in Java

• Recursive Method Example: Converting a loop-based method to a recursive one.
  • Example provided for printing stars without using loops.

Recursion Zen

• The art of identifying the best set of cases for a recursive algorithm.

Exercises

• Recursive Method pow: Calculates the power of a base number using recursion, not loops.

Recursive Traces and Tree Diagrams

• Method Mystery Example 1: Recursively simplifies numbers until a base case is reached.
• Method Mystery Example 2: Demonstrates subtraction in recursion.
• Method Mystery Example 3: Uses recursion to build complex results from base values.

Recursive Binary Search

• AP Exam Example: Understand the recursive implementation of binary search.

Merge Sort

• Algorithm:
  • Splits data in halves, sorts each half, and merges them.
  • Recursive implementation.
  • Example of a "divide and conquer" strategy.
• Merge Sort Example: Step-by-step breakdown of sorting an array.

Code Examples

• Merge Half Code: Details on merging sorted halves.
• Merge Sort Code: Recursive method for sorting using merge sort.

Complexity Analysis

• Selection Sort: Big-Oh notation discussed.
• Merge Sort: Big-Oh notation discussed.

Labs

• Lab 1: Fractal Circles: Write a recursive method in Processing to create a fractal circle pattern.
• Lab 2: Sierpinski Triangle: Write a recursive method to draw the Sierpinski triangle using Processing.