1

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.

Improve this question
5
  • a) Wrong tags. b) It's not about programming itself, more about theory. c) Read about call stack. Current function doesn't know who called it, it just do what it needs to do and returns. Commented Oct 1, 2019 at 9:12
  • I think you need to ask a concrete question: what particular bit of that paragraph confuses you? Your examples in the question are also wrong: you've repeated the same function definition twice. Commented Oct 1, 2019 at 11:20
  • Typo for the iterative process? this is the same as the recursive one Commented Oct 1, 2019 at 11:27
  • @tfb " In this case there is some additional "hidden" information, maintained by the interpreter and not contained in the program variables" this part is confusing me; What does hidden information means? Commented Oct 1, 2019 at 12:04
  • This book is bad pedagogy. It's using recursion to denote iteration; you're supposed to understand that tail recursion is a form of iteration in the context of the Scheme language. This would be better explained using a true iterative construct involving a loop, with mutated variables. Commented Oct 1, 2019 at 15:31

1 Answer 1

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.