An Introduction to Linear Recursive & Linear Iterative Processes in Programming
Using the Scheme dialect of Lisp
(Hi! If you value the content I write, I would appreciate so much if you considered becoming a member of Medium through my referral link. Now on to what you came here for…)
For the last several weeks I’ve been very slowly working my way through the first chapter of Structure and Interpretation of Computer Programs (Abelson/Sussman). When I first started studying programming people would ask me whether I liked front-end or back-end development. I’d respond without a clue, “Front-end,” only because I liked JavaScript more than Ruby — the only two languages I had studied till that point — and I liked the visual aspect that front-end languages afforded. It was eye candy, and the immediate satisfaction of manipulating things on my screen.
As I’ve been reading through this book, though, I’ve become more aware of how little I actually understand about programming (understatement), and how much I love about the mechanics of it. It’s a similar feeling to the thrill I used to get from studying music theory. (*crickets*)
One thing that’s recently been starting to make more sense is the difference between linear recursive and linear iterative processes. The idea that depending on how a procedure is written, it could use more of your computer’s resources in time and space.
To illustrate this, let’s look at a simplified version of Exercise 1.11 from SICP:
A function f is defined by the rule that f(n) = n if n < 3 and f(n) = f(n - 1) + 2 if n ≥ 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
What’s the difference between a linear recursive process and a linear iterative process?
Let’s break it down by writing the above function in the Scheme dialect of Lisp:
(define (f n)
(if (< n 3)
n
(+ 2 (f (- n 1)))))Note: in Scheme, the operator is placed to the left of the operands. So (- n 1) means “n minus 1.”
In English:
Define a function named n to return the value of n, if n is less than 3. If n is greater than three, then calculate the value of f(n - 1) + 2.This is considered both a recursive procedure and a recursive process. The reason this is a recursive procedure is because if refers to the procedure (f n) within the procedure itself.
This is also a recursive process, because when we use the substitution model (below), we’ll be building “up a chain of deferred operations” which can’t be performed until later in the process.
The linear recursive process.
Let’s begin by finding the value of (f 5). Since five is greater than three we’ll work out the second part of the if statement using the substitution model:
; Our procedure:
(f 5); Our process:
(+ 2 (f (- n 1))); Substitute 5, which is the value of n:
(+ 2 (f (- 5 1))); Do some math:
(+ 2 (f 4)); Now we will substitute (f 4) with (+ 2 (f (- n 1))), like this:
(+ 2 (+ 2 (f (- 4 1)))); Do some more math:
(+ 2 (+ 2 (f 3)))
...
etc., etc., etc.; If we cut out the extra steps above (which were included for clarity), it looks like this:
(f 5)
(+ 2 (f 4))
(+ 2 (+ 2 (f 3)))
(+ 2 (+ 2 (+ 2 (f 2)))); And once we get to that point, we can start doing our computations. Since 2 is less than 3, we return n, which is 2. Do some more math and we eventually get our answer:
(+ 2 (+ 2 (+ 2 2)))
(+ 2 (+ 2 4))
(+ 2 6)
8
Visually we can see this process grows in both length (time) and width (space).
If we were to write very large and complicated procedures that used a linear recursive process, it would require more resources to complete its computations.
The authors make a point of noting that just because this is less efficient, it can still be “a natural and powerful tool,” depending on the context. (39)
The linear iterative process.
Now let’s write the same procedure so it computes using a linear iterative process.
If we were to run the following values through the function as is, we’d get the following values:
(f n)
...(f 3)
(f 4)
(f 5)
(f 6)
(f 7); Values:
4
6
8
10
12
When n is less than 3, we know the answer will be whatever the value of n is. So I’m only interested in looking at 3 and up. (f 3) equals 4, and the values increment by 2 from there.
Using scheme we can define our own iteration procedure within our (f n) procedure:
(define (f n)
(define (iter a count)
(cond ((< count 3) count)
((= count 3) a)
(else (iter (+ a 2) (- count 1)))))
(iter 4 n))The iter procedure we are defining takes two parameters: a and count. At the end of the procedure we set a equal to 4, and count equal to whatever n starts at.
In Scheme, cond means “conditional,” and it’s just another way of writing an if-else statement, as far as I understand. (Also in Scheme, if is “a restricted type of conditional that can be used when there are precisely two cases in the case analysis.”) (19)
What makes this an iterative process?
If we substitute 6 we can see this visually:
(f 6); In evaluating this procedure we skip to the else statement since n is greater than 3:
(iter (+ a 2) (- count 1)); Using the substitution method we get:
(iter (+ 4 2) (- 6 1))
(iter 6 5)
(iter (+ 6 2) (- 5 1))
(iter 8 4)
(iter (+ 8 2) (- 4 1))
(iter 10 3); Taking out the extra math steps we see:
(iter 6 5)
(iter 8 4)
(iter 10 3)When count equals 3, the result is a, which is 10.
As we can see, the iterative process takes up less width (space).
“What’s the point?”
When I first started coding, concepts like this were not only over my head, but they seemed useless. “If the end result works — if my HTML/CSS/JavaScript hangman game does what it’s supposed to — why does it matter what’s going on under the hood?”
The authors of SICP summarize the importance of understanding the underlying mechanics of programming with the following analogy:
Our situation is analogous to that of someone who has learned the rules for how the pieces move in chess but knows nothing of typical openings, tactics, or strategy. Like the novice chess player, we don’t yet know the common patterns of usage in the domain. We lack the knowledge of which moves are worth making (which procedures are worth defining). We lack the experience to predict the consequences of making a move (executing a procedure).
The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity. (31)
If you’re just getting started with programming and really enjoying going through your front-end course at freeCodeCamp, for example, that’s great! Keep it up. Don’t let concepts like iterative vs. recursive discourage you if you don’t understand them yet. You have to start somewhere, and the important thing is to enjoy the journey. Eventually you will get to a point where you want to go deeper. You’ll want to understand more. That’s when it might be time to pick up a book like SICP. Until then — code on and have fun.
