Infinite recursion without overflow - is it possible?

Question

The reason for stack overflow is because stack space runs out, but what if functions have no parameters so that no data has to be pushed onto the stack? That still leaves pushing the "return" address, but in a case of intended infinite recursion that would be unnecessary.

So what I am asking I guess is... whether it is possible to use some kind of calling convention that the call doesn't put anything on the stack and just jumps to the first instruction and executes and provided that the final instruction will be another call to a function until ultimately execution is terminated? Ideally, if this can be implemented with function pointers and dynamic linking?

Just to specify, I am referring to a function that takes a single parameter and returns nothing, so technically fastcall will suffice, but it still preserves an address to return to, which will eventually lead to overflow. Can this be prevented in some way?

Another important point I failed to mention earlier, I don't mean recursion of a single function, e.g. where the state is static and is being reused, I mean recursion from one arbitrary function into another.

Cheiro

Not in C++ as far as I'm aware.. you need Tail Recursion which C++/C currently don't support (at least as part of the stanards) – Barroom

I don't think there is a calling convention that doesn't put anything onto the stack. MSDN's calling-convention docs show a bunch of different calling conventions, but all use the stack eventually (a few use registers first). – Afternoon

To clarify @Mgetz's comment, neither the C nor the C++ standard requires support for tail calls, but both of them do allow it, and current compilers are capable of it. – Halleyhalli

"that takes a single parameter" to please where should that be stored, if not on the stack? – Hickok

@Hickok - on a register reserved for that purpose, which is reused by each following function – Cheiro

@alk, it can be stored on the stack, the point with tail recursion is that the memory usage is kept constant, no matter how deep the recursion is. – Mercantilism

@jbr: You want to say recent compilers are clever enough to detect that the current stack frame isn't used anymore when doing the tail call and though just reuse the same stack-frame for each recursive call? – Hickok

@Hickok That would be one way to implement it, but most likely the compiler simply changes the function body into a loop, without a recursive call. Implementing tail recursion is not very difficult, it's the detection of cases where it is applicable that are hard. – Mercantilism

Answer 1

Yes it is possible, there are two kinds of of recursive function. The kind you are looking for are the primitive recursive functions, these are equivalent to a simple loop. And are normally implemented with tail recursion, where the stack is kept constant, and the function never return through the stack.

Some C++ compilers might be able to detect some primitive recursive functions, and translate them to a loop construction instead of function calls. But this only works as long as the compiler is able to recognise what is going. So the answer is perhaps. Basicly if the programmer does something highly ineffective, then the compiler might or might not be able to help. So the usual process of 'code, profile, optimise, repeat' still goes.

Mercantilism

1+, Just tested this, and it indeed seems to work. :-) – Hickok

+1 for mentioning "tail call optimization" as it is the answer and basic thing every functional programming language has in the tutorials – Deductible

Answer 2

My two cents on this.

Let us say that we have a pointer to an array stored in RAM

double* NeuronWeights[1000];

On the stack we have a function

void manipulateneuronweights(double weightsarray[1000]){

  //arbitrary genetic algorithm to vary weights in weightsarray

}

while (1){
manipulateneuronweights(Neuronweights);
}

So essentially, at the end of the function, the function is popped of the stack and loaded again. It still manipulates the weights in the external array so it still serves the purpose of recursing, without the problem of filling out the available space in the stack. You can definitely change the condition statement in the while loop since that runs infinitely

Bibcock