Sign in to follow this  
zoner7

Pointers and scope with recursion

Recommended Posts

Alright. I have a binary tree here, and I was asked to delete all the leaves in the tree. The following code works, but I'm not positive why. Suppose I am at one a leaf that has no left or right nodes. I want to delete this node. I am going to learn that this leaf has no children after the following two calls are made. recursive_clear(sub_root->left); //clear lefthand subtree of node recursive_clear(sub_root->right);//clear the righthand subtree of that node. The only issue here is that the sub_root is set to NULL when these functions are called. Since sub_root is a pointer, when one of these functions returns, shouldn't sub_root still point to NULL? Clearly this isn't the case. If The pointer didn't change its value after leaving a function, then I would never be able to progress up the tree after reaching the bottom. I just always thought that pointers kept their values after going out of scope... or is it only the dynamic memory that the pointer points to that doesn't go out of scope. The code of the whole function is below. Thank you in advance!
template <class Entry>
void Binary_tree<Entry> :: clear( )
/* Post: All entries of the binary tree are removed. */
{
  recursive_clear(root);
  return;
} //clear


template <class Entry>
void Binary_tree<Entry> :: recursive_clear(Binary_node<Entry> * &sub_root)
/* Post: The subtree rooted at sub_root is cleared. */
{
  Binary_node<Entry> *temp;
  if (sub_root != NULL)
    {
      temp = sub_root;
      recursive_clear(sub_root->left); //clear lefthand subtree of node 
      recursive_clear(sub_root->right);//clear the righthand subtree of that node.
      sub_root = NULL;
      delete temp;
    }
  return;
} //recursive_clear



Share this post


Link to post
Share on other sites
You're passing references to pointers here, so if you set that pointer to NULL inside the function, you're setting the actual pointer to NULL, not a local copy of it. However, sub_root is referring to a different pointer in each recursive_clear() call.

So, if we have a binary tree of 3 nodes, a root with only two child-nodes, then calling recursive_clear on root results in the following:
- recursive_clear(root)
- recursive_clear(root->left)
- recursive_clear(NULL)
- recursive_clear(NULL)
// here, root->left is set to NULL
- recursive_clear(root->right)
- recursive_clear(NULL)
- recursive_clear(NULL)
// here, root->right is set to NULL
// here, root is set to NULL
In all cases, the function receives a different pointer, and although that pointer reference is always named sub_root, it is never referring to the same pointer.


Now, it's not necessary to set all those pointers to NULL, considering that you're deleting the node that contains these pointers immediately thereafter anyway. You only need to do that for the root pointer. There's no need for a temp pointer either: just call delete on sub_root and then set it to NULL.

Share this post


Link to post
Share on other sites
suppose that I had a function that is passed a pointer from main



int main()
{
int *p = new int;
*p = 5;

int *q = new int;
*q = 10;

int *d;

foo (p);
return 0;
}

void foo (int *p, int *q, int *d)
{
*p = 10; //so now the integer p points to 5, and this will remain true after scope returns to main. right?

delete q; //Now the dynamic memory q pointed to remains deleted after the function ends.

q = &d; //here p becomes a pointer to q. Will p continue to point to q after control returns to main?
//This is definitely the case when we are working with class members, but will this situation work similarly?
}

How would passing the address of a pointer work differently? I'm still a little confused on that point.

Thank you



Share this post


Link to post
Share on other sites
Quote:
Original post by zoner7
suppose that I had a function that is passed a pointer from main

*** Source Snippet Removed ***


1. you need to rewrite your comments so they actually make sense, so I apologize if my reply makes no sense.

2. passing an address of a pointer is essentially passing the address of an address, which usually doesn't make much sense for a multitude of reasons. I remember someone else saying this in some other thread, but it's like sending someone a link to a website or sending someone a link to a link to a website.

You want to be messing with the website, and your program is trying to mess with links to the website. kind of.

Share this post


Link to post
Share on other sites
First of all, let's stop using the same variable names. It only seems to confuse you. Now, here's your code, with explanations on what's going on:

int main()
{
int *a = new int; // Let's call this new int 'intA'
*a = 5;

int *b = new int; // Let's call this new int 'intB'
*b = 10;

int *c;
// You forgot to initialize c! It now contains a random address.

foo (a, b, c);
// Now, 'intB' no longer exists, but b still holds the address of what once was 'intB'.
// Pointer aliasing - multiple pointers pointing to the same object - can be a dangerous thing!
// a still points to 'intA', which has a value of 10. c still points to the same old random address.

return 0;
// You forgot to delete 'intA'!
}

void foo (int *p, int *q, int *r)
{
// p, q and r are copies of a, b and c. They have the same values, so p and a are pointing to 'intA',
// q and b are pointing to 'intB' and r and c both contain the same random address.
// Changes made to p, q and r themselves have no effect on a, b and c: they may have the same value,
// but they certainly aren't the same pointers. Changes made to 'intA' and 'intB' will, of course,
// be 'visible' outside this function.

*p = 10;
// this changes 'intA's value to 10.

delete q;
// This deletes 'intB'.

q = &r;
// q now points to what r is pointing at: a random address. c, q and r now have the same value.
}


Quote:
Original post by way2lazy2care
2. passing an address of a pointer is essentially passing the address of an address, which usually doesn't make much sense for a multitude of reasons. I remember someone else saying this in some other thread, but it's like sending someone a link to a website or sending someone a link to a link to a website

There are no pointer-to-pointers being passed around in that function, just pointers.

Share this post


Link to post
Share on other sites
Quote:
Original post by Captain P
There are no pointer-to-pointers being passed around in that function, just pointers.

I was replying to "How would passing the address of a pointer work differently? I'm still a little confused on that point," at the end of his source snippet.

Share this post


Link to post
Share on other sites
Ah, you're right, I missed that part. Quote tags strip away code and that line was still inside the source tags. I agree, in C++, you shouldn't be working with pointers to pointers in most cases.


Either way, the same rules apply. The value of these pointer-to-pointers (the address of a pointer) is copied into local pointer-to-pointers. You may want to read up on 'passing by value' and 'passing by reference'. Passing by value provides a function with the value of an object, not with the original object itself. Passing by reference gives the function access to the original object. Note: although pointers are conceptually similar to references, they're not the same.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this