>> ZAMYLA: In order to understand recursion, you must
first understand recursion.
Having recursion in program design means that you have self-referential
definitions.
Recursive data structures, for instance, are data structures that
include themselves in their definitions.
But today, we're going to focus on recursive functions.
>> Recall that functions take inputs, arguments, and return a value as their
output represented by this diagram here.
We'll think of the box as the body of the function, containing the set of
instructions that interpret the input and provide an output.
Taking a closer look inside the body of the function could reveal calls to
other functions as well.
Take this simple function, foo, that takes a single string as input and
prints how many letters that string has.
The function strlen, for string length, is called, whose output is
required for the call to printf.
>> Now, what makes a recursive function special is that it calls itself.
We can represent this recursive call with this orange arrow
looping back to itself.
But executing itself again will only make another recursive call, and
another and another.
But recursive functions can't be infinite.
They have to end somehow, or your program will run forever.
>> So we need to find a way to break out of the recursive calls.
We call this the base case.
When the base case condition is met, the function returns without making
another recursive call.
Take this function, hi, a void function that takes an int n as input.
The base case comes first.
If n is less than zero, print bye and return For all other cases, the
function will print hi and execute the recursive call.
Another call to the function hi with a decremented input value.
>> Now, even though we print hi, the function won't terminate until we
return its return type, in this case void.
So for every n other than the base case, this function hi will return hi
of n minus 1.
Since this function is void though, we won't explicitly type return here.
We'll just execute the function.
So calling hi(3) will print hi and execute hi(2) which executes hi(1) one
which executes hi(0), where the base case condition is met.
So hi(0) prints bye and returns.
>> OK.
So now that we understand the basics of recursive functions, that they need
at least one base case as well as a recursive call, let's move on to a
more meaningful example.
One that doesn't just return void no matter what.
>> Let's take a look at the factorial operation used most commonly in
probability calculations.
Factorial of n is the product of every positive integer less than
and equal to n.
So factorial five is 5 times 4 times 3 times 2 times 1 to give 120.
Four factorial is 4 times 3 times 2 times 1 to give 24.
And the same rule applies to any positive integer.
>> So how might we write a recursive function that calculates the factorial
of a number?
Well, we'll need to identify both the base case and the recursive call.
The recursive call will be the same for all cases except for the base
case, which means that we'll have to find a pattern that will give us our
desired result.
>> For this example, see how 5 factorial involves multiplying 4 by 3 by 2 by 1
And that very same multiplication is found here, the
definition of 4 factorial.
So we see that 5 factorial is just 5 times 4 factorial.
Now does this pattern apply to 4 factorial as well?
Yes.
We see that 4 factorial contains the multiplication 3 times 2 times 1, the
very same definition as 3 factorial.
So 4 factorial is equal to 4 times 3 factorial, and so on and so forth our
pattern sticks until 1 factorial, which by definition is equal to 1.
>> There's no other positive integers left.
So we have the pattern for our recursive call.
n factorial is equal to n times the factorial of n minus 1.
And our base case?
That'll just be our definition of 1 factorial.
>> So now we can move on to writing code for the function.
For the base case, we'll have the condition n equals equals 1, where
we'll return 1.
Then moving onto the recursive call, we'll return n times the
factorial of n minus 1.
>> Now let's test this our.
Let's try factorial 4.
Per our function it's equal to 4 times factorial(3).
Factorial(3) is equal to 3 times factorial(2).
Factorial(2) is equal to 2 times factorial(1), which returns 1.
Factorial(2) now returns 2 times 1, 2.
Factorial(3) can now return 3 times 2, 6.
And finally, factorial(4) returns 4 times 6, 24.
>> If you're encountering any difficulty with the recursive call, pretend that
the function works already.
What I mean by this is that you should trust your recursive calls to return
the right values.
For instance, if I know that factorial(5) equals 5 times
factorial(4), I'm going to trust that factorial(4) will give me 24.
Think of it as a variable, if you will, as if you already defined
factorial(4).
So for any factorial(n), it's the product of n and
the previous factorial.
And this previous factorial is obtained by calling
factorial of n minus 1.
>> Now, see if you can implement a recursive function yourself.
Load up your terminal, or run.cs50.net, and write a function sum
that takes an integer n and returns the sum of all consecutive positive
integers from n to 1.
I've written out the sums of some values to help you our.
First, figure out the base case condition.
Then, look at sum(5).
Can you express it in terms of another sum?
Now, what about sum(4)?
How can you express sum(4) in terms of another sum?
>> Once you have sum(5) and sum(4) expressed in terms of other sums, see
if you can identify a pattern for sum(n).
If not, try a few other numbers and express their sums in
terms of another numbers.
By identifying patterns for discrete numbers, you're well on your way to
identifying the pattern for any n.
>> Recursion's a really powerful tool, so of course it's not limited to
mathematical functions.
Recursion can be used very effectively when dealing with trees for instance.
Check out the short on trees for a more thorough review, but for now
recall that binary search trees, in particular, are made up of nodes, each
with a value and two node pointers.
Usually, this is represented by the parent node having one line pointing
to the left child node and one to the right child node.
The structure of a binary search tree lends itself well
to a recursive search.
The recursive call either passes in the left or the right node, but more
of that in the tree short.
>> Say you want to perform an operation on every single node in a binary tree.
How might you go about that?
Well, you could write a recursive function that performs the operation
on the parent node and makes a recursive call to the same function,
passing in the left and right child nodes.
For example, this function, foo, that changes the value of a given node and
all of its children to 1.
The base case of a null node causes the function to return, indicating
that there aren't any nodes left in that sub-tree.
>> Let's walk through it.
The first parent is 13.
We change the value to 1, and then call our function on the left as well
as the right.
The function, foo, is called on the left sub-tree first, so the left node
will be reassigned to 1 and foo will be called on that node's children,
first the left and then the right, and so on and so forth.
And tell them that branches don't have any more children so the same process
will continue for the right children until the whole tree's nodes are
reassigned to 1.
>> As you can see, you aren't limited to just one recursive call.
Just as many as will get the job done.
What if you had a tree where each node had three children,
Left, middle, and right?
How would you edit foo?
Well, simple.
Just add another recursive call and pass in the middle node pointer.
>> Recursion is very powerful and not to mention elegant, but it can be a
difficult concept at first, so be patient and take your time.
Start with the base case.
It's usually the easiest to identify, and then you can work
backwards from there.
You know you need to reach your base case, so that might
give you a few hints.
Try to express one specific case in terms of other cases, or in sub-sets.
>> Thanks for watching this short.
At the very least, now you can understand jokes like this.
My name is Zamyla, and this is cs50.
>> Take this function, hi, a void function that takes
an int, n, as input.
The base case comes first.
If n is less than 0, print "bye" and return.