7

Infinite recursion is most often not desired, and when it happens it usually causes a stack overflow or segfaults.

But for theory's sake, and plain curiosity, I've been thinking if it'd be possible to create actual infinite recursion, intentionally.

Working in C++ and C where the stack, usually, grows for each function call, and each function returns and pops the part of the stack it handled.

Here's the thought. Would it be possible to force a function to clear out it's own stack space and then call another function so that the new function effectively replaces the first function, without the first function needing to return and then fire again via a loop.

I'm not only thinking about plain loops as a possible use for this, if there would be any. Loops usually do a good job at what they do. But what if you were to use it for sending signals through a node network, that carry on indefinitely in their own process threads until they reach a certain condition. It might be a tool that could be used for some problems.

Remember, I'm not really asking if it's practical, only if it's possible to do. For science!

Michael0x2a
  • 58,192
  • 30
  • 175
  • 224
Zoomulator
  • 20,774
  • 7
  • 28
  • 32

3 Answers3

15

Would it be possible to force a function to clear out it's own stack space and then call another function so that the new function effectively replaces the first function

This is used for tail-call-optimization, so yes, it is possible and used in practice. In languages like C++ this a nice feature, because sometimes algorithms are simpler to express using recursion, but more efficiently implemented using a loop. The transformation can in some cases be done automatically by the compiler.

Community
  • 1
  • 1
Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
  • 3
    This is not what OP asked: tail-call optimization is about replacing recursion with a loop, whereas he's talking about wiping out the stack of the frames which were allocated for the function invocation. – akappa Oct 19 '11 at 11:00
  • 8
    @akappa: No, tail call optimisation is exactly what the OP describes. If it's a recursive call to the current function, then you end up with a loop as you describe; a tail call to another function can be implemented by wiping the current stack frame and branching to the other function. – Mike Seymour Oct 19 '11 at 11:05
  • @akappa: Are you sure that tail-call optimization always produces a loop? What if the a functions calls different other functions based on a condition? This is not easily replaced by a loop, but could be optimized away. – Björn Pollex Oct 19 '11 at 11:05
  • @akappa, how would you replace with a loop an indirect tail call, like in `return (*someptr)(args...)`? – SK-logic Oct 19 '11 at 11:07
  • 1
    Umh, I've seen tail-call optimization in the context of quicksort, and it was an optimization done manually in the source code. It appears that you're right and my idea of "tail-recursion" is wrong. – akappa Oct 19 '11 at 11:08
  • I would prefer a manual optimization over a compiler side one, since different compilers would most likely handle it differently, or am I wrong? – Zoomulator Oct 19 '11 at 11:13
  • @Zoomulator: Compilers are usually better than humans at optimization. – Björn Pollex Oct 19 '11 at 11:24
  • @Zoomulator, there are languages which specifications explicitly requires that compiler do an optimisation. There are VMs (e.g., .NET) which provide an explicit tail call annotation. It is not possible at all to do it manually for a generic case. – SK-logic Oct 19 '11 at 11:24
  • @Björn Pollex: I'm wondering mainly if there's a way of guaranteeing it across implementations rather than having it more optimized on a few compilers. – Zoomulator Oct 19 '11 at 12:17
5

There is a technique called trampolining that is used to implement continuation-passing style programming without the use of tail-call optimization. If you consider any language without support for TCO, such as JavaScript, and research solutions for CPS in that language, then it is likely that the solution involves trampolining.

Essentially, with trampolining there is a function called a trampoline which iteratively calls thunk-returning functions.

I know that you said "without the first function needing to return and then fire again via a loop"—that's what trampolining is—but considering that this is C++, leaving scopes by, for example, returning is central to the core design of C++'s automatic resource management via destructors (see: RAII). You could alternatively use C's setjmp()/longjmp() functions to wipe out stack, but then you would need to be very careful in making sure that all resources are released properly.

Daniel Trebbien
  • 38,421
  • 18
  • 121
  • 193
  • 1
    You'd need an inline assembly to do trampolining efficiently in C++. And yet, it is significantly less efficient than a simple rewind-the-stack-and-jump sequence. – SK-logic Oct 19 '11 at 11:28
2

This does remind me of an optimisation that can be done in assembler code. Say you have this:

  call FuncA
  call FuncB

you can replace it with:

  push ReturnAddress
  push FuncB
  jmp FuncA
ReturnAddress:

This causes the ret at the end of FuncA to jump to FuncB directly rather than back to the caller and then onto FuncB. Not really possible in higher level languages.

There's also this:

 call FuncA
 ret

which can be changed to:

 jmp FuncA
Skizz
  • 69,698
  • 10
  • 71
  • 108
  • I use your second trick all the time. But what's the point of your first construct? – TonyK Oct 20 '11 at 13:10
  • @TonyK: The first one replaces four jumps (call-ret-call-ret) with three (jmp-ret-ret). And it's not limited to two calls, you can daisy chain any number of calls. – Skizz Oct 20 '11 at 13:13
  • In fact it replaces call-ret-call-ret with push-push-jmp-ret-ret. Is that ever an improvement? – TonyK Oct 20 '11 at 14:09
  • Well, the call-ret-call-ret is a push-jump-ret-push-jump-ret, so it is better plus you only do one memory load for the code, i.e. the code at the call-call is not reloaded between calls - there's three code loads instead of four. Less memory access the better. – Skizz Oct 20 '11 at 14:12
  • I'm quite unfamiliar with how to implement assembly code. Would there be a reasonable way of making this as an inline wrapper in C/C++ to make a function act this way? Thanks for the answer nonetheless! – Zoomulator Oct 20 '11 at 14:50
  • @Zoomulator: I was going to say there's no way to do this, but, and this is a very technical but, you could have [naked functions](http://msdn.microsoft.com/en-us/library/4d12973a.aspx) (in DevStudio anyway, other compilers will differ). – Skizz Oct 20 '11 at 14:58
  • @TonyK: Push-push-jmp-ret-ret may be inferior to call-ret-call-ret, but it can also replace call-ret-call-ret-jmp since pushed "return" address can be anywhere. A more significant aspect of ppjrr is that the pushed addresses may be the results of computations, and need not exist in any register at the time the "computed jump is taken. – supercat Nov 03 '11 at 19:15