Introduction to Recursion

Welcome back! So far, you've learned about higher-order functions, immutability, and list processing. These concepts are fundamental in functional programming. Taking a step further into this realm, we'll now explore recursion. Recursion allows a function to call itself, making it a powerful tool for solving problems that can be broken down into smaller, repetitive tasks.

In this unit, you'll get to grips with recursion, a core concept in Elixir and functional programming. Recursive functions are those that call themselves until a base condition is met. This helps you solve problems that involve repetitive or nested tasks without using traditional loops.

Consider the following example where we want to sum all the elements in a list:

defmodule Math do
  def sum_list([head | tail], acc) do
    sum_list(tail, acc + head)
  end

  def sum_list([], acc) do
    acc
  end
end

list = [1, 2, 3, 4]
IO.puts(Math.sum_list(list, 0))

In this code, Math.sum_list is a recursive function. It adds the head of the list to acc and recursively processes the tail of the list. When the list is empty ([]), it returns the accumulated sum.

The pattern [head | tail] is used in Elixir to destructure a list into its components. Here, head represents the first element of the list, and tail is a list containing all the subsequent elements. This pattern is crucial in recursion as it allows us to process each element of the list iteratively. The | is an operator (cons operator) used in list pattern matching to separate the head from the tail. This is particularly useful in recursion when you want to process each element of a list one by one.

Let's break down the recursive function Math.sum_list to understand how it works:

1. Input: The function takes two arguments: a list [head | tail] and an accumulator acc with values [1, 2, 3, 4] and 0, respectively.
2. Base Case: The function pattern-matches the list [head | tail]. If the list is empty, it returns the accumulator acc.
3. Recursive Call: If the list is not empty, the function adds the head of the list to the accumulator and calls itself with the tail of the list (remaining elements) and the updated accumulator.

Let's go through the recursive calls step by step:

• Step 1: sum_list([1, 2, 3, 4], 0): head = 1, tail = [2, 3, 4], acc = 0
• Step 2: sum_list([2, 3, 4], 1): head = 2, tail = [3, 4], acc = 1
• Step 3: sum_list([3, 4], 3): head = 3, tail = [4], acc = 3
• Step 4: sum_list([4], 6): head = 4, tail = [], acc = 6
• S tep 5: sum_list([], 10): returns 10

The function Math.sum_list recursively processes each element of the list, adding it to the accumulator until the base case is reached. This iterative process allows you to sum all the elements in the list without using loops.