Home > OS >  does recursion function with no return have build stack problem?
does recursion function with no return have build stack problem?

Time:10-28

I know that recursion function build stack because previous function is waiting for the return from the next call, but no type function don't have this dependency.so will it build stack?

CodePudding user response:

The stack in reference here is the "call stack" - like its name implies, it is relevant to what you are calling (e.g. parameters). Return values are stored on the heap and the call stack simply stores an address to the heap for the return value. For more information take a look at the article on Wikipedia (there's a nice diagram for reference, with all the proper terminology). This YouTube video also describes the call stack nicely.

Even if the return value is null, we still have to store some reference to it for the caller to use!

Let's look at an oversimplification of what happens:

foo(i) {
  if (i == 0) {
    return 0
  }
  return foo(i - 1)
}

Let's invoke foo(1), here's a simplistic view of the call stack:

[TOP OF STACK]
foo(1)
return address of foo(1)
[BOTTOM OF STACK]

Then foo(1) recursively invokes foo(0):

[TOP OF STACK]
foo(0)
return address of foo(0)
foo(1)
return address of foo(1)
[BOTTOM OF STACK]

Then foo(0) returns 0, so we start popping off our call stack:

[TOP OF STACK]
foo(1)
return address of foo(1)
[BOTTOM OF STACK]

Since foo(1) is now complete, it returns as well, so we pop from our call stack again:

[TOP OF STACK]
[BOTTOM OF STACK]

Even if the calls were not recursive, it would be handled in a similar manner.

  • Related