0

While reading the "Cracking the coding interview" I learned that all recursive problems can be solved iteratively. I can't get my head around the statement. To me, the only option left is that of brute force search. So, is there a general methodology to convert a recursive problem to an iterative one efficiently? e.g. How would one do it for merge-sort? It has complexity O(nlog(n)) in recursion. How'd one solve it iteratively?

Noman Tanveer
  • 175
  • 1
  • 2
  • 9
  • If you google what you just asked, you'll see plenty of blogs explaining how to "blindly" do that conversion. Regarding the mergesort problem, there are multiple ways of doing it: either you use an explicit stack or you just solve the problem for arrays of n = 1, then n = 2, etc until you reach n = n. – devoured elysium Jun 21 '21 at 06:47
  • 1
    You can replace a recursive call using a for/while loop, but that will not make your program a simple iteration in general. For the general case, you will need a stack, thus reimplementing what the compiler/machine does in the recursive version. Tail-recursive program can trivially replaced by a simple iteration, more complex cases are much more difficult to manage. And in the general case, you can't remove the recursion. – Jean-Baptiste Yunès Jun 21 '21 at 07:04
  • @Jean-BaptisteYunès You can always remove recursion using a stack. – Mark Saving Jun 23 '21 at 17:33
  • @MarkSaving Then it is no more an iteration. – Jean-Baptiste Yunès Jun 24 '21 at 10:42

0 Answers0