Key Takeaways

Recursion Theory: Provides a mathematical foundation for understanding when a recursive function is well-founded and will terminate. It closely relates to mathematical induction and can be applied beyond natural numbers to various types with well-ordering.

Summary: Recursion Theory

Relationship to Mathematical Induction

• Induction(귀납): Proves that a proposition holds for all natural numbers by:
  • Proving the base case (e.g., p(0)).
  • Proving the inductive case (e.g., if p(n) holds, then p(n+1) holds).
• Recursion: Similar to induction, it includes:
  • A base case to stop recursion.
  • A recursive case that progresses towards the base case.

Example: Factorial Function

• Factorial Recursion:

  int factorial(int n) {
    if (n <= 0) {
      return 1;  // Base case
    }
    return n * factorial(n - 1);  // Recursive case
  }
  

• Induction Proof: To prove the correctness of the factorial function, use induction:

  • Base Case: factorial(0) = 1.
  • Inductive Step: Assume factorial(k) is correct, then factorial(k+1) = (k+1) * factorial(k).

Generalizing Beyond Natural Numbers

• Well-Ordering: Any set with a well-ordering (total order where every subset has a least element) can be used for recursion.
• Example: Fibonacci sequence can be defined recursively using a different ordering for all integers.
  • Order: 0 ⊑ 1 ⊑ -1 ⊑ 2 ⊑ -2 ⊑ 3 ⊑ -3 ...
  • Use this order to prove correctness by induction.

Recursion on Data Structures

• Lists and Trees: Many data structures are recursively defined and can be operated on using recursion.
  • Lists: Measure by length.
  • Trees: Measure by height.

Guaranteeing Termination

• Well-Ordering and Measures: Ensure recursion terminates by showing each recursive call operates on a "smaller" value according to a well-ordering.
• Measure Function: Maps parameter values to naturals or ordinals to show the measure decreases with every recursive call.
  • Example: For lists, use their length as the measure.

Practical Implications

• Avoiding Infinite Recursion: Ensure every recursive function has a well-defined base case and recursive case progressing towards it.
• Measure and Convince: For most tasks, a formal proof is unnecessary, but understanding the measure helps prevent infinite recursion.