Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

Linear Recursion and Iteration.

I learned linear recursion and iteration, these are fundamental of programming. I'm gonna compare with these processes. You can see that both processes aren't difference at all because these calculates same mathematical function on the same domain, and each requires a number of steps proportional to n to compute n!. Of course, you can get same result 120 which is result of 5! as example from both processes.

This is the linear recursion:

(define (fact-recur n)
  (if (zero? n)
      1
      (* n (fact-recur (- n 1)))))


And this is result of trace:

trace: (fact-recur 5)
trace: |  (fact-recur 4)
trace: |  |  (fact-recur 3)
trace: |  |  |  (fact-recur 2)
trace: |  |  |  |  (fact-recur 1)
trace: |  |  |  |  |  (fact-recur 0)
trace: |  |  |  |  |  1
trace: |  |  |  |  1
trace: |  |  |  2
trace: |  |  6
trace: |  24
trace: 120


This is the iteration:

(define (fact-iter-helper n acc)
    (if (zero? n)
        acc
        (fact-iter-helper (- n 1) (* acc n))))
(define (fact-iter n)
  (fact-iter-helper n 1))


And this is result of trace:

trace: (fact-iter 5)
trace: (fact-iter-helper 5 1)
trace: (fact-iter-helper 4 5)
trace: (fact-iter-helper 3 20)
trace: (fact-iter-helper 2 60)
trace: (fact-iter-helper 1 120)
trace: (fact-iter-helper 0 120)
trace: 120


In firstly process, you seem that process expand a shape by contraction. Linear recursion need base model because it cause infinite loop without base model. The expansion occurs as the process builds up a chain of deferred operations and the contraction occurs as the operations are actually preformed. So you can confirm that function is called with repetition in expansion processes and result is evaluated each of process in contraction. If you wanna execute the linear recursion, you have to keep track of the operations to be performed later on. In this case, n that is amount of operation's information grows with linear as count of step.
By contrast, the iterative process does not grow and shrink. You only need to keep the current values of the variables product, counter and max-count on each of steps. The program variables provide a complete description of the state of the process at any point. If this process is stopped on the way and you wanna restart process, all it need three variables. But the linear recursion is difference, it has hidden information that maintained by the interpreter and not contained in the program variables, which indicates 'where the process is' in negotiating the chain of deferred operations.

Remove all ads