In this video, we'll learn about recursive functions and
how to implement them in c++.
A recursive function is a function that calls itself.
The function can call itself directly or indirectly
through another function.
If we end up with two or more activation records on the
stack for the same function, then we have recursion.
Recursion is great for certain classes of problems.
Recursive problem solving is something that most programmers have a little
trouble doing when they first learn.
That's normal.
Eventually, you'll understand that Recursive Solutions
make sense in certain cases.
There are many types of recursive problems that lend themselves
well to a recursive solution.
In mathematics, we had factorial, Fibonacci numbers
fractals and many more.
In searching and sorting, we have binary search and search
trees, depth-first search, graphs and also many more.
There are also classic problems like the towers of Hanoi that
can really be hard to solve with a non-recursive solution.
Let's see how we can calculate the factorial of a number using recursion.
Here we see the definition for factorial as you
would find in a math book.
Factorial is defined in terms of itself.
That's what recursion is all about.
We have a base case.
So in this case, factorial of 0 is 1 by definition.
And we have the recursive case.
Factorial of n or n factorial is equal to n x n - 1 factorial,
see the recursion there.
Let's see how we can implement this in c++.
So let's look at the code starting at main.
We call factorial and pass in 1/8 of the factorial function.
When the factorial function returns, the value returned
will be output to the console.
In this case, we expect 40320.
Okay, so now let's look at the factorial 'function itself.
First, we need to decide what types will accept the return.
The factorial function can generate massively huge numbers.
So in this case, I'm using unsigned long long as the return
type and the parameter type.
This can hold very, very large positive integers, but
we can still get an overflow even with such a big number.
If you look at the code for the factorial function, it looks
exactly like the mathematical definition of factorial.
We check a base case.
In this case, if n is equal to 0, we return 1.
Remember, the return knocks you out of the function immediately.
Otherwise, we return the results of calling the factorial
function again with n - 1.
So in this case, it would be returned n x call factorial with n - 1.
There's the recursion.
The base case is super important since it's what stops the recursion.
Otherwise, we would request indefinitely and eventually we
would run out of stack space and get a stack overflow error.
In a bit, we'll head over to the IDE and I'll walk you step-by-step
in detail through an example call to factorial so you can see exactly
what's happening on the stack.
Let's look at calculating a Fibonacci number now.
Here's the definition for Fibonacci number.
There to base cases.
Fibonacci of 00, and Fibonacci of 1 is 1.
And the recursive case is Fibonacci of n is equal to Fibonacci of
N - 1 + the Fibonacci of n - 2.
Again, notice the recursive definition.
Fibonacci is defined in terms of itself.
I think you can see how to implement this in c++.
Again, I've decided to use unsigned long long since Fibonacci
can also produce huge numbers.
Notice in the main, I call Fibonacci.
And the result I expect back is 832040.
Now let's look at the Fibonacci function.
Notice the handling of the bass cases.
If n is less than or equal to 1, then we simply return n.
So when n is 0., we return 0.
And when n is 1, we return 1.
That handles both base cases in one step.
We could easily rewrite this condition to explicitly check
n equals 0 and n equals 1, but this achieve the same result.
This base cases with stops the recursion.
If n is not 0 or 1, then we call Fibonacci again with both
pieces of the problem definition.
Eventually, recursion will stop and the result will be returned to main.
Notice how much the code looks like the mathematical
definition of Fibonacci.
This is by design.
Let me give you a few thoughts on recursion.
Remember, recursion is a form of iteration.
So anything that can be done recursively can also be done with
the iteration and vice versa.
Use recursion only when it makes sense.
The problem must lend itself to a recursive solution.
Don't use recursion to count from 1 to 10.
Remember the base cases.
They are with stops the recursion and are super important.
Because of the call stack, recursion can be quite
resource-intensive especially if you have a very deep recursion.
It's not uncommon when you're first learning recursion to recusing
definitely and run out of stacks space resulting in a stack overflow error.
That's perfectly fine.
This is how you learn.
I can't tell you how many times in my career I've seen recursive
functions rewritten to iterative solutions because of resource issues.
Generally, an iterative solution to a recursive define problem
is less elegant and more difficult to understand in code.
But sometimes we have to meet non-functional requirements
and that's what it takes.
Let's head over to the IDE and walk through a factorial example in detail.
So I'm in the IDE.
I'm in the section 11 workspace.
And there are two projects that are interesting here,
both use recursive functions.
When is the Fibonacci project to me, that's a factorial project.
We'll walk through a detailed example of how factorial
works recursively in a minute.
But here's Fibonacci, and it's just like I wrote in the slides.
So here in the man, I'm calculating the Fibonacci number for 5 30 and 40.
You can see the 40 is pretty large.
If you try to do like a Fibonacci a 50 or something like that, it's
going to take a while because there's a lot of recursion going on.
It all depends on how fast your machine is.
Even here when I do a Fibonacci 40, I'll run this.
And you will see a little bit of a delay.
You see that it took just over a second delay their to actually
calculate that Fibonacci number.
It's a pretty large number.
But once you start getting to really large numbers here,
for example, 45 50, then the recursion just tremendous, and it takes a
while to solve those problems.
Okay, so let me go back to Factorial.
That's the one I really want to go over here.
So here's the factorial.
Just like we wrote it, the factorial of some number and
those four examples here.
You can see factorial 63.
Factorial 8 is 4320 and so forth.
You can see the factors of 20 is a really big number.
And as this number grows here, that never really grows big time.
So let me run.
This and you could see it's really fast here.
But once you start really increasing that number there,
it's going to slow down big time.
Now what I want to do is I want to -- I'm going to comment these
out just for a minute because I'm only interested in factorial of 3.
I want to walk through a stack example of exactly what's going on
when we call factorial with a 3.
We could do a 4 or 5 or 6.
If we did that, we'd be here all day drawing stuff on the
stack because of the recursion.
3 is an easy number.
It'll be pretty easy to do on a stack, and it won't take so long.
But you'll understand exactly what's happening and whether you
use 3 or 4 5, you'll understand.
Okay, so let's do that now.
Okay, so here's my stack.
And my main is on the stack, and all main is doing is it's out putting
the result of factorial with a 3.
So I'm just going to use fact rather than right out
the entire work factorial.
So main is calling factorial with a 3.
And the resulting gets back, it's going to output, right.
Okay, so that's simple enough.
So what happens?
Well, main calls that function factorial, right.
So we're going to activate that function, and we'll
put it on the stacks.
So main is going to call factorial with the 3.
So here's the activation record for factorial from this
call right here from main.
Notice a factorial function right here has one local variable n.
So we need to allocate storage for it.
And it's say that that's in right here.
And what's the value for n?
Well, in this case, it's 3, right.
I'm passing 3 into this function.
So n is going to get a 3.
And I'm going to write the code right here in the stack.
The code doesn't exist on the stack.
It exists somewhere else, but here you'll be able to
follow it easier I think.
So what do we do?
We start executing the code.
Is n equal to 0.
No, n is equal to 3.
So, what do I do?
I return -- I'm just going to write n which is 3 x factorial of in -1.
Well, 3 - 1 is 2.
So we need to call that function.
So what do we do?
Again, we transfer control to the other function.
What are the function is it?
It's the same one.
We're just calling to recursively.
So in this case, what am I doing?
I'm calling factorial with the 2.
Factorial has an n.
So we need to allocate storage for an n.
It's just another activation record.
In this case, n is 2.
Let's start executing.
Is n equal to 0, No.
So I want to return n which is 2 x factorial of n - 1, well, 2 - 1 is 1.
so I'm going to do that.
Now notice what just happened.
I've got to activation records on the stack for the same function.
That's the definition of recursion.
All right, so now what are we doing?
We're going to call factorial with a 1.
And you could see the stack just growing, right.
Well, factorial is the same function, it's got an n.
In this case, I'm calling it with the 1.
I'm passing the by value.
So there's the 1.
And what does it do?
Is n equal to 0, nope.
So it's going to return n, which is 1 x factorial of
and - 1 which in this case is 0.
So what do I do?
Again, I stopped and I call factorial again in this case with the 0.
So let's do that.
Well, here, we're going to call factorial with a 0 and gets a 0.
Now we're here.
This is the base case.
Finally, we're going to start unwinding.
Is n equal to 0?
Yes.
So what do I do?
I return 1.
Return 1 to who.
Whoever called me.
Well, here's the call, right here.
So the value of that call will be 1.
Okay, and now what we do is we start unwinding.
So this gets popped off the stack.
And now we're here.
Well, this guy cannot return as well, right?
So it's going to return what.
It's going to return 1 x 1, 1 x 1 2 to this guy right here.
So 1 x 1 is 1.
And we're going to pop off the stack.
So this function now is gone.
That activation record gets cleaned up, and we're here, right.
So hopefully, everybody's with me.
It's pretty straightforward.
It's just a matter of keeping all your ducks in a row.
So here, we're going to return 2 x 1 which is 2 to this function call.
That's the value of that function call.
That's the 2.
And again, we're going to clean up the stack and gets popped off.
That activation record all was -- all those areas in the
stack that we allocated are gone.
So now we're here.
Finally, we can calculate this result which is 3 x 2 which is 6.
So we're going to return 6 to who, this guy is the one that called me.
That's a 6 right there, right.
The value of that function call is a 6.
What are we going to do now?
Pop off the stack.
We're cleaning up finally.
See that's the that's called unwinding from a recursive call.
So we're here.
Now we've got us 6.
And what do we do with the 6?
We out put it.
And that's the final result of the call to factorial with a 3 days.
You can see it's pretty straightforward.
It's a matter of your recursive calls -- pushed on the stack
and then you start unwinding.
The unwinding is starting right there.
That's the critical piece, that bass case.
If you forget that bass case or get it wrong, then this will just
keep going and going and eventually you're going to run out of stack
space and get a stack overflow error.
Okay, so there you go.
Obviously, if you remember the Fibonacci function, it's more
complicated than this, right, because then he had to go back to
this so you can see the Fibonacci function, which was right here has
two pieces of recursion, right.
So we're going to have to call recursive functions calling
itself obviously, but it's calling it twice per call.
So the amount of stack space it's used is larger.
That's why Fibonacci takes longer than factorial to execute,
especially with very large numbers.
Okay, so hopefully this diagram helps.
Recursion makes a lot of sense.
Once you understand what's really going on on the stack,
I think it totally makes sense.