-1

I have came across a concept in recursion which says that when loops are compiled or interpreted then they get converted to recursive functions. If it is true how it takes place ?

Improve this question
3
  • It might have said the other way around. Typically, loops are more efficient than recursion, and, many recursive algorithms can be converted into loops, some without an auxiliary data structure (if each iteration makes new state or updates existing state, while older state is not otherwise used), and some with an auxiliary stack or other data structure (to preserve some old state for later use). I don't know of any "optimizations" that translate loops into recursion -- just vice versa. Commented Feb 6, 2019 at 4:43
  • 1
    @ErikEidt: There are purely functional CPUs and VMs that don't support jumps, goto, or loops. On those kinds of machines, recursion and tail calls would definitely be the way to compile loops. For example, while the PilGRIM ISA has an instruction named Jump, this is actually not a traditional jump instruction, but a tail call. Commented Feb 6, 2019 at 9:14
  • 2
    Hi, welcome to softwareengineering.stackexchange.com. I think, it will help, if you add some more details about where you got that information from and what platform, compiler and/or language your questions relates to. Commented Feb 6, 2019 at 14:53

1 Answer 1

Reset to default
4

It depends. In many language implementations, using recursion for loops is a good way to cause a Stack Overflow as each call adds more and more entries to the stack until it eventually runs out. Some implementations get around that by taking advantage of their design combined with the Tail Call Optimization, which is effectively reusing the current stack entry because you know it will no longer be needed.

That though is rare. Most implementations simply convert the loop into properly positioned goto statements (or jump instructions depending on your perspective) so instructions are repeated.

And certain implementations in certain situations will do an optimization called Loop Unrolling where they effectively copy the code for the number of iterations of the loop rather than do either of these options. That though generally requires the number of iterations to be known at compile time and is impractical for big loops (either in instructions or iterations).

Improve this answer
3
  • I've seen a loop unrolling strategy that worked at runtime. Basically, the program figured out how many times through the loop right before entering it, and then it jumped into the unrolled loop at the appropriate place for it to come out at the right time. I thought it was pretty common for compilers to do that even for generic cases, so long as the code could figure out the iteration count before entering the loop. Commented Feb 6, 2019 at 6:37
  • 2
    Nitpick: all mentions of the term "language" in the last two paragraphs should be "compiler". Languages don't compile or loop unroll, compilers do. Two different compilers for the same language may in the same situation for the same code make different decisions about whether or not to perform loop unrolling, for example. Commented Feb 6, 2019 at 9:16
  • @JörgWMittag - good point; edited. Commented Feb 6, 2019 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.