Time vs Space
There are two important resources according to [SICP - 1.2 Procedures and the Processes They Generate ] – that is,
Time: Time to execute some procedure . As steps grows, so does the time, following an order like n, n^2, log n and so on.
Space: Space to use. Then what’s “the Space”? It seems to me that it’s like memory space in an computer ( Sorry if my understanding is wrong ). The memory region is provided for each computer processes by the operating system, and each program runs in its given range. When the spaces required by a program exceeds that capacity, the memory leak occurs.
These two resources have a key for understanding the difference between linear recursive process and linear iterative process.
Linear Recursive Process vs Linear Iterative Process
To disclose actual difference between these two processes, let’s consider the following code.
In terms of the time, both processes increase their value proportional to n. However, you can see the complete difference in the space.
; Linear recursive process ; from the figure 1.3 in SICP (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
The linear recursive process increases the space for operation proportional to n, while the space of linear iterative process doesn’t.
; Linear iterative process ; from the figure 1.4 in SICP (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
