[MUSIC]

Previously, we talked about scopes.

Scopes are a way of encapsulating where the name of a variable will work.

A scope defines a region in which you can reference a variable,

and it also declares a namespace.

We said scopes can be bounded, scopes are ordered, and

that scopes define a namespace.

I want to talk about something that's kind of similar in that,

there's a scoping aspect going on.

And this similar concept is called frames but

frames apply specifically to functions.

So at a high level a new frame is created each time a function is called,

and each time a function returns a frame is destroyed.

So a frame represents the run time execution of a function.

As opposed to just the function definition in code which sort of exists in a file.

The frame represents the function actually happening.

Actually being executed on a computer.

So if we look over here at this collection of box and line diagrams

showing the really refactored version of our little toy example,

where main calls dayGreeting, dayGreeting calls allDay and allDay calls goodDay.

We know that it has a parallel in code and then it forms a stack,

a stack of function executions that sort of line up one on top of each other.

We said this is called the stack.

Well, what is a stack?

It turns out that a stack is a stack of frames.

So in this case,

those function calls correspond directly to the code that we executed.

The bottom level is the main function.

The main function calls dayGreeting.

dayGreeting will go through loops a number of times and call allDay.

And, so, this stack on the side represents not all the executions of a function but

moment in time when goodDay is being called.

We know that when goodDay returns and allDay returns,

dayGreeting may call allDay again, and many times as part of the loop.

But at any given time, there's only one stack of frames that has been created and

when those functions return they get destroyed.

So the stack, the stack is a stack of frames.

And each time a frame is called it also, each time a function is called,

it creates both a frame and a scope.

They're two different things, but when a function is called, it creates both.

And then scopes can also be declared through curly braces separately.

And in fact you can kind of think of the curly braces,

the single set of curly braces of the outermost edge of a function

as being almost equivalent of defining a frame.

So, and here's an example.

Our dayGreeting function,

those function inputs are going to become part of the scope.

So we didn't really touch on that a lot, but those curly braces define a scope,

and the variable loops is actually declared outside those curly braces.

But, because of the syntax,

loops is placed within the namespace of the brackets that follow it.

That happens when dayGreeting creates a frame.

But, it's not the only place where sometimes variables,

through syntax, are moved into the curly braces.

For example, the loops variable in dayGreeting is accessible there,

but this also happens in for loops, so for example, in this for loop here,

the variable int i has been declared technically outside those curly braces,

but because of the syntax of C,

i is accessible within the curly braces, all right.

So that's just a reflection on the fact that sometimes the syntax

will move variables into the curly braces, into the scope of the curly braces.

In this case, we didn't actually use the variable i within the curly braces, but

we could have.

All right, when you debug a program,

meaning when you stop a program to look at how its running in the middle of it,

in order to make sure it's functioning correctly.

This is something that a developer does not an end user does.

When you debug a program you stop it in mid execution, and because of that,

because all a computer is is a sequence of function calls.

When you stop it, you get a snapshot of the frames, and the variables that

have been defined within the scope of that frame, at any given moment.

So let's take a look at doing that in an actual running example of our code.

So we're looking at the code here that we've been working with in this lecture,

where we have a main function that calls a dayGreeting with a parameter of how

many days we want to print out to the screen.

dayGreeting runs a loop which internally calls allDay.

allDay then calls the function goodDay, and

goodDay prints out the time of day to the screen.

So what I'm going to do is I'm going to come over here and

double-click in this vertical column on the left and what that's gonna do is,

it's gonna add a breakpoint.

When it's a dark blue like this, it means the breakpoint is active.

When it's a light blue, it means the breakpoint is inactive.

If I want to remove it altogether, I would right-click on it and

hit Delete Breakpoint, but for now, let's keep it active.

What I'm gonna do is I'm gonna run the program and

when the control flow of the program gets to this breakpoint, it's gonna stop.

And it's gonna enable me to look and

see the different frames that are present in the stack at a given moment.

And I can also walk through line by line and see what's happening in the code.

So, I'm gonna run it just as normal.

And the build is going to happen and the simulator's going to launch.

And it happens very quickly, so I'm sorry, this is a command line program so

there's no simulator.

It happens very quickly so what we see is that our breakpoint has been hit as

indicated by this green line and saying breakpoint over here.

And we can look over here in our navigator.

If we look under our debug pane in our navigator,

we can see that the thread that's running our code, located here, has

a stack that consists of a starting frame, our main function, which was called here.

Our main function called dayGreeting.

So daygreeting is next on the stack and then,

currently allDay is being run, and so allDay is on the stack.

What we can do is we can look and see within each one of those frames in

the scopes that it defines what variables are present and what their values are.

We call main, main call dayGreeting.

Well what's true about the variables in dayGreeting.

If we click on dayGreeting and then look down here in our lower navigation pane,

we can see that when allDay was called, loops was equal to 2.

Well that makes sense, because we called dayGreeting with 2.

And then we were going through this loop, and

on the current stack that we are executing, we can see that i equals 0.

Hm, that's interesting!

So now let's click on allDay.

If we click on allDay, we see that there's nothing down here, and

so that's because there are no variables defined within this frame, but

we can use these command buttons down here to debug the program in different ways.

This will execute the line and go to the next one within the current frame.

This will step into the next frame if necessary.

That means we'll call goodDay with morning and we'll step into it.

Let's click that one.

You can see that when we did that,

it added another frame to our stack, the one for goodDay.

There is a variable defined here, which is time of day which was passed.

We can see that that time of day is this string, morning.

And if we step over that call by clicking on this button here.

We'll see that time of day gets printed over on our console.

We get to the end of goodDay.

If we use this command here to step up in to the next frame or

continue executing our program until we leave this frame.

We'll see that our stack over here in the left gets smaller.

We come back to the function that we entered goodDay in.

We can now step over that line, and we can see that we go to afternoon.

We can step into that function, our stack grows, but

now time of day has a value of afternoon.

We can step over that line, good afternoon gets printed, we can step

over the end of goodDay which actually is the same thing as coming out of goodDay.

We come back to the line that we entered goodDay in and

now we move to our next line.

We see that that goodDay afternoon frame was removed from our stack.

And now, if we step into this call of goodDay,

we add another frame to our stack and, in this case, time of day equals evening.

And if we click one frame up on allDay,

we see there are no variables defined in that frame.

If we go to dayGreeting, we see that now loops is still equal to 0,

and i is still equal to 0, because we haven't come and executed another loop, so

let's go back to our highest frame, and

we'll execute out of that and we'll execute out of allDay.

And now we're in our loop and we can see that loop = 2, i = 0, and

we're back to dayGreeting as being our highest frame in our stack.

If we step over our loop, we can see that i increments down here, and

if I step over allDay, all three of those goodDay functions will get called.

Disable our breakpoint first.

Step over allDay.

We see that the next three phrases get passed.

We are back to our loop and now i = 1 and loops = 2.

We step over that line.

And 1 got added to i.

And so i was no longer less than loops and so we stepped out of dayGreeting.

And now when we step over this line we return to main and

our stack gets shorter by one frame.

And we can continue running until the next breakpoint or until we end our program.

And we can see that our program ends.

So, by using breakpoints, we can examine our frames,

we can look at our variables, and we can walk through our program line

by line to make sure that our logic is functioning the way that we hope it is.

This is called debugging a program.

Okay, so, a special case of a function call is called recursion, and

this is when a function within a function,

there is a call made to the same function that's running it.

So it's like calling itself.

It is calling itself.

Recursion is when a function calls itself.

Now this can be a problem if you aren't careful,

because even though you're calling yourself, a new frame still gets created.

So let's see what that looks like if we modify our programs.

Recursion is when a function calls itself.

So let's change our code so that a function calls itself.

The way we'll do that is just for the purposes of demonstration here,

we'll have allDay call allDay, with nothing as its parameter.

Just to eliminate confusion, we'll put comments,

we'll make these next three lines, comment them out, so that their not affected.

So now when we run this program,

what we'd expect is that main would call dayGreeting with a parameter of 2.

This loop would get run twice, but

the first time it gets called, allDay will get called.

And then within allDay, allDay will call itself.

And then it will call itself.

Over and over and over again.

In a sense, creating an infinite loop, but

each time that gets called, we're going to add another frame to our stack.

And since each frame uses a slight amount of memory,

very quickly we're going to run out of memory.

So let's see that happen.

Running the program.

And immediately, before we can even see anything happen,

we get this BAD ACCESS error.

We see that our stack has gotten very, very high with thousands and

thousands of frames.

That's because very quickly in the blink of an eye it used up so much memory that

the program just crashed, because it ran out of memory on the computer.

So let's run that again, but this time let's put a breakpoint in so

that we can see that happening.

Stop the current execution and run it again.

All right, as we expected, allDay got called the first time and

now before we call it again let's just go ahead and

step into that function, and step in again, and step in again.

And as you see,

each time we step into that function, a new frame is being added to the stack.

And we'll continue, continue, continue, and because there's no reason for

it to stop continuing.

It will never return from that function till we run out of memory.

So if we're continuing the program image and execution,

we'll see that happen again.

Oops, the breakpoint stopped it at the next time.

So let's disable that breakpoint and continue to run.

Recursion isn't actually used very often.

It's certainly not just a function calling itself directly.

So, if you do decide that you want to use it,

make sure that your recursive calls are surrounded by some kind of conditional

statement that will ensure that eventually your recursive call gets stopped.

So, let's look at two different functions that do the same thing.

One that does it kind of efficiently, not just kind of efficiently, one that

does it efficiently, and another one that does it inefficiently using recursion.

The task of these two functions is to multiply a number by 2, an integer by 2.

In the first case we have a function called timesTwoQuickly that

takes as input a number, and we simply multiply that by 2 and return the value.

Straight forward.

In the second case, timesTwoWithRecursion, what we do is we take a number and

if that number is 0, we return the value 0.

But if it's not 0,

we're going to call the function again with that number decremented by 1.

And whatever it gives back, we're gonna add 2 to it.

And so eventually after the number gets decreased enough,

we'll end up with the value 0.

And when times 2 with recursion returns from the call, 2 will be added to 0.

Then that frame will return and 2 would be added to 2.

Then that frame will return and 2 would be added to 4.

And then that frame will return and 2 would be added to 6 and so on and so

on until you get the final value that you were looking for.

Every time you make a call, it uses up a little bit of memory, and so

if you call timesTwoWithRecursion with a number that's two large,

probably something based on the stack frame that we saw in the previous video,

something over 300,000, you're gonna run out of memory.

Whereas the first example just isn't ever gonna run out of memory.

So let's take a look at what happens when we do that.

So just to demonstrate that recursion can be done effectively if you put

a conditional around the call to the function,

conditional around the call in the which a function calls itself,

I've modified a program just to demonstrate this.

We've created two functions, one which does timesTwoQuickly.

And one which does timesTwoWithRecursion.

The one that does timesTwoWithRecursion might be a little tricky if this

is the first time you've see something like this.

But we can see that when our program runs, we're going to assign the variable A,

the result of timesTwoQuickly, where we pass it 3.

3 is gonna be a signed number, and we're gonna return 2 times that number,

that kinda makes sense.

Then we'll put that answer out on the console using this printf, and

then we'll do the same thing with recursion.

And we'll call this recursive function.

When we call this, we're going to call it the parameter number, and

we're going to check to see if the number's 0.

If it is, we're going to stop.

Our recursion's going to end, but if it's not, we're going to return 2 times sorry,

2 plus, whatever 2 times 2 with recursion returns after we subtract 1 from number.

So each time we call this function recursively,

the number is gonna go down by 1 until it reaches 0.

And then, it will return 0.

And then, as we come off the frames as the frames pop off the stack, we'll add 2 for

each time the call was made, to ultimately get the right number, all right?

So let's do that, let's put a breakpoint in here, so

we can follow along as it goes, and run.

All right, so we stopped there,

let's step into timesTwoQuickly, we're going to return 2 times that number.

So A better get the value of 6.

Return back up the stack and we see that timesTwoQuickly it currently equals 0,

and if we step over that, A will get assigned the value of 6.

Terrific, we'll print that out to the console.

6, what we expected.

Now let's do the same thing with recursion.

We'll step into timesTwoWithRecursion and

we'll see by clicking on the stack over here that number currently equals 3.

That makes sense, we just called that.

And now, we're gonna walk over this conditional because number does not

equal 0.

And now, we're going to call this function recursively, but

now our number is going to be equal to one less.

So let's step into that function and we see we added another frame to our stack,

but this time number equals 2.

If we click here, we see number equals 3, but in our current frame, number equals 2.

Let's step over that conditional, and step in to the next function call,

recursive function call, this time number gets decremented again.

We see by clicking on the frames that we have three, two, one.

Okay, we'll step over that conditional cuz number's not equal to 0.

We'll call again the conditional in there.

Step into it.

If number equals 0 we're gonna return 0.

Now number does equal 0.

So we're gonna return the value of 0.

Let's step over this line, we'll return 0, so

the function doesn't get called recursively anymore, return up,

we'll get the value that that function returns, we'll add 2 to it, step up,

get the value that function returns, add 2 to it, step up, get 2, add 2 to the value

that that function call returned, each time popping one frame off the stack.

Going up, now we're back here and when we assign b we see b gets the value of 6.

And then we write it out to the console and end.

I didn't put a return line in the end of this.

So our output wasn't very pretty.

But we can see that our functions do what we expect.

One does it with recursion.

Now, I'm not showing you this in order to advocate using recursion, but

just to show you that recursion can be done

effectively if you put a conditional around the recursive function call.

In this case, I would definitely just multiply it by 2.

So in summary the stack is actually a series of frames.

Each frame uses a little bit of memory.

And you can run out of this memory with recursion.

A frame adds variables to a scope and other syntax does this too,

for example the for-loop.

And finally, you can examine the frames and the scopes in the debugger.

So, this is a introduction to the idea of frames and debugging.

[MUSIC]

Frames and Recursion (Video)

Foundations of Objective-C App Development

Meet the Instructors