Linear iteration and linear recursion

Although all loops in Scheme are done using recursion, the resulting code execution, can be quite different. Observe this peano arithmetic (only increment and decrement by one) addition, taken from the lesson 1b (Procedures and Processes; Substitution Model) of the MIT Lisp video tutorial page and modified for DrScheme (also see this tutorial on Google Video):

;; plus1 : number number -> number
;; add two numbers
;; by only using increments and decrements
;; example : (plus1 3 5) should produce 8
(define (plus1 x y)
  (if (= x 0)
      y
      (plus1 (dec x) (inc y))))
(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(plus1 3 5)

If we trace this (plus1 3 5), leaving out the uninteresting parts, we get this:

(plus1 3 5) |
(plus1 2 6) |
(plus1 1 7) | time = O(x)
(plus1 0 8) |
8           |
------------
space = O(1)

linear iteration : time = O(x), space = O(1)

The time it takes to run the code is proportional to the value of x, in other words, ordinal to x (O(x)). The amount of memory storage it takes to execute this code, the space, is constant, or ordinal to 1 (O(1)). This is the hallmark of a linear iteration.

If we modify the code of plus1, so it delays the addition of y until the end of the execution, we get something like this:

;; plus2 : number number -> number
;; add two numbers
;; by only using increments and decrements
;; example : (plus2 3 5) should produce 8
(define (plus2 x y)
  (if (= x 0)
      y
      (inc (plus2 (dec x) y))))
(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(plus2 3 5)

If we trace (plus2 3 5) as before, we get this:

(plus2 3 5)                   |
(inc (plus2 2 5))             |
(inc (inc (plus2 1 5)))       |
(inc (inc (inc (plus2 0 5)))) | time = O(x)
(inc (inc (inc 5)))           |
(inc (inc 6))                 |
(inc 7)                       |
8                             |
------------------------------
space = O(x)

linear recursion : time = O(x), space = O(x)

Again, the number of steps is proportional to the value of x (that there are twice as many steps doesn't matter at this point). However, the amount of space isn't constant, but proportional to value of x. This is the hallmark of a linear recursion.

Although both methods plus1 and plus2 use the same recursive looping technique, the resulting code execution (process) is quite different.

There are two other interesting problems discussed in this video tutorial lesson, Fibonacci numbers and the Towers of Hanoi. These can be expressed both as a recursive and an iterative process. I will discuss both problems in separate posts, once I've digested the concepts of this video tutorial.