Peano Arithmetic
Two ways to add whole numbers:
1: iteration process
(define (+ x y)
(if (= x 0)
y
(+ (-1+ x) (1+ y))))
(+ 3 4)
(+ 2 5)
(+ 1 6)
(+ 0 7)
7
time = O(x)
space = O(1)
called "Iteration"
2: recursive process
(define (+ x y)
(if (= x 0)
y
(1+ (+ (-1+ x) y))))
(+ 3 4)
(1+ (+ 2 4))
(1+ (1+ (+ 1 4)))
(1+ (1+ (1+ (+ 0 4))))
(1+ (1+ (1+ 4)))
(1+ (1+ 5))
(1+ 6)
7
time = O(x)
space = O(x)
called "Linear Recursion"