COMP2521 26T2 Week 1 Lecture 1

Added: 2026-06-03

[00:17:13]I think I think now it's okay.

[00:17:22]Can you please check for me?

[00:17:35]Can anyone here?

[00:17:57]Your mind become like this.

[00:18:17]Can you guys hear online or no?

[00:18:23]me.

[00:18:28]Can you hear it? Takes few seconds to have to wait little.

[00:18:38]>> Can you guys hear online?

[00:18:40]>> I think now it's working.

[00:18:44]>> I think now it's okay.

[00:18:48]Let me reduce the volume.

[00:18:55]Okay, thank you. Sorry, I didn't check that. Okay. Um, the next is developing efficient uh algorithm problem like designing, analyzing and implementing algorithm that we do throughout the course.

[00:19:15]analyzing the time and the space complexity that we discuss about this part on Thursday and again is something that we sorry yes >> yes please uh it seems that according to the most have to which is handle all the data the data I mean to the class or >> I will I will go through the course of all the sections in the course.

[00:19:56]>> So my main concern is that we have to you to >> uh >> you went to honey.

[00:20:10]>> Yeah.

[00:20:10]>> Just for labs for all labs. for exams.

[00:20:14]No, for for every has auto we have some changes this semester that for that if you don't do hand marking you will not get any type for You need to know whe >> Yeah, it's all based on C.

[00:20:56]>> Uh, and what version?

[00:21:01]>> A so everything is based on C.

[00:21:05]>> Yeah. But which version? C89, C99, this state 11 or >> doesn't just implement Whatever you are comfortable need to run all in CSC machine just you should be like run on CSC machine you don't write that on CSC machine Yeah. Uh actually a little bit is personal because you know your capability better. Yeah. You are doing part more or programming or next few things. But overall this world needs lots of exercise and you have to repeat and study. The worst thing is just leaving everything until end of the semester because the topics that we cover is a lot really impossible to even you spend one week understand all this just exercising and reading every week if you have any question to tell you that when I'm available is about to come and discuss and ask your questions or contact labs for tutor and lab assistant for programming questions.

[00:22:38]Yes.

[00:22:38]>> Is it compulsory to connect to the remote CSV machine or we have other >> so at the end because you will submit all your results and be evaluated on and your final exam is also on lab.

[00:22:52]So you have to it's better you use CSC machine to like used to it otherwise maybe for final evaluation problem.

[00:23:09]Uh yeah this is here that we said what you need actually we assume that you already know C programming language because all the programming is on based on C code and also we expect you already know condition loops function just basic C programming you know how to work with array pointer and link list and structure these are is necessary to know to actually implement all these algorithm and data structures.

[00:23:52]Um you will learn to uh analyze all the algorithm uh from space complexity and time comp complexity that we will discuss in detail on Thursday and you will learn lots of data structures also.

[00:24:10]So at the end uh we expect that you can choose which algorithm is better based on the problem and the data set that you have. You can distinguish which one like you want to go for linear search or binary search or which kind of sorting algorithm you want to use. This is what you will learn gradually during the course and other things. So teaching of this course has different part. One is lectures which is 4 hours per week. You [snorts] have tutorials one hour per week and labs two hours per week. You have quizzes every week except for last week and assignments two assignments and final exam. Let's now see the detail of each of these component. First is lecture Tuesdays 2 to 4 and Thursday 1 to three.

[00:25:11]uh here we actually present and overview the theorical part mostly if we get time a little bit of showing quotes but it's mostly about the concepts and theorical part and give lots of I try to show you um as much as possible examples so you learn the algorithm instead of just memorizing and memorizing the code.

[00:25:33]The next is tutorial one hour per week and start this week.

[00:25:39]Um they will try to clarify the lecture material and also go through the problems and you can always attend and ask all your question from tutors also uh if you don't understand anything.

[00:25:58]The next is labs two hours per week and for labs actually is completely programming part. You will have few question to answer each week. But uh marking uh of labs has two part hand marking automarking from this semester.

[00:26:20]You must get hand marking to be able to get the automarking part marks for labs. you just have uh until I think is in the website here then because next Monday is actually public holiday we put Tuesday but always next Monday 5:00 p.m. is a deadline for submitting the answer for lab and quiz.

[00:26:53]You have to submit for automarking but then you have two weeks to come in person and show the solution to the uh lab assistant to get handmarking.

[00:27:05]uh and if you do not show the your solutions to the tutors you unfortunately you will lose that automarking part score also. So the condition is you have to do the hand marking to be able to get the automarking part mark and at the end uh best seven out of eight will be used to calculate your final uh mark which is 15% of your final grade for quiz again uh best quizzes is mostly theorical question is not programming and again seven uh best seven out of eight will be used to get your calculate your final score which is 10% of your final grade you will have two assignments one is in week four one is in week seven and each of them is 15% of your final mark which is a big part totally than 30% of your marks from assignments.

[00:28:22]We will have help sessions. If you need help to answer question or any other question that you have, we will plan for it.

[00:28:32]So we will follow the late penalty policy of UNSW for lab quizzes and assignment. I'll have the same policy again 0.2% 2% of maximum mark taken from the raw mark for each hour late submission uh equal to 4.8% per day and submission later than 5 days not allowed. If you need special consideration you can apply and get little bit extension if you need it otherwise this late penalty will be applied on your mark.

[00:29:12]uh and sample solution for labs available one week after dropped date. We give extra date maybe someone uh apply for a special consideration. So it will be 12 days after initial due date uh the solution will be revealed and also yeah for assignment also we have automarking and hand marking again and final exam it will be three hours in person it will be in lab so it has two part theory and programming later we will decide that we want to give 50/50 to each part or we will [clears throat] make a 60 40. We will discuss about that how is the best for you guys. But we have a harder the most difficult part.

[00:30:13]Uh overall you need to get at least 14% of the final exam and also from each part at least you need 25% of the marks to be able to pass this course. Yes.

[00:30:28]explain more detail like the auto.

[00:30:33]>> Yeah. Uh hand marking actually solution is the same. You already submitted your solution if your program is working or not working. That's the automarking and the hand marking actually the lab assistant will see your solution and see check the slide. For example, if your code is clear enough and clean enough, how you name your variable, your function, your uh and also do you put proper comments for each line? Do you have a proper spacing?

[00:31:06]It means if someone see your code can understand what this code is actually doing. Well, it's not like you're more like >> checking and mark your uh based on that they give you is a marking actually but web aspect running or not running is auto marking.

[00:31:26]>> Okay.

[00:31:26]>> But to see how clear and clean is your code is just for hand marking part which is someone should see and usually decide how good it is.

[00:31:37]>> And we have same thing for assignment also. Okay. It's always good to always take care of the style of your code also because that will be a part of your mark for both assignments.

[00:31:53]So this is the summary labs is 15% of uh your total mark who is 10% assignment 30% and final exam uh 45%.

[00:32:06]Yes. Is it 25%?

[00:32:10]>> No. Which part? This one here.

[00:32:13]>> Yeah. 25%.

[00:32:14]>> Yes. This is a hard value. You actually should get 25% of the final exam because final exam itself has theory question and programming question.

[00:32:24]>> Yeah. So it's like 25% of the >> Yes. Whatever. For example, 20% can be 50% of or final exam can be 30% of it.

[00:32:35]You need give 25% of whatever percentage we consider for above and this is important because I can see that uh unfortunately many of the students fail despite they have a scores between 60 to 70 just because of didn't meet this hard. So that's very important part. So even they have a score of 70 which is very good score for this course with for this difficult course but they cannot pass the course and overall you need to have at least 50 out of 100 and for a special consideration if you need you can actually apply for it and you will get a little bit extension for your quiz lab or assignment.

[00:33:30]Um as you know that polaritism is banned.

[00:33:36]So we expect that you have your own uh solution for all these uh components and not allowed to use AI which is difficult to ignore it.

[00:33:53]And we have forum for discuss if you have any question we have help sessions and consultation.

[00:34:03]Consultation is with me if you have any question about the course. Uh every Tuesday 11:30 to 12:30 I'm available. I can have a face toface session with you. So if you need any help regarding the lecture itself like there's an algorithm you didn't understand properly or you think you need to see more examples or whatever I'm always available every Tuesdays 11:30 to 12:30 just you can directly email me and based on how many people um wants to have a consulting with me I can book a room and we can meet and help session is for lab that is different uh with lab assistant and tutors for applying for that one. You can there is a help section here.

[00:34:58]This information here is about the help section if you want to meet uh uh tutors and lab assistants. But if you want to see me, please directly contact me. uh I will uh arrange uh like any meeting room or whatever so you can come and if you have any question uh anything else yeah and uh please regularly check your email because we might send some announcements or you will receive email from your tutors I don't if you receive do you receive any email from your tutors already or no, you receive. Okay, you may send send some reminders or something.

[00:35:47]Uh and we will try our best to support you and uh upload all the materials on time so you can access all the materials.

[00:35:56]Okay, this is about the introduction about the course. Any question about the course marking everything?

[00:36:05]No, everything is clear for you. Yes, please.

[00:36:08]>> Um, what are the times for the >> uh they put some time here but it will be announced if you >> here there is a locations and this is the first one week two Wednesday 2 to 3 and Friday 2 to3 again and this is the location.

[00:36:34]>> Yeah, no worries.

[00:36:36]and it will be updated. So you will see the help sessions here.

[00:36:42]Anything else about the course?

[00:37:05]Oh, that's >> okay.

[00:37:08]>> I saw I saw >> Yeah, that is a first quiz all about knowing the course.

[00:37:19]>> Anything? Yes. Any question about data structures and algorithms?

[00:37:25]>> No.

[00:37:27]Do you need break or can I start recursion?

[00:37:31]>> Break.

[00:37:35]>> How many people needs break?

[00:37:39]Okay, the majority is saying recursion.

[00:37:41]So, let's start then.

[00:37:44]How about online? Any question in online? I haven't checked.

[00:37:49]I need glasses.

[00:38:05]Yes. The score of 70 and is still UF.

[00:38:21]No. for for marking quizzes you need to you don't need to come in person is it's just for lab what I said about tutorial you can see all the tutorials in the page Yeah.

[00:38:53]>> Um timet you can see the list of all the tutorials and labs in the time table in webcms. You can find the list time and location all all of them.

[00:39:20]So when should we do the quiz?

[00:39:23]>> Quiz now is already uh you can see the questions. You just submit via give >> then you submit the deadline is next for this week next Tuesday 5:00 p.m. but we always release the respond Friday because some people may ask for special consideration.

[00:39:58]No attendance to the tutorial not directly affect the final mark. It just help you to ask your questions but not extra mark for attendance.

[00:40:11]Anything else?

[00:40:20]Okay, I think okay let's start the first topic then recursion Okay, the first topic for data structure and algorithm is recursion. Actually, we use this recursion every session. So, this is the topic that we uh use it throughout the course.

[00:41:07]First, let's see what is the recursion.

[00:41:10]I wonder if you already know about version based on the program reporting course that you already have or >> Yes.

[00:41:17]>> I was just asking is it possible to turn down?

[00:41:27]>> Maybe we need to turn off the light.

[00:41:29]>> Yes.

[00:41:30]>> Where we can do that?

[00:41:33]>> Do you have any idea?

[00:41:42]and lighting.

[00:41:51]>> No, it's good.

[00:41:54]>> Okay.

[00:41:56]Okay. Uh recursion actually is kind of a technique in programming.

[00:42:03]uh the way we write our program but when we use recursion when we need repeat something in your in our programming.

[00:42:14][clears throat] So for example you want to do something repetitively one of the techniques to implement it in your program is using recursion.

[00:42:26]You already know because you definitely know about loops. You know for while use it for repeating few or more lines or actions in your code which is iteration.

[00:42:41]When we use loop actually we name it iteration but this is different way of implementing repeat repetition in your code which is recursion. So what is the difference? Why we use recursion? why we don't stick on the iteration.

[00:42:58]So uh actually when we do recursion we calling a function [clears throat] inside uh actually we have a function and inside of the function call that function again. Why we should let sometime go for recursion not for iteration just using loop because some problems inherently are recursive. So it's easier to implementing using recursion to use iteration. But we have other way around also. Sometimes it's better to go for iteration and recursion. I will show you by examples that when we go and use any of these techniques based on the problem again is about thinking about computer scientists. So you know there is a difference between iteration and recursion. That's what they're doing.

[00:43:45]Same thing. But we have to know where we use iteration and where recursion is actually better.

[00:43:54]Uh as I said recursion is actually a function that call itself.

[00:43:59]And what we do with recursion actually we have a main problem. With recursion we create a a sub problem and again another sub problem sub problem sub problem somewhere we should stop and then solve all these sub problem. This is how we actually do the recursion. So again we have a main problem and then we create a sub problems and this repetitively we create sub problems but somewhere we have to stop and then solve all these sub problem to get the final results is very common in tree least and divide and concare that we we'll discuss next weeks.

[00:44:43]What is important is if you want to solve a problem using recursion, you have to analyze your problem to see if you can find base case and recursive case. Base case it means how and where you terminate this recursion. That is very important. If you don't terminate it properly, it will be indefinite loop.

[00:45:08]It will be a stack overflow because it's repeatedly doing something without stopping somewhere. So this is very important that you properly stop your recursion somewhere. So that is the basics and then how now we need to implement this repetition which is recursive case. So for any problem that you want to solve with recursive you have to realize what is the base case and what is the recursive case.

[00:45:40]uh as I said if it's trivial they return the answer this is a sub case or base case otherwise we actually solve a smaller instance and then combine all the results to get the final results let's see some examples that what does it mean when we actually saying recursion just uh suppose we want to sum all the uh natural numbers number. For example, if n is three, we want to sum 1 + 2 + 3. So, we have to add or sum all this natural number until that n that is we have or for example, if n is 7, we want to sum 1 + 2 + 3 + 4 till 7 and get the final result. As it's clear, we repetitively doing something correct with summing numbers. So, there is a repetition.

[00:46:37]Now we can implement it using iteration or recursive. If it is iteration, we just can have a for loop. Uh the index can be 1 to three or 1 to 7 and using one extra variable and sum all these numbers. Correct or no?

[00:46:55]But with recursion now we want to sort with recursion we have to find two things. where this repetition stopped and how I implement this repetition base case and retirement case. So we have to see where we can find this in this problem and then implement based on that. We know based on these two examples if we start from any number for example if it is three if we go from last number to the first number we start from 3 + 2 and end with one and if n is seven it is 7 654 always end with one if it is a th00and 999 9998 till one so whenever n reach to one it is the stopping criteria. So that can be our base case.

[00:47:52]Correct?

[00:47:54]So first you have to find what is the base case and then the repetition part which actually doing this adding for you.

[00:48:07]Okay, let's see. This is a actually the piece of code that can show. I would like to use my pen with mic is a little bit difficult.

[00:48:24]Yeah, I have to put it back.

[00:48:28]I show you how it work.

[00:48:40]Okay.

[00:48:43]Uh let's see how we can like implement this simple problem using recursion here. For example, sorry.

[00:49:03]For example, n is five.

[00:49:07]So you want to say 5 + 4 + 3 + 2 + 1. We start from n. This is n.

[00:49:18]This is actually n minus one.

[00:49:21]n minus 2 till we reach one. So one is our stopping criteria. And if you see here in the main the n is five and we want to calculate sum of five. And here if n is one return one. So because this is our actually uh stopping criteria or base case otherwise this is our uh recursive function. As you can see I have a function name sum and inside of the function I'm calling this sum again.

[00:49:57]So this is a recursion.

[00:49:59]I have a function and calling this function inside of the function. This is the recursion again. So first time n is five. So we calculating sum of five.

[00:50:12]Uh if n is one stop. So n is still not one. So we go to the recursion line. It says five plus sum of 5 - 1. So next time I have to calculate sum of four.

[00:50:29]Again it call this time sum with number four. We will check we are not still reach the stopping criteria. And again it will be four plus sum of four. I'm sorry this is not comfortable.

[00:50:51]4 - 1 and then sum of three, 3 - 1, sum of two and sum of one. And here we some we stop we reach to a stop in criteria or base case because it says if n is equal to one return one. So it will be one till now we just have a one big problem and create a few sub problem and now we want to go back and s uh solve all these small problems. So sum of one is one.

[00:51:35]Here will be 2 + 1 2 and then 3 + 2 5 4 + 5 9 5 + 9 14. Sorry this was three. So I have 3 + 3 6 4 6 10 and 10 5 15.

[00:52:09]So as you can see a recursion first we found out how implement this problem as a recursive function we ch we actually have a base condition we have a recursion function in recursive always we create a sub problem until a stop somewhere and then we have backtrack and solve all these sub problem to get the final answer. Is it clear?

[00:52:38]>> Yes.

[00:52:46]>> Yeah. Actually, I will tell you how this possible. We use a stack for it which is been discussed in Turkey but I will explain that because it may be position for you where we keep all this and then the person back and uh solve all this problem. We have to save and keep it all in the memory to then later come back and then uh solve each of the sub.

[00:53:13]Yes.

[00:53:23]fail see the sum because sum is now of the function it call the function again and all the lines will be run again >> okay >> we don't have print here print should be finish >> and then >> and then >> yes >> yeah because of all the number will be save in the stack and I will explain and from the last number will be all printed so it's not print like a loop uh for loop that's inside of the loop that actually and it's printing every time in recursion recursion should be finished then the line after recursion will start running >> yeah little different mechanism compared to normal iteration any question yes please Sorry, I cannot hear.

[00:54:30]>> Base case and recursion case. And then where did it start?

[00:54:35]>> That's where the if we had loop that's where the loop would start, right?

[00:54:39]>> If it was a loop that for example for loop you mean?

[00:54:42]>> Yes. for loop we put index i from one to five and every time we put a step for it like decreasing and then inside of the loop we have like a variable sum and summing each index with that sum you want to see the iteration uh example >> we're trying to determine the base condition we just think where we would start with that >> you mean you can't do it to loop also No, >> I cannot understand your question.

[00:55:15]>> How we determine the base condition every time.

[00:55:17]>> How we determine as I said you have to see your problem. For example, here we say whatever it is, we always start from n and we end up with one because you are summing all the numbers to that particular number. So always one can be reaching to one can stop function. Based on the program you will see where this repetition can stop. Choose that as your base condition. You will see more example. Every problem is different.

[00:55:46]Based on the problem, you will choose what can be your base or solving condition. And if you don't set properly, it will be indefinite like indefinite condition will happen.

[00:56:07]Any question?

[00:56:12]Okay.

[00:56:15]Um, next, how about this one?

[00:56:21]This is another implementation for the same problem. Do you think it will give the same answer or different answer? The only thing is change is those red parts.

[00:56:32]Will it give the same answer or no?

[00:56:37]same because we are just going still of stepping on one we are stepping on zero so it will be the same because we're summing but if it's about multiplication multiplying numbers will be completely different because you're at the end multiply by zero and make everything zero.

[00:57:00]How about this one?

[00:57:04]No because instead of the number that we are expecting will be minus one whatever number it is because the last condition is minus one supposed to be 25 will be 24.

[00:57:20]How about this one?

[00:57:24]Why one more than what we are expecting to get this one.

[00:57:38]And why I changed one more thing which is not highlighted. Sorry.

[00:57:47]>> Sorry.

[00:57:54]Yeah, here I I'm not decreasing the n.

[00:57:58]So it will be indefinite situation because it never reach to n uh equal to one because I'm not reducing or decreasing n inside of the recursion function.

[00:58:13]Okay, another example of recursion uh factorial that we use it in different calculation. It's also a kind of recursive function.

[00:58:31]For example, if you want to calculate the factorial of the number, for example, factorial of five is five multiply four 3 2 until one and factorial of zero is itself one. So if you want to implement this as a recursion, we have to see what is the base condition and which part is actually recursion function. We know that whatever number that we have and we want to calculate factorial at the end if we reach with zero the factorial will be one. So this is the stopping condition and every time we multiply n in the next number. So it will be n mult* n minus one. So let's see how it works.

[00:59:42]again. Uh just suppose we want to you know that let me just for Five factorial is like five * 4 3 2 1 correct. This is as we know mathematically. So if you want to implement it as a recursion again we have a function fact and inside of the function we calling this function. So this is a recursion.

[01:00:18]Initially we want to calculate fact of five and we know that if we reach zero we will should return one because zero factorial is one. We reach we haven't reached to zero. So we have to see this line which is five ult* fac of four and again recursively because we see factor of four again this function will be called this time factor of four will be four multiply factor of three and factor of three is three Fact two and factor of two will be two. Fact one and fact one will be one. Fact zero.

[01:01:15]Okay. We reach to uh stopping condition.

[01:01:19]If we reach to zero we have to return one. So this will be one. 1 * 1 is 1. 2 * 1 is 2.

[01:01:31]Here 3 * 2 6 6 4 * 6 and 5 * 24. So this is how we calculate the factorial of five using the recursion.

[01:01:51]Any question? Yes.

[01:01:56]The best way to find >> Yes, we always create sub problem until the stop and then we start solving. So [clears throat] stop we are not actually solving we are just creating sub problems. Is there a scenario where >> yeah like yes it can be multiple it depends on the I think this one can answer your question.

[01:02:38]Okay, just before to go that one. Is it correct or no? Can it calculate fact five or no?

[01:02:51]>> Base condition will be reached. This will be infinite loop.

[01:02:54]>> A little bit louder please.

[01:02:56]>> Will be infinite loop because the base condition will never be reached.

[01:02:59]>> Yes, because our base condition here is wrong. It says if n is 100 return one but we are starting from number five and we are not increasing so the base condition is wrong. It will be indefinite calling style.

[01:03:17]Another example just quickly I show this example also. Another example is Fibonacci function.

[01:03:26]uh Fibonacci sequence uh is a series that always start with zero and then one and from third one we always calculate the sum of two previous numbers. Always start with zero and one and then 0 + 1 1 + 1 2 2 + 1 3 kill.

[01:03:52]So always we calculate sum of two previous number to find the next number in the series. This is Fibonacci function. So again we are seeing some repetition in this series. So we can see how we can implement it using recursion.

[01:04:12]So what can be the base condition here?

[01:04:14]For example, if I say show me the first five sequence or first 10 numbers in this sequence. Imagine I want to see first 10 numbers into sequence. What will be the base condition?

[01:04:37]Zero because always start from zero and one. So doesn't matter how many sentence I want how many numbers I want to see if I start with the last number always I have to see zero and one to stop because of zero is always zero and of one is always one the rest should be calculated using the two previous numbers.

[01:05:06]This is how we show it mathematically.

[01:05:10]If um as you can see if n is zero or n is one the output is n itself. Otherwise we have to always calculate the sum of two previous numbers in the series which is previous number and two number behind.

[01:05:29]So n minus one and n minus2.

[01:05:33]And again if you want to calculate and show this piece of code show uh n can be five here. So it's showing the five first number in Fibonacci series you want me show you or is it clear for you? Should I show you with example?

[01:06:01]>> You want to see the example? Yes.

[01:06:28]Okay.

[01:06:30]Here in this example you can see the main function when we said we want to see that first uh five numbers in this series and then I have a for loop and put this calling Fibonacci inside of the loop.

[01:06:54]Can you tell me why I have a loop here and then I have a recursion other side also? So I'm using both loop and recursion. Yes, >> you want to print the whole series. So you need need to do something for each number. But in order to get each number you have to go through.

[01:07:13]>> Yes, correct.

[01:07:15]>> Yeah. So for each of these calculating for example third number in Fibonacci series I need recursion to calculate it and then for number fourth number I need to go through recursion.

[01:07:30]So this uh for loop is just for uh going to all this one to five number but for each of this number I have to actually uh run decursion on it. So here we can see loop and recursion both because we have to find each of this number and then print it out.

[01:07:53]Okay. If n is five here we call first time uh we want to find the Fibonacci of zero then one then two then three four and then Fibonacci of five. So first time we call Fibonacci with zero.

[01:08:19]Okay zero if it's n is zero return zero because we know that the uh Fibonacci series always start with zero. So if n is zero the output is also zero. So in this four it will print zero uh as a output. Next time for loop next time I will be one. So we will calculate Fibonacci of one. Again you will call Fibonacci and if it is one again return one.

[01:08:54]So it will print one.

[01:08:57]Next time I is two we have to call function. It says even if it's second number in the sequence still it is one because it always start from 0 one one. So again Fibonacci of two is also one. This because of for loop it will print again one as output.

[01:09:23]Next time is Fibonacci of three.

[01:09:28]So not this stopping condition applied not this one and not this one. So we have to call the recursion function.

[01:09:36]As you can see recursion is called Fibonacci twice. So it will be FE of 2 plus fib of one. Now we have to call fib of two and fib of one again.

[01:09:59]Fib of two we already know that it is one. I don't want to calculate again. So just it will be one. This will be one. It will be two. So output will be two. Next time Fibonacci of four will be fib of three plus fib of two.

[01:10:24]Fib of two we know already is one but f of three we need to calculate again.

[01:10:30]We can see here but actually in practice it will be calculated again. This is a problem of recursion that repetitively we repeating and calculating same thing that already we calculated before. We can see here Fibonacci of three is two but it will again calculate it when you're using recursion.

[01:10:52]So fib of three will be fib of 2 + fib of 1 which is two sorry will come very messy. So it will be 2 + 1 3 is no enough space here.

[01:11:19]And the last one Fibonacci of five itself is Fibonacci of four plus Fibonacci of three and then again we have to calculate for four again calculate for three again and whatever is needed and then solve all these sub problem to get the final result and print it out And here you can see that what actually we did to calculate Fibonacci of five. You need to calculate Fibonacci of four and three and four itself is three and two and three is two and one and two is one is zero. You can see how many times we calculate Fibonacci of zero or one or three. That is a problem with recursion that sometimes we need to repeat same thing again and again and again. If you want to like if it if you want to achieve off 10 then it will be crazy. It will be big three any question.

[01:12:26]No cannot see.

[01:12:35]Okay.

[01:12:38]So what we do here actually the term of creating sub problem from main problem we call it winding and when we backtrack and solve all these sub problem we call it unwinding just is a term that if you see somewhere is the same thing that we are doing here creating sub problem to sub problem from the main problem is actually winding until we stop somewhere and then rewinding unwinding when be solving all these sub problems and one thing here important we will discuss about stacks I think in week three uh all this calculation all this function call that we did should be saved somewhere then we can access and solve all these sub problem the data structure that we use to save all these sub problem is actually a stack so we are using an extra memory when we are using recursion and we put all these sub problem in the stacks and then access those sub problem and solve all of them. So this is one of the actually problem with using recursion that if there your recursive call is a lot you using lots of memory for it and if you don't have enough memory or your base condition is not correct you will see a stack overflow error.

[01:14:10]One more thing that um one of you also uh uh asked this recursion function before this recursion function there might be some quotes some quotes can be after this recursion line or both side.

[01:14:26]So where you put your recursion function will affect the final output.

[01:14:31]For example, here we have prints and then uh recursion column.

[01:14:40]Suppose n is three. What we will see now as output. If n is three, what is show?

[01:14:55]3 2 1 not zero because if it n is zero return I'm not returning anything so it just a stop so it will be 3 2 1 how about this one here the print is after recursion function >> one two three because recursion should be finish and then print will start. So the output will be 1 2 3 and how about here recursion is in the middle of two prints and suppose n is three.

[01:15:48]It will be 3 2 1 1 2 3 correct.

[01:15:57]So where you put your recursion is important is affect your final result.

[01:16:04]Another small things here sometimes recursion can be direct or indirect. If you have a function like all the examples that we saw and you call it inside of the function, it is a direct call or it can be indirect.

[01:16:21]Yeah, you have a function and call another function and then call back the first function. So it can be indirect call. Here as you can see here is the first function. In first function we call second function and inside of the second function we call first function.

[01:16:40]So recursion can be indirect.

[01:16:46]Uh any question?

[01:16:50]Yes.

[01:16:55]>> Yes. In all the examples that we saw before, it was a direct because we have a function like f and we calling f inside of this function.

[01:17:08]This is direct. Okay. But we may have two recursive function.

[01:17:16]In the first function we call the second function which is f_sub_2 and inside of the f_sub_2 we call f_sub_1. So this is indirect.

[01:17:31]Uh now see how we can uh define recursion on array.

[01:17:39]Just just an example because recursion we can use recursion on array link list tree graph whatever. We're going to see one example of using recursion function to calculate something on on a specific array. Imagine we have a array for example array of five number and we want to sum all the elements in this array using recursion.

[01:18:05]We can simply do it using iteration.

[01:18:07]Correct.

[01:18:10]Summing all the items because you just need to have a for loop and go from the first item to the last item and then sum all the items inside of the uh array. Now we want to see how we can do it using recursion. It's a little bit more complicated when you want to use recursion for this.

[01:18:31]This is a implementation of using recursion to sum items inside of the array. Can anyone tell me how it works?

[01:19:02]Is it big enough? So Okay.

[01:19:22]>> Yes.

[01:19:24]>> It starts at the end of the array and winds it winds towards the side of the array, returns zero to start the sum when it gets to the zero position of the array and then unwinds back towards the end of the array, adding up the sum along the way.

[01:19:41]>> Can you It starts at the starts at the end.

[01:19:45]>> Yes.

[01:19:46]>> Goes all the way to the beginning.

[01:19:48]>> Okay.

[01:19:49]>> And then take the sum of the take the sum of the entries on the left as it moves back towards the right.

[01:20:03]>> That's correct that it start from end to start of the array a little bit different.

[01:20:10]We for example we want to sum all the elements in this array. Okay. If or we first we have to see why that that the stopping condition is if n is zero return zero. n is length of array.

[01:20:29]We know that if the length of array is one it just have one item. What will be the sum of the all the items in the array? The item itself. Correct or no?

[01:20:39]If the length of the array is one and we want to calculate sum of the array it will be the as number it is. So we want to recursively making sub problem length one and a stopping carrier is when we reach to length zero length zero it means array is empty so that n is about the length of the array. So here so whenever we reach to length of zero we stop first we get and we know that in C the indexes start from 0 0 1 2 3 4 so when it says array n minus one it means this item so it will be 3 plus sum of array until n minus one. So we have 10 2 5 6.

[01:21:43]Again we call this function.

[01:21:47]This time again we take the last item out of the array will be three + 6 plus sum of 10 to 5 and again we continuously take the always the last item out and then apply this recursion on the rest of the items. Now length is two 3 6 5 2 sum 10 and then 3 6 5 2 sum nothing. Now we have a array with length of zero. So this will be zero.

[01:22:33]And now we can simply sum all these numbers to get the final uh actually sum of the whole array.

[01:22:44]Any question?

[01:22:55]Does this mean this function the first repeat?

[01:23:02]>> No. No. I just actually I have to I just repeated because you know you know that I take the item out that at the end we just calculate one time.

[01:23:16]So next time I better for to avoid confusion I don't put three here just ignore this and ignore this will be 0 + 2 and then + 5. So every time we just use this number once.

[01:23:38]I just put that number. You know that we already processed that number. Now we just have a look to rest of the array.

[01:23:44]But every time we just uh actually consider each number once when we want to calculate the sum. Yes, please.

[01:23:52]>> Is there anything that stops us from saying >> sorry a little bit louder? I cannot >> Is there anything that stops us from having any return?

[01:24:05]So you want to start >> like that is the basis instead of >> like can we use like an array of like one bas if n is one if n is one then I cannot say return one I can say return array whole array because array has one item inside of it because of that We went to the until is empty. So we can return zero.

[01:24:39]>> But we could also return like >> yeah if we just we want to stop when the length of the array is one then we have to return the number inside of the array.

[01:24:53]>> Yeah. Yeah. But just to be careful how to implement it that your stopping criteria really work properly >> at this one.

[01:25:06]>> Sorry.

[01:25:11]>> I didn't put 10.

[01:25:15]>> I miss Yeah. Sum. Yeah. That then is sum of 10 which is 10. And then sum of uh Yeah. This one wait here it is 10 here >> plus sum of empty array.

[01:25:34]>> Yes. So we shouldn't miss any number.

[01:25:36]Yes is not even can see here 10 is here became worse. Okay. And this one, what is the difference between this one and previous one?

[01:26:10]>> Yeah, in the previous one we every time take the last item and take it out. And here we always take the first item and then uh recursively see the rest of the items in the array. The only difference is there we every time take the last item out. Here we take first item out.

[01:26:33]So our stopping criteria is still the same. We continue this until the length of the array is like zero. Array is null.

[01:26:47]Okay. Which one is better?

[01:26:50]The we take every time the last item or first item?

[01:26:56]Which one?

[01:26:57]No difference. Both are the same because the number of time do repeats and doing the recursion are the same and the final results also the same. So we can see that we can you can implement recursion for same problem differently and get exactly the same results with same complexity and quickly see one example on the link list because we can apply recursion in any data structure. You already know about link list. Each link list has different nodes. Each node has data and a pointer to the next node.

[01:27:40]Uh any question >> previous pointer?

[01:28:01]>> Yeah.

[01:28:03]Yeah.

[01:28:03]>> How we >> Yeah. Because it says >> no in C when you mention to name of the array name of the array always point to the first item of the array. So when I say array + one it says next index.

[01:28:21]Yeah, because we already one item and then the rest of the array will be the rest of the items in the array. We're starting from beginning of >> what we need is like the array plus one is to change the pointer to >> pointer yes to next element is like a we're changing the index going to the next element in the array.

[01:28:47]This a r here is act like a index.

[01:28:58]Um link list itself is kind of uh inherently is recursive because each node has data and uh actually link again data link data link. So it has this recursion itself. when you want to create a link list.

[01:29:17]Uh here again if you want to apply that summing the items in the link list you can see here every time imagine this is a link list we have different items in the list for simplicity I just show like this. So this is a first node, second node, third node. Again we have to we can have the same type of uh recursion that we defined for previous array.

[01:29:40]Every time we get one node and then apply recursion in the rest of the list and then take another item out and then apply recursion to the rest of the list until we reach to the null. So it will be the same kind of function here. As you can see, we can first take the first node out and then apply recursion on the rest of the remaining list. And again, we take the next item out and then uh see the rest of the list. But again, uh we will at the end just have 2 + 4 + 5 + 7. This if you you see that repetitively, I put the number just to show you how it works. But we just uh use this numbers just once when we are doing final sum.

[01:30:32]Uh here one recursion simple recursion function on the link list.

[01:30:39]Uh the function is print list and we call this recursively inside of the function. As you can see, uh we will uh print out the value and then we go to the next uh node and we recursively continue until we reach to the end of the link list. So that's a recursive function that print out all the items or elements inside of the link list.

[01:31:10]question here. As you can see again we have a base case which is reaching to the end of the link and this is our uh lines that recursively uh repeat this one actually calculating some of the item inside of the list. Again the same logic uh if it is uh null return zero. This is our stopping function base case. Otherwise every time we will take the value and then sum it with the elements in the rest of the list like array.

[01:32:01]Sorry, I forgot something about the difference.

[01:32:07]>> In a node type, for example, inside of the node value can be integer, can be character, can be what type of the data is inside of the uh node.

[01:32:29]So we can this is a few uh actually exercise defining recursion function for printing all the items in the link list or printing items reverse from end to first or every second item or we print specific item that we have the index of it. You already see two of them I think.

[01:32:57]What this one doing?

[01:33:05]What this function does >> not from the end.

[01:33:23]It is started and showing all the values until reach to the null. It's stop. Yes.

[01:33:31]Okay.

[01:33:33]Because print is before print list it will print and then recursion apply again. So if the items are 2 4 5 6 we will print 2 4 5 6 not from end to the uh >> head sorry because here is difficult to here. Sorry. How about this one?

[01:34:01]The answer is there.

[01:34:04]What is doing?

[01:34:08]Because print f is after recursion function.

[01:34:13]It will print items reverse from end to first item.

[01:34:23]this one because every time we skip one note, it will show actually every other nodes in the link list.

[01:34:36]And this one find a particular item that we already give the index of it. Like for example, we want to uh show node index two.

[01:34:51]Uh I think this is the last thing. Yeah, this one I just uh say this helper function is actually then we will discuss in uh week three. writing helper function is instead of we have a function and call that function inside of the function directly we can have some extra function to make our program a little bit more clear. So what we do actually instead of for example here we have a function and then inside of the function we call the helper function which is our main recursive function. Yes.

[01:35:47]>> So when you're doing the general >> [music] >> NUS because every time I have to send an item or add to this function and then I'll do all this calculation again. So based on if I need to go to previous item or next item then it can be nus 2 actually just the index of the item >> that you are using. Yes. So that is a different way of using compared to iteration.

[01:36:22]So the helper function is nothing different and the results also all the same. The only things is we have two function. First function is just like calling the second function and then main recursive happening in the second function. For example, look this one. This is without helper function. We have a uh print with index and then we call this print with index inside of the function is like a normal recursive function or we can write it like this. We can have two separate function. In the first function we call this recursive function and then we have this recursive function also is just u like adding another function but the results are the same.

[01:37:20]So overall uh recursion in most of the time is more clear and elegant.

[01:37:30]uh iteration can be more faster and less memory. We see that uh recursion can have lots can use lots of memory and based on the problem we will make a decision that iteration is better or recursion is better.

[01:37:46]The common mistakes missing base uh missing base case wrong base condition not reducing problem or indefinite recursion that if you do not implement it properly it will happen.

[01:38:02]Okay. Um this is all for today and if you have any feedback please anyway positive negative if it will help me to adjust my teaching based on your feedback.

[01:38:22]Thank you.

[01:38:28]You're happy you're going in more happiness. [laughter] Thank you everyone online.

[01:38:43]So we have to stop.

[01:38:54]Um I just have a question about what you said in the first part about >> is it very difficult We want to