Recursion

The recursion recipe: handle the base case (empty list, zero), then reduce the problem (cdr down the list, decrement n) and combine.

Recursive vs iterative processes (SICP): factorial builds deferred multiplications (stack grows); fact-iter carries state in arguments, and with tail-call optimization (guaranteed in Scheme) it runs in constant space.

;; Factorial
(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

;; Sum a list
(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst) (sum (cdr lst)))))

;; Map, written by hand
(define (my-map f lst)
  (if (null? lst)
      '()
      (cons (f (car lst)) (my-map f (cdr lst)))))

;; Filter
(define (my-filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst)) (cons (car lst) (my-filter pred (cdr lst))))
        (else (my-filter pred (cdr lst)))))

;; Flatten a tree
(define (flatten t)
  (cond ((null? t) '())
        ((pair? t) (append (flatten (car t)) (flatten (cdr t))))
        (else (list t))))
(flatten '(1 (2 (3 4)) 5))                ; (1 2 3 4 5)

;; Fibonacci (tree recursion)
(define (fib n)
  (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))

;; Tail-recursive (iterative process) version with an accumulator
(define (fact-iter n)
  (let loop ((i n) (acc 1))               ; named let
    (if (= i 0)
        acc
        (loop (- i 1) (* acc i)))))