How to decide how to build a recursive function

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?

4

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

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.

1

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *