8

All problems that are solvable with recursion are solvable with loop, and vice versa.

Is this statement right or proven at all? sometimes, using recursion causes stack overflow. if the statement is correct. we'd better use loop instead.

thanks

Baz
  • 36,440
  • 11
  • 68
  • 94
booirror
  • 372
  • 1
  • 3
  • 9
  • 1
    "Solving with a loop" usually means using the heap to store the stack instead of the thread's call stack. – tenfour Aug 27 '12 at 13:27
  • possible duplicate of [Can all iterative algorithms be expressed recursively?](http://stackoverflow.com/questions/2093618/can-all-iterative-algorithms-be-expressed-recursively) – wkl Aug 27 '12 at 13:32
  • I deleted my answer as I discovered a this is a duplicate, but stack overflows are an artificial limitation (bound by call stack size since function calls push another frame onto the stack). Some languages/compilers can 'optimize' away certain types of recursion, such as Tail Call Elimination, to avoid such stack overflow issues. – wkl Aug 27 '12 at 13:34
  • 1
    That's not a duplicate - this one asks for recursive -> iterative, the other one for iterative -> recursive – ltjax Aug 27 '12 at 13:42
  • 2
    @ltjax - the answer is the same - they might ask for different directions, but the answers in the other question mention that recursion and iteration are equivalent. – wkl Aug 27 '12 at 13:52
  • 1
    @birryree I believe that SO policy is that two different questions that have the same answer are not considered duplicates. – Raedwald Aug 31 '12 at 16:11
  • @Raedwald - Fair enough, I was being overzealous. – wkl Aug 31 '12 at 16:16

2 Answers2

13

Yes. Loop + Stack will solve all recursion problems.

After all, compiler does that internally. Recursion is nothing but pushing data onto a stack, and later popping from it, done by the compiler.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
Nawaz
  • 353,942
  • 115
  • 666
  • 851
2

Typically, the corresponding iterative (looping) solution will need just as much storage, but will need to manage it explicitly.

unwind
  • 391,730
  • 64
  • 469
  • 606