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.