12. Recursion

Recursion is a fundamental technique in functional programming where a function calls itself to solve a problem by breaking it down into smaller subproblems.

A recursive function typically has two parts:

1. Base case: the condition that stops the recursion.
2. Recursive case: the call to itself with a smaller problem.

A simple example, computing the factorial of a number:

(defun factorial (n)
  (if (<= n 1)
      1                          ; Base case
      (* n (factorial (- n 1))))) ; Recursive case

* (factorial 5)
120

* (factorial 0)
1

Let's see how it works step by step:

(factorial 5)
→ (* 5 (factorial 4))
→ (* 5 (* 4 (factorial 3)))
→ (* 5 (* 4 (* 3 (factorial 2))))
→ (* 5 (* 4 (* 3 (* 2 (factorial 1)))))
→ (* 5 (* 4 (* 3 (* 2 1))))
→ (* 5 (* 4 (* 3 2)))
→ (* 5 (* 4 6))
→ (* 5 24)
→ 120

Another example, adding all the numbers in a list:

(defun sumar-lista (lst)
  (if (null lst)
      0                                    ; Base case: empty list
      (+ (car lst) (sumar-lista (cdr lst))))) ; Recursive case

* (sumar-lista '(1 2 3 4 5))
15

The flow would be:

(sumar-lista '(1 2 3 4 5))
→ (+ 1 (sumar-lista '(2 3 4 5)))
→ (+ 1 (+ 2 (sumar-lista '(3 4 5))))
→ (+ 1 (+ 2 (+ 3 (sumar-lista '(4 5)))))
→ (+ 1 (+ 2 (+ 3 (+ 4 (sumar-lista '(5))))))
→ (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (sumar-lista '()))))))
→ (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))
→ (+ 1 (+ 2 (+ 3 (+ 4 5))))
→ (+ 1 (+ 2 (+ 3 9)))
→ (+ 1 (+ 2 12))
→ (+ 1 14)
→ 15

Key points for writing recursive functions:

1. Identify the base case: when should the recursion stop? Usually when the list is empty (null), a number reaches zero, etc.

2. Define the recursive case: how do you reduce the problem? Typically by processing the first element (car) and calling recursively with the rest (cdr).

3. Make sure you advance toward the base case: each recursive call must get closer to the base case, or you will have infinite recursion.

Example of counting elements in a list:

(defun contar (lst)
  (if (null lst)
      0
      (+ 1 (contar (cdr lst)))))

* (contar '(a b c d e))
5

Recursion can be more elegant than iterative loops, especially when you work with recursive structures such as lists or trees. In later lessons we will look at optimizations such as tail recursion.