Functional Programming

Overview of Problem Solving Approaches

  • Introduction to recursive problem-solving concepts.

  • Comparison between recursion and iterative solutions.

Questions Raised by Students

  • Students questioned the necessity of recursion:

    • "Why not just use a loop to process each element sequentially?"

Situations Where Iteration Suffices

  • Simple problems can be addressed iteratively:

    • Examples:

    • Finding the sum of all elements in a list.

    • Squaring all elements in a list and storing them in a new list.

  • Aim of the lecture is not simply to show recursion for these problems, but to instill a broader algorithmic mindset for solving various problems.

Understanding Recursion for Problem Solving

  • Goal: Provide students with a structured approach to tackle new programming problems.

  • Key Principle: Break down a problem into smaller, more manageable elements.

  • Recursive Design Algorithm:

    1. Base Case: Identify a simple case where a solution can be given immediately.

    2. Recursive Case: If the problem is more complex, reduce the problem size and call the function recursively.

    3. Dealing with the Remainder: After solving the smaller problem, integrate that solution with the leftover parts to form the final answer.

  • Benefits of Recursion:

    • Reliability: Following this structured method will always yield a solution.

    • Code Compatibility: Recursive solutions can always be translated into code.

Importance of Recursive Solutions

  • Recursive approaches are particularly beneficial for complex problems where straightforward solutions are not evident.

  • Encourages a different mindset that helps tackle problems beyond simple iteration.

Use of Scheme Language in Recursion

  • Scheme is chosen for its structure, which aligns well with recursive problem-solving methods.

  • Procedures in Scheme follow a natural recursive pattern, enhancing clarity and understanding.

Recursive Problem Solving Steps in Scheme

  1. Check for Base Case: Is there an obvious solution? If yes, return the answer.

  2. Identify Alternative Simple Cases: If not, check for different simple cases and provide answers for those as well.

  3. Decompose the Problem:

    • Is the current case complicated? If yes, call the function on a smaller segment of the problem.

  4. Handle the Leftover Elements: Combine results from the base case solution and recursive solutions to derive the final answer.

Example Recursive Function: Finding Maximum in a List

  • Task: Write a function to find the maximum number in a list recursively.

Recursive Steps:

  1. Base Case: If the list has one element, return that element as the maximum.

  2. Recursive Case: Compare the first element with the maximum of the rest of the list.

    • If the first element is higher, return it as the maximum.

    • If it is not, return the maximum from the recursive call.

Pseudocode Illustration:

(define (max-list l)
  (if (null? (cdr l))
      (car l)
      (if (> (car l) (max-list (cdr l)))
          (car l)
          (max-list (cdr l)))))

Example of More Complex Problem: Finding Subsets of a List that Add Up to a Given Number

  • Task: Given a list of numbers and a target sum (n), return all subsets of the list that sum to n.

Steps:

  1. Base Case: If the list is empty, return an empty set.

  2. Recursive Case: Given a non-empty list:

    • Form subsets that do not include the first element.

    • Form subsets that include the first element and check if those subsets can sum to the target value by adjusting the target.

Pseudocode Illustration:

(define (sum-to-n l n)
  (if (null? l)
      (if (zero? n)
          '(())
          '())
      (let* ((first (car l))
             (without-first (sum-to-n (cdr l) n))
             (with-first (map (lambda (subset) (cons first subset))
                                (sum-to-n (cdr l) (- n first)))))
        (append without-first with-first))))

Final Summary

  • Recursion offers a powerful way to solve problems that may be difficult to tackle using iterative methods.

  • Following the structured recursive process can handle even complex tasks reliably, while ensuring the code remains clear and maintainable.

  • Encouragement for continued practice with both simple and complex recursive functions for mastery and confidence.

  • Mathematical foundation provided by proof by induction enhances understanding and certainty in recursive solutions.