An Introduction to Linear Recursive & Linear Iterative Processes in ProgrammingUsing the Scheme dialect of LispJoe CardilloBlockedUnblockFollowFollowingMay 6Photo by Ilze Lucero on UnsplashFor 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)8Visually 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:4681012When 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).
.