How to access the call stack?

Question

I have a tree data structure composed by parent nodes and child nodes, something like this:

<Node1>
  <Node2/>

  <Node3>
    <Node4/>
  </Node3>
</Node1>

And to parse the structure i use a μ-recursive function:

void RecursiveFunction(NodeT node)
{
    if(node.has_child())
        RecursiveFunction(node.child());
}

When i call RecursiveFunction passing as parameter, for example, Node2 i want to have the access to the father (Node1) data without storing these data using additional data structures, because the data of the first node has been stored on the call stack before making the recursive call. So I need to access the call stack to read data of Node1 while I am parsing Node2 failing direct access to the father, and so on.

For example, if i'm parsing Node4:

void RecursiveFunction(NodeT node)
{
    /* Access to Node3 and Node1 data...

    if(Node4.has_child())
        RecursiveFunction(Node4.child()); */
}

Is it possible? In what way?

Thanks.

This is a VERY bad idea. If you want to do that, include a pointer to the parent in `NodeT`. Trying to mess around with addresses in the stack is going to be a) messy, b) extremely unportable, c) probably unreliable. — CodeClown42, Apr 23 '12 at 11:44
Why not store this state in the Node and then just do `node.parent()`? — RedX, Apr 23 '12 at 11:45
I just want to know if you can access the stack and how, if this is not a correct way i will not do it. — gliderkite, Apr 23 '12 at 11:50
@gliderkite: The layout of the stack as well as classes is an implementation detail that is not portable across compilers and architectures. In pricinple you can do what you want but the solution would only apply to your specific compiler settings. — Martin Liversage, Apr 23 '12 at 12:00
Implementing the recursion by iteration is quite easy, a lot safer and equally fast as accessing the call stack. Also, if you are writing a program for PC machine, take into consideration, that a structure with 1000 levels of nesting will take only 4 kB of memory. You don't really have to fight for every byte - memory nowadays is very cheap. — Spook, Apr 23 '12 at 12:00
Thanks to all, at this point I will avoid using the stack for my purposes. — gliderkite, Apr 23 '12 at 12:03
And one more thing. Sometimes compiler doesn't place function parameters on the stack - see http://en.wikipedia.org/wiki/Tail_call — Spook, Apr 23 '12 at 12:05

score 1 · Accepted Answer · answered Apr 23 '12 at 11:41

It would be possible, but it would be quite dangerous to do so. This is mainly because you want to mess with the process stack. Also I don't think there are any library functions to do so, that being said you would have to do some pointer arithmetics to achieve that.

score 1 · Answer 2 · edited May 23 '17 at 10:34

1

Even if you would find a way to access the data from the calling function, it would not be easy for any other programmer to understand what you do.

I would suggest to replace the recursion by an iteration which should allow you to express clearly what you want to do. See Way to go from recursion to iteration for more information.

edited May 23 '17 at 10:34

Community

1
1

answered Apr 23 '12 at 11:47

Philipp

11,549
8
66
126

score 1 · Answer 3 · answered Apr 23 '12 at 11:49

Accessing the callstack is a little bit of overengineering for me. Convert the function from recursive to iterative and use your own stack. The stack shall contain an instance of NodeT and integer value informing the function, how many of the node's children has been already processed. If this value is lower than node's child count, loop shall increment this value and add the next child to the stack. Otherwise it shall process the node and then pop it from the stack.

The other advantage is, that you're no longer restricted by size of the program's stack and you can process way more nested structures if there is such a need. Otherwise you risk, well, let's not be affraid to say, stack overflow.

Michael Wild · Answer 4 · 2012-04-23T12:04:22.083

0

If you want or must (e.g. homework requirement?) stick with recursion, add the parent node as a second argument to your function which defaults to NULL, indicating that the current node is the root node. I.e.:

void RecursiveFunction(NodeT const& node, NodeT const* parentPtr=NULL)
{
    if(node.has_child())
        RecursiveFunction(node.child(), &node);
}

Note that I modified your function to accept the first argument by reference to const, otherwise you create a lot of copies of your tree.

edited Apr 23 '12 at 12:04

answered Apr 23 '12 at 11:55

Michael Wild

24,977
3
43
43

No homework, no reference just because this is an example. Anyway, how can i access to the parent of parentPtr? – gliderkite Apr 23 '12 at 12:01
If you need that, you need to include that information in your `NodeT` type. – Michael Wild Apr 23 '12 at 12:03
As I wrote, I can not have direct access to the father with my data structure. – gliderkite Apr 23 '12 at 12:04
Then you're out of luck. Just out of curiosity: Why not? Is it some limitation of already existing code? What you actually want to do is what debuggers do. And besides, for some of the function calls there might not even *be* a stack because the compiler decided to inline it. – Michael Wild Apr 23 '12 at 12:07
The data structure is not my, i cannot change it. – gliderkite Apr 23 '12 at 12:08
Are the functions under your control? Could you use a `std::list` to push and pop all the elements that are being processed manually? – Michael Wild Apr 23 '12 at 12:10
Yes i could use [stack](http://www.cplusplus.com/reference/stl/stack/). At this poit i will find i different solution (avoid using call stack). – gliderkite Apr 23 '12 at 12:12

score 0 · Answer 5 · answered Apr 23 '12 at 13:27

The call stack is used for function parameters as well*, so use that to build the chain:

struct chain {
  NodeT* node;
  chain const* parent;
}
void RecursiveFunction(chain const& c)
{
    if(c.node->has_child()) {
       chain child = { c.node->child(), &c };
        RecursiveFunction(child);
    }
}

[*] At least conceptually; actual implementations may differ. In any case this C++ code is portable, unlike low-level hacks.

How to access the call stack?

5 Answers5