Intended infinite recursion, no-return functions

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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