CODEWITHSUNDEEP
c++recursiontime-complexity
novalain
novalain

Reputation: 2209

Multiple recursive calls

I know what a recursive function is and how I can visualize every recursive call on top of the stack. But I have no idea how to think when the function make multiple calls to itself like

float foo(int n){

   int a = 0;
   for(int i = 0; i < n; i++)
       a += 1;

   if (n > 2)
       return foo(n/2) + foo(n/2); // What happens here?

    return a;
}

Shall I think of two different stacks now or what is the best way to visualize the result?

Upvotes: 3

Views: 1724

Answers (4)

No-Bugs Hare
No-Bugs Hare

Reputation: 1638

Let's try to visualise stack (yes, there is only one stack) for different stages of call foo(4):

before calling foo(4): caller-stack

within original call foo(4): stack=caller-stack, foo(4)

when foo(4) is within the first call to foo(2): caller-stack, foo(4), foo(2)

foo(4) within the first call to foo(2), where foo(2) has already called first foo(1): caller-stack, foo(4), foo(2), foo(1)

after returning from first foo(1): again caller-stack, foo(4), foo(2)

foo(4) within the first call to foo(2), where foo(2) has called second foo(1): caller-stack, foo(4), foo(2), foo(1)

after returning from second foo(1): again caller-stack, foo(4), foo(2)

after returning from first foo(2): caller-stack, foo(4)

foo(4) is within the second call to foo(2): caller-stack, foo(4), foo(2)

foo(4) within the second call to foo(2), where foo(2) has already called first foo(1): caller-stack, foo(4), foo(2), foo(1)

after returning from first foo(1): again caller-stack, foo(4), foo(2)

foo(4) within the second call to foo(2), where foo(2) has called second foo(1): caller-stack, foo(4), foo(2), foo(1)

after returning from second foo(1): again caller-stack, foo(4), foo(2)

after returning from second foo(2): caller-stack, foo(4)

after returning from foo(4): caller-stack

Upvotes: 1

user2512323
user2512323

Reputation:

As other answers mentioned, there is only one stack and recursive calls evaluated strictly in given order.

However, for analysis purpose, you can visualize entire call sequence as a tree. Call tree for <code>foo(n)</code>

Upvotes: 3

Jeremy Friesner
Jeremy Friesner

Reputation: 73051

Shall I think of two different stacks now or what is the best way to visualize the result?

It's still a single stack. In this line:

   return foo(n/2) + foo(n/2); // What happens here?

... first one of the calls to foo() will be evaluated (with its arguments and local variables pushed on to the stack, used, and then popped off of the stack again), and then the other one will be evaluated in the same way. (Note that it is undefined in the language spec which foo() call will be evaluated first, so it's up to the compiler's implementers to decide what order they prefer).

Upvotes: 1

Jeff Foster
Jeff Foster

Reputation: 44706

return foo(n/2) + foo(n/2); // What happens here?

The first expression evaluates completely prior to the second one evaluating. There's nothing to do with two different stacks. One stack with the first call expands and contracts as it is evaluated, and once this expression is completely evaluated the second begins.

Does that help visualize it?

Upvotes: 1

Related Questions