Recursion Clarify

closed account (4ET0pfjN)
For recursion, when an initial param gets modified like a numeric value, we use the desired modified value to become the base case and for recursion, I'm sure that it returns that value back to its caller, and this continues returning all the way to the original caller: main, so what I'm trying to say is that it's this value from the base case that gets returned all the way to original caller: main. So I'm a little confused why this function works for inserting a BST node. The instruction I'm unsure about is:

BST insert function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
node* insert (node *p_tree, int key)
{

 if ( p_tree == NULL )//base case: return new node
 {
  node* p_new_tree = new node;
  p_new_tree->p_left = NULL;
  p_new_tree->p_right = NULL;
  p_new_tree->key_value = key;
  return p_new_tree;
 }
 // decide whether to insert into the left subtree or the right subtree
 // depending on the node's value 
 if( key < p_tree->key_value )
  p_tree->p_left = insert( p_tree->p_left, key );//Won't the new node's address be returned all the way

 else
  p_tree->p_right = insert( p_tree->p_right, key );//Won't the new node's address be returned all the way rather
// than what it does which is returning the updated right subtree so I'm a little lost here...

 return p_tree;


So so let's say I make the following list in main:
1
2
3
4
5
6
7
8
9
10
 
int main()
{
 node root = NULL;
 root = insert(root, 80);
 insert(root, 29);
 insert(root, 100);
 insert(root, 28);
 insert(root, 27);
 return 0;
}


So for inserting 28 (where recursion first occurs), the recursive calls are:

node->left = insert(node->left)//to go to node 29->left node->left = insert(node->left)//to go to node 28->left
and now we insert new node 27 and then return the new node and upon returning,
the current top of stack, so the current node is node 28 so we return ptr to the new node 27 as node for node 28->left, and then we back up again (return I mean) so wouldn't node 27 get returned meaning node 29->left = node 27, this is where I am confused. I thought a returned value gets returned ALL THE WAY to original caller: main. That's why I'm unsure why this code works.

I tried with this useless function and indeed the deepest value in base case is retured all the way:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int return_when_one(int num)
{
 if ( num == 1 )
  return num;
 else
  return return_when_one(num - 1);
}

int main()
{
 int num = 3;
 cout << return_when_one(num);//Output: 1

 return 0;
}


Please let me know. Thanks.
Last edited on
closed account (o1vk4iN6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 

node* insert (node *p_tree, int key)
{

 if ( p_tree == NULL )
 {
  node* p_new_tree = new node;
  p_new_tree->p_left = NULL;
  p_new_tree->p_right = NULL;
  p_new_tree->key_value = key;
  return p_new_tree;
 }
 
 if( key < p_tree->key_value )
  p_tree->p_left = insert( p_tree->p_left, key ); // nothing is being returned here

 else
  p_tree->p_right = insert( p_tree->p_right, key ); // nothing is being returned here

 return p_tree; // returns the valued passed, so if it is not null nothing is changed
}


I don't see why it wouldn't work as intended ?
Last edited on
mimichacha (10)
The 'BST insert function' works different from your 'return_when_one'.

The 'BST insert' would return the new node, only if the input node is NULL, otherwise it simply return the input node.
It always return the input parameter p_tree, and p_tree is modifeid only if it is NULL.

However, your 'return_when_one' returns input num, only when it equals 1.
Ikaron (175)
So for inserting 28 (where recursion first occurs)

Actually recursion first happens on line 5 when you insert 29. Basically it's doing this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
main starting on line 5:
* Pass root node pointer into function along with key (29)
  - Is p_tree null? // p_tree == root
    No.
  - Is key less than p_tree->key_value? (is 29 < 80?)
    Yes.
    // Recursion:
  * Pass p_left node pointer into function along with key (29)
    - Is p_tree null? // p_tree == root->p_left
      Yes.
       - Create a new node
       - Initialize its left and right pointers to null 
       - Set key_value to key (29)
       - Return pointer to new node
    - Set p_left to the pointer that was just returned
  - Return pointer to current node
* Back in main
// main doesn't do anything with the return value


So now lets skip to line 7 where you insert 28:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
main starting on line 7:
* Pass root node pointer into function along with key (28)
  - Is p_tree null? // p_tree == root
    No.
  - Is key less than p_tree->key_value? (is 28 < 80?)
    Yes.
    // Recursion:
  * Pass p_left node pointer into function along with key (28)
    - Is p_tree null? // p_tree == root->p_left
      No.
    - Is key less than p_tree->key_value? (is 28 < 29?)
      Yes.
      // Recursion:
    * Pass p_left node pointer into function along with key (28)
      - Is p_tree null? // p_tree == root->p_left->p_left
        Yes.
         - Create a new node
         - Initialize its left and right pointers to null 
         - Set key_value to key (28)
         - Return pointer to new node
      - Set p_left to the pointer that was just returned
    - Return pointer to current node
  - Set p_left to the pointer that was just returned 
  // ^ In this case p_left is set to its self
  - Return pointer to current node
* Back in main
// main doesn't do anything with the return value


I think I got that right. What may be throwing you off is when the function returns p_tree (Check lines 23 & 24 in my 2nd example). "Node 29->Left" isn't being set to "Node 27" because insert() only returns 1 of 2 pointers:
1) A pointer to the newly created node.
2) p_tree

I've re-read this about 20 times and I'm not sure if I've written it well enough. Let me know if you're still unclear about what's going on.
closed account (4ET0pfjN)
I think where I'm stuck is when we reach base case, we:
return p_new_tree; which let's say currently the root is 80, 29, 28.
So we go left and node 28->left would be p_new_tree (pointer to this new node)
which is what this does 
1
2
 
if( key < p_tree->key_value )
  p_tree->p_left = insert( p_tree->p_left, key )//so p_new_tree returned to the current p_tree->left and p_tree currently is node 28
, ok I forgot about the the last line in the function: return p_tree;//so this means currently we are @ node 28 so we return node 28 back to the previous left subtree recursive call so we return pointer to node 28 to: 
1
2
 
if( key < p_tree->key_value )
  p_tree->p_left = insert( p_tree->p_left, key )
again, and then return p_tree; where now p_tree is node 29 which gets returned to the previous left subtree recursive call so again: I think where I'm stuck is when we reach base case, we:
return p_new_tree; which let's say currently the root is 80, 29, 28.
So we go left and node 28->left would be p_new_tree (pointer to this new node)
which is what this does 
1
2
 
if( key < p_tree->key_value )
  p_tree->p_left = insert( p_tree->p_left, key )//so p_new_tree returned to the current p_tree->left and p_tree currently is node 28
, ok I forgot about the the last line in the function: return p_tree;//so this means currently we are @ node 28 so we return node 28 back to the previous left subtree recursive call so we return pointer to node 28 to: 
1
2
 
if( key < p_tree->key_value )
  p_tree->p_left = insert( p_tree->p_left, key )
again, and then return p_tree; where now p_tree and NOW p_tree is node 80 which points to node 29. I hope that is correct. I think it was forgetting about that last line return p_tree; at the end of the function that threw me off.

Put simply: What you return is what you get back. Just like what you put in is exactly what you get in return...I just forgot about what is being returned, so initially once base case reached, indeede p_new_tree is returned, BUT then onwards it's p_tree being returned so the pointer to the new node (p_new_tree) is being returned and assigned to the previous caller's p_tree->left and so forth, so each level has their own p_tree->left that we return back all the way to main. Because a stack frame stores independently its own version of the pointer p_tree so when we return p_tree, it goes back to whoever called it but it's different than my return_when_one function where the SAME value returned back to main b/c I am setting p_tree->left = insert(p_tree->left) for e.g. and THIS p_tree will be returned. I think that's right.
Last edited on
viliml (791)
So basicly, you are simply wondering why the code that works, works? That doesn't make any sense! Simply take it as an axiom or something, and you're done!
closed account (4ET0pfjN)
What do you mean? I'm just trying to clarify and by writing it out, I'm teaching myself.
closed account (o1vk4iN6)
Can you clarify what you don't understand, a simpler explanation (and better formatting) is easier to get your point across than that huge mess above.

The function recursively traverses the tree (going left or right depending on the key) until it reaches the end of a leaf node (the base case), where it than creates a new node for the key.

You shouldn't be comparing it to the "return_when_one" function you made as they are doing different things, if that's where the confusion is.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 

int return_when_one(int num)
{
  if ( num == 1 )
    return num;

  return_when_one(num - 1);

  return num;
}

int main()
{
 int num = 3;
 cout << return_when_one(num); //Output: 3

 return 0;
}


Still this example doesn't do exactly what the insert does as there is no node data, but it's closer than your other example.
Last edited on
Topic archived. No new replies allowed.