1
00:00:02,560 --> 00:00:07,150
So now that we learned a lot about closures and scope and so on,

2
00:00:07,480 --> 00:00:14,950
let's have a look at recursion which is a quite interesting pattern, a quite interesting way of using functions,

3
00:00:15,190 --> 00:00:19,770
which is not exclusive to Javascript but which you can use in any programming language.

4
00:00:19,780 --> 00:00:22,290
Let's start with a simple recursion.

5
00:00:22,330 --> 00:00:24,190
Let's say we want to create a function,

6
00:00:24,460 --> 00:00:28,270
power of which should calculate the power of something

7
00:00:28,570 --> 00:00:35,470
and this function should get two arguments - the value and then the power which we want to use, so that

8
00:00:35,470 --> 00:00:47,770
we for example can run power of two and three and what we would get is the result of two times two times

9
00:00:47,770 --> 00:00:48,340
two,

10
00:00:48,340 --> 00:00:48,760
right,

11
00:00:48,760 --> 00:00:49,950
which would be eight,

12
00:00:49,990 --> 00:00:52,830
that's two at the power of three.

13
00:00:52,930 --> 00:00:54,740
So this is what this function should do.

14
00:00:54,910 --> 00:01:03,520
Now a first implementation could simply start with a result of one and then use a for loop where

15
00:01:03,520 --> 00:01:12,370
we go through all iterations that we need, so i smaller n and increment i

16
00:01:13,300 --> 00:01:24,110
and then in here, we change result to be equal to result times x or shortcut, like this and then in the

17
00:01:24,110 --> 00:01:27,380
end, we return the result.

18
00:01:27,380 --> 00:01:33,970
Now this calculates the power of x because what it does is it goes through this loop n times,

19
00:01:33,980 --> 00:01:38,990
so in this case here three times and every time, it takes the result where we start at one because we're

20
00:01:38,990 --> 00:01:42,020
doing a multiplication, starting at zero would be a bad idea,

21
00:01:42,650 --> 00:01:43,820
we would always get zero,

22
00:01:43,880 --> 00:01:48,110
so we start at one and then for the first iteration, i is zero

23
00:01:48,110 --> 00:01:50,840
but we don't really care about i, we just care about x..

24
00:01:50,930 --> 00:01:58,640
So in the end we take the old result which is 1 and multiply this with x which is 2 for this call here

25
00:01:58,700 --> 00:02:00,940
because the value for x is two.

26
00:02:01,070 --> 00:02:03,680
Then we go through this loop a second time,

27
00:02:03,710 --> 00:02:06,310
i is now one but n was three

28
00:02:06,320 --> 00:02:10,910
so we still go through that and our result is two from the first iteration,

29
00:02:10,940 --> 00:02:12,890
x is also still two

30
00:02:12,890 --> 00:02:19,070
so now we have two times two, we got four and now we go through that a third and last time because i is two

31
00:02:19,070 --> 00:02:21,380
now, n is still three

32
00:02:21,380 --> 00:02:26,430
so we go through that, result was 4, x still is 2, new result is 8.

33
00:02:26,540 --> 00:02:32,540
We don't go through this loop a fourth time because i now is three and so is n and hence the result gets

34
00:02:32,540 --> 00:02:32,980
returned.

35
00:02:33,200 --> 00:02:36,680
So if i save that and i reload, i get eight down there,

36
00:02:36,680 --> 00:02:38,980
that works as it should.

37
00:02:39,010 --> 00:02:45,650
Now we could implement it like this but with the concept of recursion, we can actually write this in

38
00:02:45,650 --> 00:02:47,070
a shorter way.

39
00:02:47,150 --> 00:02:51,410
So let me copy that and comment it out and let's try again.

40
00:02:51,410 --> 00:02:59,210
So here is another try of writing that power of function, this time with recursion. The idea behind a

41
00:02:59,210 --> 00:03:08,720
recursion or a recursive function is that the function calls itself. So we return x times and now we

42
00:03:09,110 --> 00:03:15,920
reference the same function here with a value for x but now with n - 1,

43
00:03:15,970 --> 00:03:17,920
so what's the idea here?

44
00:03:17,920 --> 00:03:25,660
Well when we call this function, we return x which is two times the same function call but with n

45
00:03:25,690 --> 00:03:26,580
minus one,

46
00:03:26,590 --> 00:03:32,970
so n is three here, we call the function again with a value of two for n because it's n - 1.

47
00:03:32,980 --> 00:03:41,050
So if this function then runs again, we get x two but n now also is two for this function call and it's that same

48
00:03:41,050 --> 00:03:42,190
function.

49
00:03:42,190 --> 00:03:47,710
So now again we have 2 times and now again, we call that same function again, this time again with n -

50
00:03:47,710 --> 00:03:48,010
1,

51
00:03:48,040 --> 00:03:52,630
so n was 2, minus 1 is n equal to 1.

52
00:03:52,630 --> 00:03:56,520
Again this function runs again, calls itself again here and so on

53
00:03:56,530 --> 00:03:59,490
so obviously this would lead to an infinite loop

54
00:03:59,500 --> 00:04:05,260
so we also need to specify some exit condition with an if statement where I check if n is equal to 1,

55
00:04:05,770 --> 00:04:09,430
then i want to return x actually,

56
00:04:09,460 --> 00:04:15,850
so then i want to return just x, i don't want to call myself again, otherwise and we don't need an else

57
00:04:15,910 --> 00:04:20,590
statement because if we return here, this won't execute anyways, we run this code.

58
00:04:21,160 --> 00:04:28,110
So if i save that, we again get a, we get no error or anything like that, we get the expected result.

59
00:04:28,200 --> 00:04:31,380
Still, it might not be super clear what's happening here.

60
00:04:31,590 --> 00:04:38,280
So to make that clearer, let's actually use the dev tools, dive into app.js and let's set a breakpoint

61
00:04:38,280 --> 00:04:38,790
here,

62
00:04:38,910 --> 00:04:44,510
let's set a breakpoint inside the power of function here.

63
00:04:44,520 --> 00:04:52,140
Now if i reload, this pauses and now let's expand this section down here and let's have a look

64
00:04:52,140 --> 00:04:54,550
at the call stack, we see in the call stack,

65
00:04:54,750 --> 00:04:58,140
there is one power of call because we just got started,

66
00:04:58,140 --> 00:05:01,740
the value for x is two, the value for n is three.

67
00:05:01,740 --> 00:05:05,820
So if we continue, we skip this if check because n is three

68
00:05:05,820 --> 00:05:08,840
so we don't make it into there and we're now in this line

69
00:05:08,850 --> 00:05:11,070
and now here, we call this function again.

70
00:05:11,100 --> 00:05:13,830
So now let's step into that function call.

71
00:05:14,070 --> 00:05:20,400
Now you see on the call stack, we have two power of calls, the first one with which we started

72
00:05:20,730 --> 00:05:23,670
and the second one and the difference can be seen here,

73
00:05:24,360 --> 00:05:27,700
n here it's three,

74
00:05:27,740 --> 00:05:31,630
here it is, for the one we're currently in, it's two.

75
00:05:31,760 --> 00:05:33,580
So the same function executes again

76
00:05:33,590 --> 00:05:38,830
but of course it's a different execution, we got two ongoing executions. The first one is paused

77
00:05:38,840 --> 00:05:43,230
so to say because it waits for the result of the second execution,

78
00:05:43,220 --> 00:05:45,760
so now let's see what the second execution does.

79
00:05:45,860 --> 00:05:50,780
N is two so we still skip this if check and we call ourselves again,

80
00:05:50,780 --> 00:05:53,890
so let's step into that function call and now

81
00:05:53,900 --> 00:05:59,240
n is one for that third function call, we got three times the same function called on the call stack

82
00:05:59,270 --> 00:06:04,060
now. Now n is one so now we will actually make it into this if check,

83
00:06:04,070 --> 00:06:10,070
so if we step into there, we actually return and on the call stack, you will see that if i advance,

84
00:06:13,180 --> 00:06:17,620
we now get rid of one of the function calls, instead

85
00:06:17,620 --> 00:06:20,820
now this function call for the second one,

86
00:06:20,830 --> 00:06:27,010
so the third one which was triggered by the second one, returned a value, it returned a value which we

87
00:06:27,010 --> 00:06:29,300
now use in that second call.

88
00:06:29,320 --> 00:06:35,110
So now if we continue, we're back in the first function call where we started everything

89
00:06:35,110 --> 00:06:37,680
and if we now continue, we're done

90
00:06:37,870 --> 00:06:41,710
and the overall result of this function called will be 8.

91
00:06:41,740 --> 00:06:46,630
So this is the idea of recursion, we call ourselves and why is this now better than a loop?

92
00:06:47,080 --> 00:06:51,900
Well simply because it's shorter. As you will also see in the next lecture,

93
00:06:51,940 --> 00:06:53,050
it's not just shorter,

94
00:06:53,080 --> 00:06:55,330
it can also help us with other problems

95
00:06:55,420 --> 00:07:00,700
but here already we can save some space because we can even write this in a shorter way.

96
00:07:00,730 --> 00:07:06,430
This is the more understandable way, the shortest possible way would be to return a ternary expression

97
00:07:06,850 --> 00:07:14,740
where we check n equal one and if that is the case, we return x which we do here as well,

98
00:07:14,740 --> 00:07:18,880
otherwise we perform this operation.

99
00:07:18,880 --> 00:07:23,730
So now we got one line where we previously needed a for loop,

100
00:07:23,860 --> 00:07:25,570
that's the power of recursion,

101
00:07:25,570 --> 00:07:30,340
it can save us code and it can do more than that as you'll see in the next lecture.