3

When and why does recursion perform worse than iteration?

I was recently asked this question for interview. My answer was recursion performs worse when the depth of recursion is large. The interviewer seemed to be expecting a different answer. Could anyone please explain it more.

josh3736
  • 139,160
  • 33
  • 216
  • 263
softwarematter
  • 28,015
  • 64
  • 169
  • 263
  • 1
    Perhaps they were expecting the answer that premature optimization is a waste of time, that you should write code that is clear and understandable and only optimize if it's demonstrated to be an actual bottleneck. You can come up with some great theoretical answers either way, but ultimately, all of them are irrelevant in the real world. – Cody Gray - on strike Feb 01 '12 at 03:27
  • 1
    Perhaps she wanted you to talk about tail recursion optimization? http://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion – MK. Feb 01 '12 at 03:27
  • possible duplicate: http://stackoverflow.com/questions/72209/recursion-or-iteration – M.Babcock Feb 01 '12 at 03:28
  • 12
    Recursion: The absolute fastest way to a http://stackoverflow.com/questions/9090339/when-and-why-does-recursion-perform-worse-than-iteration – NotMe Feb 01 '12 at 03:28
  • @M.Babcock It is not a duplicate. I had seen that question. This one asks the reason. – softwarematter Feb 01 '12 at 03:29
  • @ChrisLively - I didn't flag the question as a dupe (I actually voted it as off topic), I just figured I'd bring it up. Your comment was pretty good though. – M.Babcock Feb 01 '12 at 03:32
  • 1
    *That one gives you the reason*. Read [Paul's answer](http://stackoverflow.com/a/72469/366904) again, carefully this time. Note the links. – Cody Gray - on strike Feb 01 '12 at 03:32
  • @M.Babcock: Thanks. I was hoping that it wasn't too subtle. :) – NotMe Feb 01 '12 at 03:34
  • Because **function calls are expensive** – Seth Carnegie Feb 01 '12 at 03:40

2 Answers2

4

Could be many reasons; some that come to mind:

  • The recursive depth is large increasing stack use - time is spent winding and unwinding the stack, and memory is consumed by the stack leaving less for each recursion, whereas iterating uses JUMP commands that do not use more resources (including the stack)
  • The recursive function holds a lot of state (e.g. local variables) that must be kept in memory until the recursion is complete (iteration, on the other hand, throws away the locals with each iteration), again leaving less available memory for each subsequent recursion
D Stanley
  • 149,601
  • 11
  • 178
  • 240
0

From what you've stated, you have answered the When part of the question:

when the depth of recursion is large

but not the Why part, so you have only answered half of what the interviewer asked.

jdigital
  • 11,926
  • 4
  • 34
  • 51