Sometimes when you're coding you're on a problem which can be solved with some recursive method. What is for you the best way to detect when the recursion is a good way to solve a problem and how to implement it efficiently?

I mean, how do you visualize it? How do you convince yourself that it works?


There is no one answer to wether you are better of with a recursion, loop, multiple function calls, ...

But there are some hints:

  • recursion depth can be limited by the size of the call stack (depends on the language). A value that pops into mind is a max of 1024.

  • if the data structure is recursive, for instance a binary tree, recursion is your friend.

  • put your problem into words: "and then the same for the next item" => iteration; "and then the same for the rest" => recursion.

  • if you need to store intermediate values, it is easier done with iteration.

  • if your problem is inherently self-similar, go with recursion.

Final remark: All problems can be solved by both iteration and recursion. It is a good exercise to implement both. Observe, which took you longer, which runs faster, which uses less memory, which is parallelisable? And most importantly: Which was more fun to implement?

  • 3
    Point 1 is (mostly) invalid for tail recursive languages. – thorsten müller Aug 16 '16 at 9:15
  • 3
    "Most problems can be solved by both iteration and recursion." – All of them, actually. Recursion and Iteration are provably equivalent. Iteration is trivially equivalent to tail-recursion. The mapping from general recursion to iteration is not 1:1 like the mapping from iteration to tail-recursion, but it's doable: worst-case, you have to carry around a stack to emulate the recursive call stack. – Jörg W Mittag Aug 16 '16 at 10:09
  • @JörgWMittag; Thank you for pointing that out. I will edit the answer. – steffen Aug 16 '16 at 10:30

Depends on the problem. ! The factorial example is pretty artificial; it’s so simple that it really doesn’t matter which version you choose.  Many ADTs (e.g., trees) are simpler & more natural if methods are implemented recursively.  Recursive isn’t always better. ! Solve a large problem by breaking it up into smaller and smaller pieces until you can solve it; combine the results. Recursion is much better than iteration for problems that can be broken down into multiple, smaller pieces. Precisely, in divide and conquer method using recursion can reduce your problem size at every step and would take less time than a naive iterative approach. Recursion is simpler to implement, and it is usually more 'elegant' than iterative solutions.

  • this post is rather hard to read (wall of text). Would you mind editing it into a better shape? – gnat Aug 18 '16 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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