CODEWITHSUNDEEP
c++recursion
member123
member123

Reputation: 3

How to use return function in recursion

I am having this below code for inorder traversal of tree:

void inOrder(struct node* r)
{
    if (r==NULL)
    return;

    else
    {
        inOrder(r->left);
        printf("%d ", r->value);
        inOrder(r->right);
    }
}

I am having this silly doubt:

When the bottom most left child is passed as root, it is not null. In the next iteration root will be null (as left child of bottom most left child will be null) and it will encounter return.

Wont this return statement pass the control to main function (or wherever it is called) without printing anything?

Does return behave differently in recursion?

Upvotes: 0

Views: 108

Answers (3)

Passer By
Passer By

Reputation: 21130

A classical example of recursion might better illustrate the problem

int factorial(int n)
{
    if(n == 0)
        return 1;
    return n * factorial(n - 1);
}

If we were to call factorial(3), it will recursively call factorial till the base case n == 0, at which point, will return the control flow to the point where it was called, which is factorial(1) and not main.

So, no, your return statement goes back to the parent node where the function was called.

Upvotes: 0

Nadir Laskar
Nadir Laskar

Reputation: 4150

When the bottom most left child is passed as root, it is not null.

void inOrder(struct node* r)
 {
if (r==NULL)
return;

else{
inOrder(r->left);
printf("%d ", r->value);
inOrder(r->right);
}

}

In your above code when you pass the bottom most left child as root.

It first executes this line

if (r==NULL) return;

as r is not null currently it will skip this return.

In the else part it would now execute

else{
  inOrder(r->left);

Here, It is calling the same function again so, the current execution will pause for a moment and resume when this call returns.

Now, inOrder(r->left); call inOrder(struct node* r); again with null as parameter r to this call. since, you are passing r->left which is null.

so, this call to inorder will hit return

if (r==NULL) return;

As it returns it will resume last instance of inorder call which paused at inOrder(r->left); call.

This is possible because whenever you call a function from inside a function is maintains a call stack.

Now, after resuming it will execute the next line

printf("%d ", r->value);

Which will print the value in your bottom left most node.

finally, it will call the last line

inOrder(r->right); which will again pause the execution of current function and after saving the current state of function in call stack it will call the inorder with null again r->right which will return again from

if (r==NULL) return;

and finally it will come back to original execution of inorder and resume and as there are no instruction left it will return to the main method if you called from there and resume what left in main.

so, your answer is it will print only the value in the bottom most left node.

Upvotes: 0

TsReaper
TsReaper

Reputation: 845

This return will pass the control back to the position where the current "layer" of function is called.

Function calls are organized in a structure called stack. Imagine that there is a box in your computer. The computer can put an element into the box(on top the other elements in the box), or it can remove the element at the top of the box. Consider the following code.

void f(int x)
{
    if (x == 0)
        return;
    f(x - 1);
}

If you call f(2) in the main function, the computer puts f(2) into the box. When f(2) is executed, it calls f(1) inside the function, so the computer puts f(1) into the box(on top of f(2)). As f(1) also calls f(0), the computer puts f(0) into the box.

When f(0) is executed, nothing is called and it meets the return instruction. So the computer removes f(0) from the box, and f(1) is now on top of the box. So your computer knows that it is f(1) rather than main that calls f(0), so it will continue executing f(1). It is the same when f(1) is returned.

Upvotes: 1

Related Questions