The Call Stack Does Not Say "Where You Came From", But "Where You Are Going Next"

The call stack does not say where you came from, but where you are going next?

You've explained it yourself. The "return address" by definition tells you where you are going next.

There is no requirement whatsoever that the return address that is put on the stack is an address inside the method that called the method you're in now. It typically is, which sure makes it easier to debug. But there is not a requirement that the return address be an address inside the caller. The optimizer is permitted to -- and sometimes does -- muck with the return address if doing so makes the program faster (or smaller, or whatever it is optimizing for) without changing its meaning.

The purpose of the stack is to make sure that when this subroutine finishes, it's continuation -- what happens next -- is correct. The purpose of the stack is not to tell you where you came from. That it usually does so is a happy accident.

Moreover: the stack is just an implementation detail of the concepts of continuation and activation. There is no requirement that both concepts be implemented by the same stack; there could be two stacks, one for activations (local variables) and one for continuation (return addresses). Such architectures are obviously much more resistant to stack smashing attacks by malware because the return address is nowhere near the data.

More interestingly, there is no requirement that there be any stack at all! We use call stacks to implement continuation because they are convenient for the kind of programming we typically do: subroutine-based synchronous calls. We could choose to implement C# as a "Continuation Passing Style" language, where the continuation is actually reified as an object on the heap, not as a bunch of bytes pushed on a million byte system stack. That object is then passed around from method to method, none of which use any stack. (Activations are then reified by breaking each method up into possibly many delegates, each of which is associated with an activation object.)

In continuation passing style there simply is no stack, and no way at all to tell where you came from; the continuation object does not have that information. It only knows where you are going next.

This might seem to be a highfalutin theoretical mumbo jumbo, but we essentially are making C# and VB into continuation passing style languages in the next version; the coming "async" feature is just continuation passing style in a thin disguise. In the next version, if you use the async feature you will essentially be giving up stack-based programming; there will be no way to look at the call stack and know how you got here, because the stack will frequently be empty.

Continuations reified as something other than a call stack is a hard idea for a lot of people to get their minds around; it certainly was for me. But once you get it, it just clicks and makes perfect sense. For a gentle introduction, here are a number of articles I've written on the subject:

An introduction to CPS, with examples in JScript:

http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/11/recursion-part-five-more-on-cps.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/15/recursion-part-six-making-cps-work.aspx

Here are a dozen articles that start by doing a deeper dive into CPS, and then explain how this all works with the coming "async" feature. Start from the bottom:

http://blogs.msdn.com/b/ericlippert/archive/tags/async/

Languages that support continuation passing style often have a magic control flow primitive called "call with current continuation", or "call/cc" for short. In this stackoverflow question, I explain the trivial difference between "await" and "call/cc":

How could the new async feature in c# 5.0 be implemented with call/cc?

To get your hands on the official "documentation" (a bunch of white papers), and a preview release of C# and VB's new "async await" feature, plus a forum for support Q&A, go to:

http://msdn.com/vstudio/async

How does the call stack unwinding process exactly work, for function calls? - C++

towerOfHanoi(stack1,stack2,stack3, 2) returns stack3 to towerOfHanoi(stack1,stack2,stack3, 3) beacuse of

if (n == 2) {
    return stack3;
}

but

towerOfHanoi(stack1,stack2,stack3, 3) doesnt return anything to main. Because you didnt provided a return statement at the end function.

Non-Basic Code in VBE Call Stack - What Does it Mean?

As freeflow mentions in comment to you, the call stack shows [Non-Basic Code] whenever an external code is called.

Look at this part:

For Each Fil In OldFolder.Files
    ...
Next Fil

You are doing a For Each over the OldFolder.Files; who is the one doing the enumerating? It's not obvious when you program VBA, but if you were writing C, something has to implement the enumerator for the For Each statement to work on. In this case, the Scripting.Files object has implemented a hidden enumerator. Thus, when VBA has a For Each, it's calling the hidden enumerator, and getting a item out of it.

This is not the only way. There are other ways you can see a Non-Basic Code -- a common routine is via event handlers. Say you do a MyWorkbook.Save to save the Excel workbook. That will call events on the workbook such as BeforeSave event and so forth. If you have VBA code in the event handlers, you certainly will see a Non-Basic Code between the calls.

Basically, whenever your code has to pass through some external library to execute the code, the call stack will insert Non-Basic Code to let you know that there's a layer between your VBA code and the previous code that triggered it. There are also cases where your VBA code might be accessed by a non-basic Code entirely so it'll be the first one in the call stack, too.

How do I break out of this recursive call?

Your code never does.

Recursive algorithms pretty much all boil down to this exact same style:

1. First, check if some edge case has been reached (generally, the very simplest case). In this case, return immediately - do not recurse. By tautology, if the answer is so easy you can just give it without needing to recurse, that defines 'edge case' / 'simple case'. There must be at least one such case, or a recursive algorithm cannot work.

2. Otherwise, provide your answer and feel free to employ as many recursive calls as you prefer, but every single last one of those calls must be simpler, defined by the idea that it is strictly closer to that simple case as mentioned in 1.

3. All state is conveyed via parameters. It is common to have a private helper method that does the actual work which has a bunch of extra parameters, and the public API that is a one-liner that calls the helper, providing initial values for those extra parameters. Only if you have no such state can you omit this one.

Your code isn't doing this. There is a simple case, which is if a or b or c is 0, but your 6 recursive calls are not clearly moving towards simplicity.

The fix is not obvious. Your algorithm cannot work as written and cannot be fixed without considerably rethinking it.

Hopefully the above will help you: Your recursive calls need to become simpler somehow, guaranteed. Right now it's not guaranteed: Yes, every call is moving one of the 3 numbers closer to the edge case (be 0), but there is no clear flow: If I call your code with, say, 3/4/5 as arguments, then it makes recurisve calls with 2/5/5, 2/4/6, etcetera. That first call (2/5/5) is not moving guaranteed closer to the edge case, because as part of its call stack, it'll be doing 3/4/5 again.

---

Related Topics