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.

Execution of the Tail Recursive Implementation of Factorial

Pointers, Arrays, and Recursion

Conheça os instrutores