5

In this video around the 28 minute mark, Brian Harvey was asked by a student if we should always use an iterative process over a recursive process when writing programs. He said no, because

Your programs are not gonna run into space limitations. And in terms of locality of what's in memory, you have to have a lot more control than you do over the way the program is interpreted to really affect that.

Since this is not a scheme course I assumed he is talking generally here about programming languages. And when he said ""Your programs are not gonna run into space limitations.", is he disregarding stack overflows? I am confused by his answer because isn't having a stack overflow means you already ran out of space with function calls? And I don't understand anything from the "in terms of locality" part. stack overflows can happen to scheme, java and other languages. Am I correct or I'm misunderstanding his statement?

6
  • Of course, stack overflows can happen in lisp, as well as Java.
    – azurefrog
    Commented Dec 16, 2015 at 18:08
  • @azurefrog edited, thanks Commented Dec 16, 2015 at 18:13
  • The locality part refers to memory locality, which involves how close together values are stored in memory. Locality can often affect performance in drastic ways because of how CPU caches work. Without watching the clip in question, just reading the quote, my guess at what Harvey is saying is that you have very little control over memory locality in any general sense, especially so in higher-level programming languages, and so writing iterative algorithms instead of recursive ones really isn't going to affect that. Commented Dec 16, 2015 at 18:37
  • 1
    @morbidCode Yes. And that's usually a valid assumption for 99% of algorithms, unless you're working in an environment with an especially constrained stack size. Even in a language like Java, which has a fairly shallow stack, will not likely overflow for algorithms which cannot be trivially expressed iteratively. In a language like Scheme, in which recursion is a common tool, it's even less of a concern. If it ever does become a concern, you can refactor it, but he's saying that it probably won't matter, so you should write code to be as clear as possible first, which is very good advice. Commented Dec 17, 2015 at 7:15
  • 1
    I think he wants to avoid that students become obsessed by optimisation. The course is at a very early stage and my understanding is that he values clean code more that performant code. So he really means that the code his students will have to write is so limited in terms of space requirements that stack overflow isn't going to happen.
    – uselpa
    Commented Dec 18, 2015 at 13:02

3 Answers 3

1

The video you are referring to is a Computer Science lecture. Computer Science is largely theoretical and addresses many details of computing that are not relevant in practicality. In this case, as he says towards the start of the lecture, today's computers are large and fast enough that performance is rarely an issue.


Memory locality is not related to StackOverflowExceptions, in any language. Actually, memory locality refers to the SRAM (static RAM), which holds a cache of adjacent data brought in whenever the bus retrieves data from memory (can be either the disk or RAM). Taking data from this cache is faster than getting it from memory, so a program will run faster if all the data it needs for several, consecutive operations is within the cache.


Now that's all very low-level. Behind most (if not all) modern languages, like Java, there is a compiler working to do numerous low-level optimizations. This means, first of all, that there's little you can do to optimize your code for at a low-level, especially without interfering with compiler optimizations. Secondly, (like as he says right after the segment you're referring to) unless you are a making a resource-intensive game, it is not worth your time to worry about performance (unless you have noticeable performance issues, but that's more likely an indication of other problems in the code).

1

Nowadays with our huge memory stack overflow often is the sign of endless recursion, just as with iterative a non-halting program is a sign of an endless loop.

So yes he is right.

1

Will my recursive procedure cause a stack overflow? It depends on the kind of recursive procedure you have designed, depending on the problem, most naive recusions can be converted to tail-calls(in tail call optimised 'TCO' languages), which allows a recursion to run in constant memory space without using mutation or other stateful things.

In scheme, an iterative process:

(let ((i 0)
      (max 10))
  (let loop ()
    (cond ((< i max)
           (printf "~A~N" i)
           (set! i (+ i 1))
           (loop))
          (else i))))

This procedure uses constant memory, which is equal to the space needed to store the call to loop on the stack. this procedure is not a function, it uses mutation to iterate (its also a recursion ;) but..).

In scheme, two recursions:

(define (fact-1 n)
  (cond ((eq? n 1) n)
        (else (* n (fact-1 (- n 1))))))

(define (fact-2 n carry)
  (cond ((eq? n 1) carry)
        (else (fact-2 (- n 1) (* carry n)))))

Fact-1 is a normal recursion, and is very much functional, there is no state change, instead, the memory use grows as new lexical closures are created with each fact-1 call, eventually exhausting the stack. It grows like

=>(fact-1 10)
..(* 10 (fact-1 9))
..(* 10 (* 9 (fact-1 8)))
..(* 10 (* 9 (* 8 (fact-1 7))))
..     .....
..(* 10 (... (* 2 1) ...))
..     .....
..(* 10 362880)
=>3628800

Whereas Fact-2 is recursive, but in tail form, so instead of building the stack, and collapsing the calls at the base case, the value is passed forward and we get this:

=>(fact-2 10 1)
..(fact-2 9 10)
..(fact-2 8 90)

..(fact-2 7 720)
.. .......(fact-2 1 362880)
=>3628800

Which is equivalent to making fact-1 into an interative process, but without mutation, as values are passed forward, instead of assignment. Notice that each call still produces a new lexical closure, but since the function doesnt return to the original caller, but to the original callers stack location, the compiler can discard the previous closures instead of having them nesting inside of each other, re-binding the variables at each level of recursion.

So where should I use recursion vs iteration That depends entirely on both the process to be designed and the language used. If your language does not support TCO, then you will need to only use shallow recursions, and write looping(recursive or iterative) procedures in a stateful manner. If you do have TCO, then it could be best to use recursion, or tail-calls, or stateful things, or a combination of them. Not all recursive procedures can be written in tail form, and not all iterative processes can be written as a recursion. If you are concerned about memory usage, and are wanting deep recursions, you must use Tail-calls.

NOTE: Some of you may have noticed, but the first procedure is actually a tail call too, but the example still illustrates the point of a normal iteration doing stateful! things, and running in constant maximum memory regardless for all valid inputs.

3
  • What about c# and scala? I believe they both support tail form. Do you mean I will not run out of memory if I write a tail-recursive function without a base case? And isn't a recursive function with an iterative process really is the same with tail-form? Commented Apr 1, 2016 at 6:51
  • Well, If what c# and scala support is true TCO, then a recursive function written in tail-form will use constant memory. even without a base case, instead of running out of memory, you will have an infinite loop(which you may want).
    – Anandamide
    Commented Apr 1, 2016 at 16:55
  • ie (define (foo n) (* n (foo (- n 1)))) has no base case, and since its not in tail form, It will run out of stack space as the calls grow like (fact 10) -> (* 10 (fact 9)) -> (* 10 (* 9 (fact 8))) ....., whereas, if we make it (define (foo n carry) (foo (- n 1) (* carry n))) and then do (foo 10 1) we get (foo 9 10) -> (foo 8 90) -> (foo 7 720) .... which will never run out of stack, even without a base case, it will just keep using a constant amount of memory, ie, the amount needed to store the current function call
    – Anandamide
    Commented Apr 1, 2016 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.