How to use return function in recursion

Question

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?

@StoryTeller I don't think a notion of call stack is required to understand this, just the basic semantics of function calls and the return statement — Passer By
– Passer By, Commented Jun 1, 2017 at 6:35
Recursive functions work exactly like all other functions. I think you might be thinking of recursion as a kind of loop, but it's a normal function call. — molbdnilo
– molbdnilo, Commented Jun 1, 2017 at 6:43
@PasserBy - Clearly it is required. Otherwise the OP would have been unlikely to get confused about where the return statement takes them. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Jun 1, 2017 at 7:12
@StoryTeller the call stack is for all intents and purposes, an implementation detail, albeit a very well-known one. A function call and return statement is a concept. For example, explaining function calls in Haskell with a call stack doesn't make sense. — Passer By
– Passer By, Commented Jun 1, 2017 at 8:54

TsReaper · Accepted Answer · 2017-06-01 06:33:22Z

1

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.

edited Jun 1, 2017 at 6:33

answered Jun 1, 2017 at 6:27

TsReaper

8557 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

member123 Over a year ago

Thanks a lot for this detailed explanation. It makes things very clear. Thanks again!

Nadir Laskar · Accepted Answer · 2017-06-01 06:43:02Z

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.

Passer By · Accepted Answer · 2017-06-01 08:54:58Z

0

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.

edited Jun 1, 2017 at 8:54

answered Jun 1, 2017 at 6:45

Passer By

21.6k7 gold badges58 silver badges112 bronze badges

Collectives™ on Stack Overflow

How to use return function in recursion

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related