How to decide how to build a recursive function

Question

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?

• gnat: obligatory reference to How to decide how to build a recursive function
• jk.: Possible duplicate of Recursion or while loops
• steffen: @gnat: O_o no break condition ........
• thorsten müller: Is Programmers.StackExchange tail recursive? Or did gnat cause a StackOverflow?

Answer 1

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?

• thorsten müller: Point 1 is (mostly) invalid for tail recursive languages.
• Jörg W Mittag: "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.
• steffen: @JörgWMittag; Thank you for pointing that out. I will edit the answer.

Answer 2

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.

• gnat: this post is rather hard to read (wall of text). Would you mind editing it into a better shape?