SICP 1.2.1 Notes: Linear Recursion and Iteration
Procedures define functionality on a local level, however, it is smart for the programmer to want to know what is happening on the global level of their program. This is a hard thing to do.
There are common “shapes” of processes generated by procedures that correspond to the very valuable computational resources of time and space. This is known in a more modern sense as Big O notation, which deals with the time-complexity of a given algorithm - how long it will take to compute it.
Linear Recursion
Linear recursion is often represented by the factorial function:
n! = n * (n - 1)*(n - 2)*(n - 3)...etc.
This function can be reinterpreted as:
n! = n * (n - 1)!
Which is a function that can easily be implemented as a procedure like so:
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
The “shape” of this procedure is one characterized by expansion and then contraction. The expansion happens because a chain of deferred operations is built up with the recursive nature of the computation, each successive step of the computation building off of and using the result of the last. The contraction occuring when the computations actually begin to be executed.
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
Recursive processes are characterized by a chain of deferred operations.
Since the computation of n! is characterized by a chain of deferred computations relative the size of the argument passed in for n, more information is needed to keep track of the computation as the size of n increases. The information needed to compute the function grows linearly with n and thus the number of steps to execute the computation as well. This kind of process, where the computational time is proportional to n, is known as a linear recursive process.
Iterative Process
We could rewrite this procedure from a different perspective like so:
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter ( * counter product)( + counter 1))))
(iter 1 1))
Both of these functions do the same thing: calculate the factorial of a given number. Each function calculates the result in a number of steps proportional to n.
In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies the conditions under which the process should terminate
Again an iterative process is a combination of:
- A procedure which is comprised of a fixed number of state variables
- A fixed rule for how each of those state variables should progress in the computation, going from state to state
- And an optional end test condition, that once the procedure reaches a certain state, triggers the procedure to terminate itself and stop the computation
Since the number of steps to compute n! still grows linearly with n, this iterative function is considered a linear iterative process.
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720
Comparing Recursive vs Iterative Processes
In the iterative function, the combination of the state variables provide a complete snapshot of the program at any given moment in time. Like a bunch of cogs in a machine working in unison, if you stopped the machine at any one point you could discern how far into the process the machine is by looking at the position of the cogs (state variables).
This is not the case with the recursive function. If you stopped the program mid-way there is certain “hidden” information that is kept track of by the interpreter, rather than be contained in state variables inside of the procedure, that keeps track of “where” in the computation it currently is.
Difference between Recursive Process and Recursive Procedure
If a procedure is defined as recursive it is referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. Whereas if a process is defined as being some sort of recursive, linear recursive, for example, it is strictly in reference to how the process evolves, not the syntax of how the procedure was written.
For example, the iter definition in the iterative process function, is a recursive procedure. It references itself in its procedure definition. So it is a recursive procedure that produces an iterative process. It produces an iterative process because it’s state is captured by the three program variables: product, counter, and n (which, functions as the max-count, termination-triggering condition of the procedure).
Tail Recursion
Another thing that furthers the confusion around recursive procedures vs recursive processes is the fact that Object-Oriented Languages require special “looping constructs” such as do, repeat, for, for-each, and while to implement recursive procedures as iterative processes. Without the special looping constructs recursive procedures in Object-Oriented Languages consume an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, an iterative one.
Scheme/Lisp does not need the special looping constructs to be able to compute iterative processes: it can execute an iterative process in constant space, even if the iterative procedure is described by a recursive procedure. A language with this feature is considered to be tail recursive. It is able to compute iterative processes without special iteration constructs. However, some tail recursive languages will still contain the special iteration constructs, only as syntactic sugar though. You could still achieve the same iterative process with clever procedure definitions, not having to rely on the special constructs.
