• 13 minutes ago
Transcript
00:00First of all, we will see backtracking on Arrays, which means how we can backtrack on the recursive function in
00:08the form of recursive function, we are going to solve a question.
00:10This question is only to build understanding of backtracking. In the question, I will give an empty array, and this
00:17array will give me the size.
00:19I will give an array size, n is equal to 5. What I have to do is write a recursive
00:25function. First of all, my i is equal to 0 index, here 1 store.
00:31Then my i is equal to 1 index, here 2 store. Then my i is equal to 3 index, here
00:363 store. Then my i is equal to 4 index, here 4 store.
00:41i is equal to 5 index, here 5 store. How will this recursion be?
00:45How will this recursion be? If I visualize this recursion in a form of call stack, then I will make
00:50my main function here.
00:52The main function will be put on my recursive function. Then what will I do?
00:56Here i is equal to 0, here i will assign my value 1 to my index i is equal to
01:030.
01:03After that, this will be put on another recursive call, which means the same function will be called.
01:08And then i is equal to 1, then my value will be 2. Then another recursive call, which means i
01:14is equal to 2,
01:15I will have value 3. In this way, my recursive calls are coming up.
01:20And what will the last recursive call come? Some recursive calls come in.
01:24And my last recursive call will be called index is equal to 4, where I will assign value 5.
01:29Once i will assign value 5. Once i will assign value 5. Then what will i do?
01:32I will start going down this call stack.
01:34Because in my recursive return statement will come in.
01:37So, as i will go back here.
01:40The values i have assigned value 5. How will i assign value 5?
01:43I have assigned value 5.
01:46I have assigned value 5.
01:47Where will i assign value 5?
01:49Where will i assign value 5?
01:50So, in my recursive base case i have taken.
01:52Because i have taken the case that i have taken the case.
01:54Like i have taken the case.
01:54What did i learn?
01:55In recursive case.
01:56We have done many recursive.
01:57And i have done many recursive, from breaking and conquering.
01:59We will also know that my recursive base case goes up, up, up, up, up, up, up, up, up, up,
02:04up.
02:04So, what do i do?
02:05We start to return the case.
02:07So, as i have turned the case here.
02:10The job is that i will return from the time to this value.
02:14To take the time, i have to decrease the values.
02:15To take the value to minus two.
02:17so I will decrease this as I will do 3
02:21so I will return this here
02:23so I will decrease 4 to 2
02:25here I will decrease
02:27so I will decrease 3 to 1
02:30here I will return this
02:32so I will decrease 2 to 0
02:33and here I will return this
02:35on my main function
02:37so I will decrease 1 to 1
02:39so my final array
02:41what is the state of final array
02:43what is the state of final array
02:45in my final array
02:47I will have some elements
02:48first I will have minus 1
02:51then 0, then 1, then 2
02:53then 3
02:53what do I have to do?
02:56what do I have to do?
02:57what do I have to do my array?
02:58I have to do this array
03:01I need to do this array
03:03and I need to do this array
03:07when I have to do base case
03:08I will go back to the main function
03:11when I have a second time
03:12then what do I need?
03:13I need this array
03:16in which I have assigned every element
03:18which I have assigned the value
03:20every time I have done it
03:23once I write the code
03:24and then we understand
03:25that the backtracking
03:27is actually done
03:27now if I write the function
03:29then what do I have to do
03:30first of all the main function
03:31I have to create an array
03:33I will give this array
03:34I will give size
03:35new int
03:365
03:37now I will not assign values
03:40because I have to keep this array
03:41because I have to keep this array
03:42I have to keep this array
03:43which one will assign values
03:44is my recursive function
03:45so I will give a function
03:48public
03:48static
03:49void
03:50change
03:51array
03:51I will give this array
03:52because the array
03:53will constantly change
03:54in this array
03:56one parameter
03:57will be my array
03:58another parameter
03:59what do I need?
04:00another parameter
04:00is to traverse that array
04:02I need index
04:03to change which index
04:04value
04:05and what value
04:07to change
04:07I need to change
04:08two parameters
04:09one is my index
04:10i
04:11one is the value
04:13which I will assign
04:14to the index
04:15here
04:16what will I do
04:16I will call
04:17to the main function
04:17in my change array
04:19I will pass the array
04:21I will start
04:21from the index
04:220
04:23and the value
04:23will start
04:24with my 1
04:25what will I do
04:26in the beginning
04:27that my array is empty
04:28and all the value
04:290
04:300
04:300
04:300
04:35not
04:36there will
04:37be
04:38all these
04:39conditions
04:400
04:408今
04:41I
04:41will bring public
04:44static
04:45void
04:46print
04:46array
04:46let's
04:49crunch this
04:53backtracking
04:54function
04:54that Omega ch
04:56I will print my array elements because I will use it every time.
05:02I did not do anything in print array.
05:04There is a very simple loop.
05:06From zero to zero, where the value is stored in every index.
05:11I will print it.
05:13My work is to change the array.
05:15Then I will print it in my main function.
05:18What is the work of the change array function?
05:20There will be two steps in this function.
05:22One will be my base case.
05:25One will be my base case.
05:27The first is my base case.
05:29The second is my recursion part.
05:31We used to call recursion basics.
05:33What is the work?
05:35The work is nothing.
05:36It is not my recursion.
05:37The work is recursion.
05:38I will call recursion.
05:41What is recursion?
05:43I will assign my value to the array index.
05:47First of all, what will I do?
05:49I will assign my value to the Ith index.
05:53The array of I is equal to value.
05:57The value of Ith index will store my value.
06:00Now, as I have stored the current index value.
06:03After that, I will put recursive call for the array.
06:06I will call the change array.
06:08I will call the array of Ith index.
06:10I will call the value of Ith index.
06:13I will call the value of Ith index.
06:19I will increase the value of Ith index.
06:20Now, when that call comes back to my current level.
06:23What will I do?
06:24Then, I will decrease the value of Ith index.
06:30I will decrease the value of Ith index.
06:32I will decrease the value of Ith index by 2.
06:33I will assign it to the array of Ith index.
06:36This will be my recursion.
06:38What will I do?
06:40I will assign my value to the previous value.
06:42I mean 1, 2, 3, 4, 5.
06:44After that, I have added a call to the levels.
06:46Now, when the call comes back,
06:48the next steps will execute the call.
06:51The next steps,
06:52when the call comes back,
06:53when the call comes back,
06:55the next line will execute, which is this line.
06:58Now, when the line will execute,
06:59the value of every index,
07:00will be minus 2.
07:03And what is my base case?
07:04The base case is that the value of i,
07:06the value of i,
07:07which will equal.
07:09n is my array.length.
07:11Now, I have no index left too.
07:13What do I have to do here?
07:15I will print my array here,
07:16and then I will do return.
07:19I mean, what is my base case?
07:21And what is my main function?
07:23What is my last area?
07:24We are going to analyze this code.
07:26Let's run this code here.
07:30The base case is called 1, 2, 3, 4, 5.
07:34And the main function is called the array.
07:37After changing the area, that is minus 1, 0, 1, 2, 3. Now what are we going to do?
07:42One time we will analyze the call stack, we will analyze it very well
07:45that what our calls actually meant. So this is my code. This is my base case.
07:51And here I have done my recursion. First of all, I have changed the value.
07:55After that, I have performed my function call step.
07:59And after the function call, I have written the value
08:03and I have written the value to minus 2. When we come back,
08:06we are called backtracking step. So let's start.
08:10In the beginning, what values have passed from the main function?
08:13My array will come to the start of the whole array.
08:17And because the address by value is passed,
08:20or the reference by value is passed,
08:21so the array is indirectly passed by reference.
08:24I have done any changes on any level,
08:27it will show all the levels.
08:29In the beginning, I had passed 0 and passed as 1.
08:32So in the beginning, the function call will come to my change array.
08:37If this is my array, which is empty,
08:41I have 5 index.
08:43If i is equal to 0,
08:45then the value is equal to 1.
08:47What will I do here?
08:49I will assign my value to 1.
08:50Now what will happen?
08:52This function will call up.
08:54The base case will not be true.
08:56So I have done this work here.
08:58Now I will call up to the level.
09:01What will happen?
09:02The same function will call up to the level.
09:03The same function will be called.
09:05I is equal to 1 passed.
09:06Value is equal to 2.
09:07I will go to the value to 1.
09:09If I have my value to 2,
09:10then my value will come here.
09:12Then I will do this work again.
09:14Now I will add another call.
09:16Once I add another call,
09:17then I will add another stack frame.
09:19The same function will be called.
09:20I was equal to 2 passed.
09:22Value is equal to 3 passed.
09:23First, I will check that the base case is true.
09:25After I will change my index value.
09:28So I have assigned value to index as well as 2.
09:30So I have assigned to index as well.
09:31And then I will add 3.
09:32Now we will add change-array again.
09:35I will add another call from the above.
09:38So I have called the change-array.
09:39Now I will add i is equal to 3.
09:41And I will add value to 4.
09:42I is equal to 3.
09:44And I have added value as well as 4.
09:47As I have added value as well as 4,
09:49I will add change-array again.
09:50I need to call the change array, so I have another stack frame. I called the change array, i is
09:56equal to 4, value is equal to 5, so what will I do?
09:59I assign value 5 to the fourth index. This is my index, this is my value. Now what will happen?
10:06Now I will add another next call to my next level. CA, I called the change array, i is equal
10:13to 5, value is equal to 6.
10:15As i is equal to 5, what will happen? The length array is equal to 5, so my array will
10:22be equal to 5.
10:23What will I do in this case? I have to print my array. What will I do in the output?
10:28My array will print me 1, 2, 3, 4, 5, because these are my array values.
10:36Now what is my work? I have in the base case and I have printed my array, so now I
10:40will return.
10:41When I return, just like I came here from here, I mean I came to this level.
10:47Just like I came to this level, what will happen? The upper level will be completely empty.
10:53The upper level is completely empty. Now when I came to this level, where i is equal to 4,
10:58I have already executed this line. I have already executed this line.
11:02The value changed. The upper level has been added to the upper level, so this line is executed.
11:07So when I return to function call, I will come to this third line.
11:12Third line is this line. What will I perform here? I have to make my array of i value by
11:192.
11:20So I have to make my array of i is equal to 4. I have to make my array of
11:24i value by 2.
11:25So I will make my array of i value by 3.
11:28As the value is 3, what do I call this? I call this backtracking step.
11:33Backtracking means to come back, backtrack the same way.
11:37So when I come back, after the function call, the step always becomes backtracking.
11:45Backtracking is never before function call. It will always be after function call.
11:49Now I have to make my array of i value by 2, so I will return.
11:53As I return, I mean I will return here.
11:58What happened here? The upper stack frame is empty.
12:02This is also removed, this is also removed, this is also removed.
12:05Now I have to make my array of i value by 2.
12:07This is equal to 3. I have to make my array of i value by 2.
12:17Then I will return here.
12:17After that, I will return.
12:19I will return and what I will do here?
12:21I will return here.
12:21If I came back here, then the upper level will be empty.
12:25Here I will execute these two lines.
12:27Now I will execute this line.
12:29I will minus this i is equal to 2.
12:32So i is equal to 2.
12:33I will minus this one.
12:35Now I will return here again.
12:39and I will refer to the upper level.
12:42And i will return here.
12:43I will return here again and perform the last line here.
12:46Second step, The last line , i is equal to 1
12:46and that will be equal to 0.
12:50Again, I will go recursively down. When I went down, the upper level will be empty.
12:56The upper level is empty, now I will do i is equal to 0.
12:59I will do it minus 2, so I will do it minus 1.
13:03Now, as I will come back to the main function, what happened in the main function?
13:09This level will be empty. What is the main function?
13:13The main function will print my array again.
13:16Now, I will print my array again.
13:19Now, what values will come back?
13:20The values will be minus 1, 0, 1, 2 and 3.
13:24So, when I went up and went up, I had some changes in my array.
13:29And because of that, my array was like this in the base case.
13:32And when I came back and came back,
13:34After the main function of the main function, my array looks like this.
13:39This result is because of backtracking.
13:42Backtracking means that when you perform recursion from the call stack,
13:47We call recursion.
13:50So, I used recursion in this way to change my array values.
13:56How much time complexity in this whole process?
13:58The time complexity in this whole process is bigger of n.
14:02Why? Because I performed n steps.
14:05I performed n steps.
14:08I performed n steps.
14:08I performed n steps.
14:09When I printed my array twice, I performed two n steps.
14:13So, if I amortized time complexity,
14:16We have now understood that I have to ignore all constants.
14:19So, if I have total time complexity, that will be bigger of n.
14:22And how much space I used?
14:24I have no extra space used.
14:26The array was already in the main function.
14:28The space that I used is my stack call.
14:32So, space is bigger of n.
14:34Because I put recursion in the stack,
14:36To total n levels calls.
14:37Leg it in.