Placeholder Image

Subtitles section Play video

  • 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.

In order to understand recursion, you must

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

A2 US factorial recursive node base recursion return

Recursion

  • 169 16
    Jjli Li posted on 2016/07/06
Video vocabulary