How is the variable closest is updated using recursion

Question

0.00/5 (No votes)

See more:

There is a variable closest in my code and I dont understand how it loops throughout the recursion process.

<pre>#include <cmath>
#include <float.h>

class BST {
public:
  int value;
  BST *left;
  BST *right;

  BST(int val);
  BST &insert(int val);
};

int findClosestValueInBst(BST *tree, int target);
int findClosestValueInBstHelper(BST *tree, int target, int closest);

int findClosestValueInBst(BST *tree, int target){
  return findClosestValueInBstHelper(tree, target, tree->value);
}

int findClosestValueInBstHelper(BST *tree, int target, int closest) {
  // Write your code here.
  if(abs(target - closest) > abs(target - tree->value)){
    closest = tree->value;
  } 
  if(target < tree ->value && tree->left != nullptr){
    return findClosestValueInBstHelper(tree->left, target, closest);
  } 
  else if(target > tree->value && tree -> right != nullptr){
    return findClosestValueInBstHelper(tree->right, target, closest);
  }
  else {
    return closest;
  }

}
int main(){
  return 0;
}

What I have tried:

I tried to imagine the variable closest to be 13 when the target is 12. I went through the code and was going over the conditions but cant understand how i get the initial closest value and how it updates.

Posted 6-Jan-23 13:39pm

Amin Rashid

Updated 9-Jan-23 12:47pm

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2023-01-06T19:17:00

This is only a little textbox, and I can't see when your eye's glaze over - so I'm not going to try explaining in detail or I'll be here typing all day, and you still won't understand.

Instead, I'll give you a quick overview, and make a suggestion that you really should follow, OK?

Recursion happens when you (directly or indirectly) call a function before you exit the same function. For Factorials, it's obvious:

C++

int fact(int n)
   {
   if (n <= 1) return 1;
   return n * fact(n - 1);
   }

Call that and think about how it works:

C++

int f = fact(4);

Fact is called, and n is 4 so it calls fact(3) and when that returns, multiplies it by 4 and returns.
But before it can do the multiply, it enters a new instance of fact with a new value for n (because n is a function parameter, it does not affect the value of n in the calling function).
So now you are executing fact with n as 3, so it calls fact(2) and when that returns, multiplies it by 3 and returns.
But before it can do the multiply, it enters a new instance of fact with a new value for n
Now you are executing fact with n as 2, so it calls fact(1) and when that returns, multiplies it by 2 and returns.
But before it can do the multiply, it enters a new instance of fact with a new value for n
This time, n is 1 so it returns 1, and the previous instance can do it's multiply and returns 2 * 1
So the previous instance can do it's multiply and returns 3 * (2 * 1)
And you are back to the first instance and it can do it's multiply and return 4 * (3 * (2 * 1))

So the final return sets the value of f to 4 * 3 * 2 * 1, or 24 - which is 4!

Your code is doing the same kind of thing but for a b-tree - it goes all the way down the left branch, then follows that with the right branches (and their left branches). Set up a simple tree:

C++

And run your code through the debugger - note which value the current node holds each time, and you will see that it visits every node, and the order in which it does it.

Think about it, and you'll get the idea!

merano99 · Answer 2 · 2023-01-09T12:47:00

The program is incomplete and would have to be completed first. After adding the constructor and the method insert to the BST class, test data and the corresponding call would make sense.

My test program looks like this:

C++

int mydata[] = { 15,3,6,8,13,27,2,18,4 };
BST* head = new BST(mydata[0]);

for (int i=1; i < sizeof(mydata)/sizeof(int); i++)
   head->insert(mydata[i]);

int result = findClosestValueInBst(head, 12);

cout << result << "\n";

The result 13 seems to correspond to the expected result.

As OriginalGriff has already written, it makes sense to look at the flow with the debugger.

How is the variable closest is updated using recursion

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0