1
00:00:06,880 --> 00:00:09,370
I hope you've enjoyed this section on recursion.

2
00:00:09,640 --> 00:00:15,910
We are now going to have an assignment to really solidify our learning of recursion.

3
00:00:16,510 --> 00:00:21,220
For this assignment we are going to execute the some triangle of array problem.

4
00:00:21,700 --> 00:00:28,060
And what this problem is, is we're going to have a vector of integers and we're going to print a sum

5
00:00:28,060 --> 00:00:29,710
triangle from it.

6
00:00:30,190 --> 00:00:34,360
So in order to get a better understanding of this, let's walk through the problem.

7
00:00:35,110 --> 00:00:41,440
So as I said, one of the first things that we are going to have is a vector of integers.

8
00:00:41,890 --> 00:00:51,940
So we'll call our vector a and we will say inside this vector we have one, two, three, four and five.

9
00:00:52,840 --> 00:01:01,240
And in this case, let's just go ahead and look at the output of what we would expect, a proper function

10
00:01:01,720 --> 00:01:05,350
function to print for us.

11
00:01:05,890 --> 00:01:16,150
So we will have 48 And then on a another line we'll have 20 and 28 and below that we'll have eight,

12
00:01:16,360 --> 00:01:23,710
12, 16 and then we'll have three, five, seven, nine.

13
00:01:24,010 --> 00:01:30,730
And our last line will be one, two, three, four and five.

14
00:01:31,150 --> 00:01:38,320
So you might be wondering how we generate the line preceding above it.

15
00:01:38,770 --> 00:01:42,370
Well, if we look at this, we will see we have one plus two.

16
00:01:43,060 --> 00:01:48,040
Equals to three to plus three is equal.

17
00:01:48,820 --> 00:01:49,720
Five.

18
00:01:51,130 --> 00:01:58,960
Three plus four equals seven and four plus five equals nine.

19
00:01:59,380 --> 00:02:03,430
So three, five, seven, nine.

20
00:02:03,610 --> 00:02:05,080
And that is our next line.

21
00:02:05,980 --> 00:02:10,090
In this line we will do three plus five equals eight.

22
00:02:11,410 --> 00:02:14,920
Five plus seven equals 12.

23
00:02:15,460 --> 00:02:19,510
And then seven plus nine equals 16.

24
00:02:21,490 --> 00:02:24,490
And as you can see, this equals the next line.

25
00:02:24,700 --> 00:02:34,840
And now we will have eight plus 12 equals 20, and 12 plus 16 equals 28.

26
00:02:35,560 --> 00:02:42,700
And then our final line is 20 plus 28 is equal to 48.

27
00:02:43,420 --> 00:02:46,630
So that is how we generate the output.

28
00:02:47,260 --> 00:02:51,160
So if we want to do this recursively, what should our approach be?

29
00:02:51,190 --> 00:02:55,060
Well, obviously, recursion is the key to solving this.

30
00:02:55,660 --> 00:03:00,250
And then at each iteration, you will want to create a new array.

31
00:03:00,250 --> 00:03:07,720
So a temporary array which contains the sum of consecutive elements in the array that was passed in

32
00:03:07,720 --> 00:03:09,160
as the parameter.

33
00:03:09,610 --> 00:03:16,090
And then you're going to want to make a recursive call and pass the newly created array in the previous

34
00:03:16,090 --> 00:03:16,780
step.

35
00:03:16,990 --> 00:03:21,820
And then when we are backtracking, we want to print the array in reverse order.

36
00:03:22,210 --> 00:03:27,160
So what does our steps Recursion?

37
00:03:29,290 --> 00:03:32,500
Obviously, because that is what this assignment is all about.

38
00:03:33,100 --> 00:03:40,090
And then so at each iteration, at each iteration.

39
00:03:42,980 --> 00:03:48,830
Create a temp.

40
00:03:49,320 --> 00:03:52,100
I'm underlining it because this is a very important step.

41
00:03:53,300 --> 00:03:57,680
Array or vector that.

42
00:03:59,880 --> 00:04:01,140
Contains.

43
00:04:03,390 --> 00:04:03,900
This.

44
00:04:06,270 --> 00:04:08,520
Of consecutive.

45
00:04:10,950 --> 00:04:11,600
Due to.

46
00:04:14,480 --> 00:04:15,710
Elements

47
00:04:17,720 --> 00:04:19,970
in the.

48
00:04:22,990 --> 00:04:25,570
Array parameter.

49
00:04:26,050 --> 00:04:31,960
I'm a short net, so what I mean by contains the sum of consecutive elements in the rate parameter and

50
00:04:31,960 --> 00:04:36,370
the first array that was passed in, we passed in one, two, three, four and five.

51
00:04:36,370 --> 00:04:43,030
So the sum of consecutive elements would be one plus two, two plus three, three plus four, four plus

52
00:04:43,030 --> 00:04:43,600
five.

53
00:04:44,290 --> 00:04:52,180
So you can think of that as I plus I plus one and then store this value and then I would go up.

54
00:04:52,180 --> 00:04:54,370
So now it's I plus I plus one.

55
00:04:54,910 --> 00:05:00,310
And we just continue on doing that and then we want to make recursive call.

56
00:05:02,980 --> 00:05:04,060
Recursive.

57
00:05:06,470 --> 00:05:06,890
Call.

58
00:05:08,600 --> 00:05:10,190
And pass in our new array.

59
00:05:13,800 --> 00:05:16,830
Passing the temp.

60
00:05:18,380 --> 00:05:18,900
Ray.

61
00:05:20,970 --> 00:05:32,700
And then print erase when backtracking a.k.a. unwinding the stack.

62
00:05:34,380 --> 00:05:37,830
That way it prints out in reverse order.

63
00:05:39,030 --> 00:05:40,830
So give this a go.

64
00:05:40,830 --> 00:05:46,980
And then in the next lecture, I will go over my solution to this problem.