12

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.

Improve this question
8
  • 2
    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) Commented Mar 15, 2014 at 12:35
  • 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). Commented Mar 15, 2014 at 12:35
  • 3
    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. Commented Mar 15, 2014 at 12:36
  • "that takes a single parameter" to please where should that be stored, if not on the stack? Commented Mar 15, 2014 at 12:59
  • 1
    @alk 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. Commented Mar 15, 2014 at 13:09

2 Answers 2

Reset to default
11

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

1+, Just tested this, and it indeed seems to work. :-)
+1 for mentioning "tail call optimization" as it is the answer and basic thing every functional programming language has in the tutorials
0

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

Improve this answer

Comments

Your Answer

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