1
00:00:00,670 --> 00:00:01,290
Welcome back.

2
00:00:02,020 --> 00:00:07,090
I'm about to show you my favorite animation of the course, I'm very proud of it, so don't laugh at

3
00:00:07,090 --> 00:00:08,280
me if you think it's silly.

4
00:00:08,920 --> 00:00:17,680
I like to think of recursion as this scenario where you have this tap pouring water into a glass for

5
00:00:17,680 --> 00:00:21,330
this little man that's sitting on the couch watching TV.

6
00:00:22,150 --> 00:00:27,310
And what I think about recursion, I like to think that they have two big problems.

7
00:00:28,760 --> 00:00:35,960
One is that, well, they're kind of difficult to understand at first, the second is that we can have

8
00:00:35,960 --> 00:00:41,540
a case like this where I'm pouring water into a glass, I'm pouring water into a glass and pouring water

9
00:00:41,540 --> 00:00:42,170
into a glass.

10
00:00:42,320 --> 00:00:47,840
And that is me calling the function over and over and over.

11
00:00:48,440 --> 00:00:54,020
And as we keep going, as we keep going, fills up the cup past its limit, it keeps going.

12
00:00:54,020 --> 00:00:54,890
It doesn't stop.

13
00:00:54,890 --> 00:00:57,890
It keeps calling the function, keeps calling the function until.

14
00:00:58,280 --> 00:01:00,770
Oh, boy, the man has drowned.

15
00:01:01,910 --> 00:01:06,590
What just happened here, this is called Stack Overflow.

16
00:01:07,130 --> 00:01:08,210
Let's go back to some code.

17
00:01:09,880 --> 00:01:12,670
Remember the function inception that we created?

18
00:01:13,890 --> 00:01:15,630
If I run this function.

19
00:01:18,160 --> 00:01:19,840
And I say Inception.

20
00:01:22,620 --> 00:01:26,310
And simply run this function, I'll get an error.

21
00:01:27,120 --> 00:01:29,190
Let's make this a little bit bigger to see.

22
00:01:30,190 --> 00:01:38,110
I get an error saying maximum call stack size exceeded my browser, in this case, Google Chrome is

23
00:01:38,110 --> 00:01:42,570
smart enough to say, all right, you got to stop this madness.

24
00:01:42,580 --> 00:01:49,390
I'm just calling this inception function over and over and over and over, because remember, our function

25
00:01:49,390 --> 00:01:54,990
just calls itself and eventually, if Google Chrome doesn't stop this, it's going to crash.

26
00:01:55,240 --> 00:01:57,190
And in the past, that's what would happen.

27
00:01:57,190 --> 00:02:01,300
If I run this function, the browser will crash and I would have to restart it.

28
00:02:01,660 --> 00:02:07,540
But they've added a safeguards here saying, hey, you've called the maximum cost size.

29
00:02:08,020 --> 00:02:09,390
You got to stop what you're doing.

30
00:02:10,180 --> 00:02:13,090
Now, this is called stack overflow.

31
00:02:16,120 --> 00:02:17,800
Let's dive deeper into this topic.

32
00:02:18,760 --> 00:02:25,900
Just going to clear the console here and right our inception function, but this time I'm going to add

33
00:02:25,900 --> 00:02:28,450
a keyword called debugger.

34
00:02:29,500 --> 00:02:36,040
That the Chrome browser is going to detect and pause the function when it sees this word.

35
00:02:37,040 --> 00:02:38,540
So I'm going to.

36
00:02:39,830 --> 00:02:40,790
Run this function.

37
00:02:43,270 --> 00:02:49,030
And you'll notice that as soon as I hit enter, it's going to stop and give me a little panel here where

38
00:02:49,030 --> 00:02:50,230
I can control the function.

39
00:02:50,740 --> 00:02:51,520
Let's hit enter.

40
00:02:52,830 --> 00:02:56,130
And there you go, I'm in now the debugger mode.

41
00:02:57,570 --> 00:03:05,660
And you'll see here a few things, one, it'll show me where I am in the function and also show me changes

42
00:03:05,910 --> 00:03:07,810
around just so it's a little bit cleaner.

43
00:03:07,830 --> 00:03:09,420
I'm going to make this a little smaller.

44
00:03:09,480 --> 00:03:10,040
There you go.

45
00:03:10,770 --> 00:03:15,820
You see here something called call stack now from the name Stack Overflow.

46
00:03:16,110 --> 00:03:20,100
This might give you a bit of a hint right now.

47
00:03:20,100 --> 00:03:23,220
We've called the inception function right here.

48
00:03:23,670 --> 00:03:24,330
We have an.

49
00:03:25,340 --> 00:03:31,940
Called it the second time around, if I click on the step over icon over here, it's going to go to

50
00:03:31,940 --> 00:03:34,750
the next line of a code, it's going to go to the next.

51
00:03:35,090 --> 00:03:38,120
And now it's going to call the next inception function.

52
00:03:39,270 --> 00:03:41,250
Have a look over here at the call stack.

53
00:03:42,760 --> 00:03:44,860
As to what's going to happen next.

54
00:03:47,500 --> 00:03:51,760
Do you see that I just added another function on the call stack?

55
00:03:52,680 --> 00:04:00,350
And as we know about STAC data structure, we're just adding the function call on top of the other one,

56
00:04:00,690 --> 00:04:06,000
and if I step over here and go again, that's a third function call.

57
00:04:06,180 --> 00:04:08,270
And if I keep going, keep going, keep going.

58
00:04:08,400 --> 00:04:13,530
You'll see that I'm just adding more and more and more things to the stack.

59
00:04:14,250 --> 00:04:15,690
But there's a problem here, right?

60
00:04:16,200 --> 00:04:19,520
Nothing's getting popped from the stack.

61
00:04:20,190 --> 00:04:25,260
Instead, the function just keeps running, keeps running, keeps running, keeps running, keeps running

62
00:04:25,500 --> 00:04:29,550
until we run out of memory here.

63
00:04:29,880 --> 00:04:37,320
Remember, Stack in this case is grabbing a piece of memory from our computer and adding inception to

64
00:04:37,320 --> 00:04:37,890
the stack.

65
00:04:38,430 --> 00:04:40,350
And as you know, memory is limited.

66
00:04:40,350 --> 00:04:41,770
We don't have infinite amount.

67
00:04:42,150 --> 00:04:46,980
So as we keep going, as we keep going, it's going to stack overflow.

68
00:04:47,910 --> 00:04:54,840
And throw in there, and this is one of the biggest problems with recursion that we're going to get

69
00:04:54,840 --> 00:05:01,530
into later on, as you see here, though, it can be very, very dangerous because we can run programs

70
00:05:01,770 --> 00:05:09,030
that overflow, that never stop, that have infinite loops, essentially that crash our programs.

71
00:05:09,750 --> 00:05:13,140
You'll also see here that this costs memory.

72
00:05:13,560 --> 00:05:18,930
A stack is holding these function calls and recursion.

73
00:05:18,930 --> 00:05:26,250
One of its downside is that we have to hold on to these calls and remember them one by one, which can

74
00:05:26,250 --> 00:05:27,540
get really expensive.

75
00:05:28,200 --> 00:05:34,470
So if you ever get asked this question in an interview about recursion, maybe a possible problem with

76
00:05:34,470 --> 00:05:42,750
recursion, you can simply say, well, the computer needs to allocate memory to remember things stack

77
00:05:42,750 --> 00:05:48,870
overflow can occur when we have recursion and there's no way to stop this recursive.

78
00:05:48,870 --> 00:05:55,140
Call it simply the computer saying, whoa, whoa, whoa, whoa, OK, this is getting silly.

79
00:05:55,140 --> 00:05:56,970
I'm not remembering any more things.

80
00:05:56,970 --> 00:05:58,040
I'm out of memory.

81
00:05:58,560 --> 00:06:00,450
I'm going to just write.

82
00:06:01,910 --> 00:06:06,680
In the next video, we're going to try and solve this problem and learn about something called a base

83
00:06:06,680 --> 00:06:13,760
case, I think that you have to have in a recursive function to stop it from doing this.

84
00:06:14,630 --> 00:06:15,560
I'll see in the next one.