Recursion Lecture Notes

Introduction

• Delivered by Stanford Center for Professional Development
• Focus on understanding recursion through vocabulary and examples.

Key Concepts of Recursion

• Definition: A recursive function calls itself to solve a problem.
• Recursive problems exhibit self-similarity (e.g., surveying different parts of a campus is similar to the overall survey problem).
• Base Case: The simplest form of a problem that can be solved directly without further recursion.
• Recursive Case: Reduces the problem into smaller instances of the same problem.

Structure of Recursive Functions

• All recursive code generally follows a two-case structure:
  • Base Case: Stops recursion and returns a result.
  • Recursive Cases: Make recursive calls to break down the problem further.

Functional Recursion

• Involves functions that return non-void results (e.g., integers, strings).
• Combines results from recursive calls to formulate the final answer.

Examples of Recursive Functions

1. Raising a Number to a Power
   • Iterative method: Multiply the base repeatedly.
   • Recursive method: Compute power by calling itself with a reduced exponent.
     • Base case: if exponent is 0, return 1.
     • Recursive case: return base * power(base, exponent - 1).
2. Debugging Recursion
   • Common mistake: Not making progress towards the base case, leading to infinite recursion and stack overflow errors.
3. More Efficient Recursive Strategy
   • For odd/even exponents: Compute half the exponent and square it.
   • Example: power(base, exponent) for odd uses two recursive calls on half the exponent.

Efficiency of Recursion

• Recursion does not guarantee efficiency; it can be as efficient as iteration depending on the problem.
• For problems with simple iterative solutions, iterative methods may be preferred.
• Recursion shines in more complex problems where it simplifies coding and logic (e.g., tree traversals, combinatorial problems).

Palindrome Check

• A palindrome reads the same forwards and backwards.
• Recursive approach:
  • Base cases: 0 or 1-character strings are palindromes.
  • Recursive case: Check outer characters and call the function on the inner substring.

Searching Algorithms

1. Linear Search: Sequentially checks each element in an array.
2. Binary Search:
   • Requires sorted data.
   • Divide and conquer: Compare the target value to the middle element and eliminate half the search space.
   • Base case: No elements left to search or a single element left to check.

Combinatorial Problems

• Choosing combinations (e.g., choosing 4 people from N).
• Recursive formulation:
  • Include/exclude a specific item and calculate combinations accordingly.
  • Base case: If K is 0 (selecting none from N) or K equals N (selecting all).

Conclusion

• Recursion is a powerful concept for solving many types of problems in programming.
• Understanding and practicing recursive techniques is critical for developing efficient algorithms.

---

Note

• Continuous examples and practice will deepen understanding of recursion patterns.