0:02

In this video, we're going to trace through

Â the execution of a tail recursive version of factorial.

Â The factorial function has one parameter

Â 'n,' which is the number we're computing the factorial of.

Â And it returns an integer that is the factorial of that input.

Â The difference between this version and the previous implementation is

Â the helper function named "fact_helper" which has two parameters,

Â an integer 'n' and an integer answer.

Â 'n' is the number we are computing the factorial of,

Â and answer is a running product gets computed with each recursive call.

Â You can see that when "fact_helper" calls itself,

Â it is the last computation it does.

Â This is called tail recursion.

Â Let's step through the execution.

Â We begin inside the factorial,

Â where 'n' has the value of three and we're going to call "fact_helper."

Â So we need to create a stack frame.

Â And we're going to send in the arguments 'n' equal to three and answer equal to one.

Â We mark the call site location with a one,

Â so we know where to return when we leave the function.

Â Inside a "fact_ helper" because 'n' has the value of three,

Â we skip over the base case and we're going to call "fact_helper" once again.

Â This time, creating a stack frame for

Â the next recursive call where 'n' has the value of two and answer has the value of three.

Â Now, as we step through this code note that it does not

Â have a compiler optimization that we'll introduce later in this video.

Â So this is going through the tail recursive function as you would

Â expect it to happen with nothing fancy or optimized yet.

Â We step into the function,

Â once again we pass the base case,

Â then we make another frame for the next call the "fact_helper"

Â where 'n' has the value of one and answer has the value of six.

Â We step into that function,

Â pass the base case and make another stack frame for

Â this call to "fact_helper" where 'n' has

Â the value of zero and answer has the value of six.

Â This time when we step into the function,

Â 'n' is less than or equal to zero.

Â This is the base case,

Â so we return the answer six all the way up these calls.

Â Returning from the recursive call to call site location two,

Â then repeatedly returning to call site

Â two and destroying the stack frame for each recursive call.

Â This repeats again.

Â Finally, we return the value six to call site location

Â one and move our execution arrow back into the function factorial.

Â Now the thing to notice here is that we only needed to

Â return the value six all the way up these calls.

Â As soon as we placed each tail recursive call,

Â we didn't actually need the stack frame anymore because

Â there's no value in the frame that we're going to use again.

Â An optimizing compiler will recognize

Â this and perform what's called tail recursion elimination.

Â A stack frame will not be created for each recursive call to "fact_helper."

Â Let's step through the optimized version.

Â We start inside a factorial once again with 'n' having the value of three.

Â We create a stack frame for "fact_helper" where

Â 'n' has the value of three and answer has the value of one.

Â We mark the call site location one and step into "fact_helper."

Â 'n' is not less than or equal to zero,

Â so we're going to place the recursive call to "fact_helper."

Â However, we're going to reuse the frame.

Â First, we have to evaluate the parameters to two and three respectively.

Â Note that we do this before we start changing any of

Â the values in the frame since we want to use the current values.

Â Then we are going to update the value of 'n' in the frame to be

Â two and the value of answer to be three.

Â Now we jump back inside of "fact_helper," pass

Â the base case and once again we're about to place a recursive call.

Â But instead, the compiler will make the code update

Â the values of 'n' and answer to the new arguments, one and six.

Â We skip the base case and reuse the stack frame one more time.

Â This time with 'n' having the value of zero and answer having the value of six.

Â This time we go into the base case and now return the answer of six,

Â one time back to call site location one in the function factorial.

Â Notice that the stack frame does not need to be created for every call to "fact_helper."

Â What this means is that the space you

Â require is no longer proportional to the size of 'n'.

Â You simply need one frame for factorial and one frame for fact helper.

Â