Week 2: Recursion & Data Processing

What You’ll Learn

• How recursion replaces loops
• Processing lists using pattern matching
• Writing functions with base case and recursive case
• Transforming and filtering data
• Thinking in terms of data flow instead of control flow

Concept

In imperative programming, iteration is usually done using loops:

let sum = 0
for (let i = 0; i < list.length; i++) {
  sum += list[i]
}

In functional programming, we use recursion instead of loops.

Recursion works by breaking a problem into:

• Base case → when to stop
• Recursive case → how to reduce the problem

Basic Recursion Example

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)

How it works:

sum([1,2,3])
= 1 + sum([2,3])
= 1 + 2 + sum([3])
= 1 + 2 + 3 + sum([])
= 6

Pattern Matching in Lists

[head | tail]

• head → first element
• tail → rest of the list

This is the foundation of recursive data processing.

Why This Matters in Real Systems

In real systems:

• Data often comes in streams or collections
• You need to process, transform, and filter it

Recursion helps by:

• making data flow explicit
• avoiding mutable state
• working naturally with immutable structures

In the BEAM ecosystem:

• processes handle data in small transformations
• recursion is optimized (tail-call optimization)
• large data can be processed safely without mutation

Examples

Example 1: Understanding Recursion Shape

defmodule RecursionDemo do
  def count_down(0), do: :done
  def count_down(n), do: count_down(n - 1)
end

IO.inspect(RecursionDemo.count_down(3))
# :done

# This example shows the core idea of recursion:
# - A **base case** (`0`) where recursion stops
# - A **recursive case** where the input is reduced

defmodule ListTraversal do
  def print_all([]), do: :ok
  def print_all([head | tail]) do
    IO.puts(head)
    print_all(tail)
  end
end
ListTraversal.print_all([1, 2, 3])
# 1
# 2
# 3
# This example teaches:
# - How `[head | tail]` is used to process lists
# - How recursion naturally replaces loops

Problems

Q1

Write a recursive function to calculate the length of a list.

Q2

Write a recursive function to sum only even numbers in a list.

Q3

Write a function that removes all nil values from a list.

Q4

Given a list of numbers, return a new list with only numbers greater than 10.

Q5

Rewrite this using recursion:

let result = []
for (let i = 0; i < list.length; i++) {
  if (list[i] > 0) {
    result.push(list[i])
  }
}

Solutions

def my_length([]), do: 0
def my_length([_ | tail]), do: 1 + my_length(tail)

def sum_even([]), do: 0

def sum_even([head | tail]) do
  if rem(head, 2) == 0 do
    head + sum_even(tail)
  else
    sum_even(tail)
  end
end

def remove_nil([]), do: []

def remove_nil([nil | tail]), do: remove_nil(tail)

def remove_nil([head | tail]), do: [head | remove_nil(tail)]

def greater_than_10([]), do: []

def greater_than_10([head | tail]) do
  if head > 10 do
    [head | greater_than_10(tail)]
  else
    greater_than_10(tail)
  end
end

def filter_positive([]), do: []

def filter_positive([head | tail]) do
  if head > 0 do
    [head | filter_positive(tail)]
  else
    filter_positive(tail)
  end
end

Summary

• Recursion replaces loops in functional programming
• Every recursive function needs a base case and a recursive case
• Lists are processed using pattern matching
• Data is transformed, not mutated
• These ideas scale directly to real-world data processing systems