CODEWITHSUNDEEP
recursioniterationlisp
Zakaria Sichaib
Zakaria Sichaib

Reputation: 137

Linear recursive vs Linear iterative process (LISP)

So i'm reading the SCIP book which uses the Lisp language to explain the core concepts and i'm currently stuck on Linear recursive vs Linear iterative process difference.

and the example used to demonstrate the difference is the computing of n!

Linear recursive process 

 (if (= n 1)
 1
 (* n (factorial (- n 1)))))

it produces this process :


(* 6 (factorial 5))

(* 6 ( * 5 (factorial 4)))

(* 6 ( * 5 ( * 4 ( factorial 3))))

(* 6 ( * 5 ( * 4 ( * 3 ( factorial 2)))))

(* 6 ( * 5 ( * 4 ( * 3 (*2 (factorial1))))))

(* 6 ( * 5 ( * 4 ( * 3 (*2 1)))))

(* 6 ( * 5 ( * 4 ( * 3 2))))

(* 6 ( * 5 ( * 4 6)))

(* 6 ( * 5 24))

(* 6 120)

720

Linear iterative process 

(define (factorial n)
 (if (= n 1)
 1
 (* n (factorial (- n 1)))))

produces the following process 

(Factorial 6)

(Fact-tier    1  1  6)

(Fact-tier    1  2  6)

(Fact-tier    2  3  6)

(Fact-tier    6  4  6)

(Fact-tier  24  5  6)

(Fact-tier 120  5  6)

(Fact-tier 720  6  6)

720

Even though i did understand the main difference between them i still don't get this paragraph

"The contrast between the two processes can be seen in another way. In the iterative case, the program variables provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three program variables. Not so with the recursive process. In this case there is some additional "hidden" information, maintained by the interpreter and not contained in the program variables, which indicates ``where the process is'' in negotiating the chain of deferred operations. The longer the chain, the more information must be maintained.

Upvotes: 1

Views: 757

Answers (1)

coredump
coredump

Reputation: 38799

The recursive version has the following trace:

  0: (FACTORIAL 10)
    1: (FACTORIAL 9)
      2: (FACTORIAL 8)
        3: (FACTORIAL 7)
          4: (FACTORIAL 6)
            5: (FACTORIAL 5)
              6: (FACTORIAL 4)
                7: (FACTORIAL 3)
                  8: (FACTORIAL 2)
                    9: (FACTORIAL 1)
                    9: FACTORIAL returned 1
                  8: FACTORIAL returned 2
                7: FACTORIAL returned 6
              6: FACTORIAL returned 24
            5: FACTORIAL returned 120
          4: FACTORIAL returned 720
        3: FACTORIAL returned 5040
      2: FACTORIAL returned 40320
    1: FACTORIAL returned 362880
  0: FACTORIAL returned 3628800

Intermediate results for recursive calls are used to produce new results. There need to be some memory to store intermediate results while the recursive calls are made, in order to combine them and compute the result when they finish. This storage is on the call stack, in stack frames.

The "iterative" process has the following trace:

  0: (FACTORIAL 1 1 10)
    1: (FACTORIAL 1 2 10)
      2: (FACTORIAL 2 3 10)
        3: (FACTORIAL 6 4 10)
          4: (FACTORIAL 24 5 10)
            5: (FACTORIAL 120 6 10)
              6: (FACTORIAL 720 7 10)
                7: (FACTORIAL 5040 8 10)
                  8: (FACTORIAL 40320 9 10)
                    9: (FACTORIAL 362880 10 10)
                      10: (FACTORIAL 3628800 11 10)
                      10: FACTORIAL returned 3628800
                    9: FACTORIAL returned 3628800
                  8: FACTORIAL returned 3628800
                7: FACTORIAL returned 3628800
              6: FACTORIAL returned 3628800
            5: FACTORIAL returned 3628800
          4: FACTORIAL returned 3628800
        3: FACTORIAL returned 3628800
      2: FACTORIAL returned 3628800
    1: FACTORIAL returned 3628800
  0: FACTORIAL returned 3628800

In the case of the iterative process, you can see that the result is always the same: intermediate results are just passed back unchanged to the toplevel. In other words, we already know the final result when we are at the innermost call. No storage is necessary for any intermediate value, since everything is kept in the function arguments. You could just as well mutate the arguments with the new values and loop.

In fact, this is basically what happens when calls in tail-position are optimized: recursive calls reuse the same stack frame as their caller, flattening the trace as follows:

(FACTORIAL 1 1 10)
(FACTORIAL 1 2 10)
(FACTORIAL 2 3 10)
(FACTORIAL 6 4 10)
(FACTORIAL 24 5 10)
(FACTORIAL 120 6 10)
(FACTORIAL 720 7 10)
(FACTORIAL 5040 8 10)
(FACTORIAL 40320 9 10)
(FACTORIAL 362880 10 10)
(FACTORIAL 3628800 11 10)
FACTORIAL returned 3628800

You end up having the same behaviour as if you had use a loop construct. But note that even with loops, you can benefit from this trick: tail-call elimination is not limited to recursive calls, it may be done whenever you can safely reuse a frame when calling a function.

Upvotes: 4

Related Questions