nm0718: how many people looked at the examples that we covered last time on inheritance and abstraction how many people didn't good we looked at two different ways in which you could two different ways in which you could have subclasses of other classes so we looked at one case where we had an alcoholic drink class and then we had a subclass of wine which was a particular case of an alcoholic drink okay and that was the example we've been working through over the a week or so and then the last thing that we looked at last time was having a generic abstract class there are seats around here round the other side if you want to come down the other thing that we looked at was an abstract class which could have several different possible cases of which there could be beer wine spirits and so on and they both do equiv-, roughly the same job okay so those are alternative ways of looking at inheritance and abstraction but the second one has this generic class and we'll look at that a little bit later in the course and we'll see why that's quite useful in allowing you to to do a new category of things on er the things that are different but are broadly the same have this broad abstract structure that's the same how many people understood the difference between the two ways of doing inheritance how many people didn't of those people that didn't how many of you looked at the notes and tried to work through an example okay the one thing that we didn't do last time was the final keyword final modifier and we encountered the final modifier over several previous cases several previous slides when we were looking at modifiers how many of you have done Pascal okay so you'll know that in Pascal there are things called constants okay and in general there are things that are constant that have constant value like pi which is three-point-one-four-one and whatever it is er and there can be various other constants and i've avoided this up to now 'cause we can deal with all the uses of the final keyword er in one chunk and when you have a variable just like any other variable and you know that its value isn't going to change throughout a program then by adding the keyword final at the front of the declaration you can say that that is a constant so final int lucky number equals seven which is assigned is assigned the constant value seven and that value will never change throughout a program i was going to try and turn down the lights can you see this at the back good okay okay so that's fairly straightforward but in classes in objects in classes it becomes rather different it has a very different meaning and that is that you can't override a method that is final in a subclass okay so for example one thing that you've seen several times before is the two-string method the two-string method in the previous examples that we've seen allows you to print out a representation of an object okay and whenever you define a two-string method in your objects in your classes that overrides the previous two-string method the two-string method that is there by default you've seen the equals method we defined an equals method last time okay and it's used with strings and there's a default equals method and these things are overridden so that when you define your own equals method it will override any previous equals methods that exist and there is a default that exists but you will override that what this says is that if you have a final keyword with a method definition in a class you will not be able to override it okay so if in the default definition of equals or two-string this keyword final was there then we wouldn't be able to override that with our own definitions of equals and two-string okay so that's all that final means and we've seen several different modifiers we've seen static and private as well which are both final by implication so although they don't have final in them they are final methods you can't override things the reason for using final is that if the compiler knows that it's never going to have to redefine it it's never going to have to do anything more then it can optimize the code when it's converting it to the thing that it actually executes it can try and make it run quicker faster better okay without that knowledge without knowing that we won't override it it's very difficult to be able to do that so it's quite useful 'cause it allows the compiler to optimize code and because of the way it works which is all really a consequence of the fact that you can't override things a final class can't be a superclass so in the previous example the abs-, alcoholic drink the abstract alc-, alcoholic drink and the generic alcoholic drink you can't have final for the methods that are sorry for the class er that will then er generate subclasses like wine and beer and so on okay any questions how many people understood that okay good that's it that's classes they're done they're finished if you have questions problems ask your seminar tutor or ask me later okay but that's it that's essentially all we're going to do on classes and objects okay so i expect you now to know it and you have a test gosh is it next week someone's nodding test next week how many of you remember you have a test next week hurray next Thursday i think a test in L- three the second test the second test for this course worth five per cent of the marks okay so the key thing that we're going to do today is to look at recursion and recursion is a very simple but powerful concept but it's also something that people find quite difficult typically to deal with okay and recursion just refers to something that refers to itself and this is repeated over and over again by referring to itself and so this picture of a television screen within a television screen within a television screen is a recursive picture because it just keeps on going until some point at which we can't see it any more okay and that's all that recursion is it's just defining something in terms of itself so this T-V picture contains a T-V picture which in turn contains a T-V picture and so on how many people have heard of the Towers of Hanoi wow how many people can solve the Towers of Hanoi mm this is my i i cheated earlier today because i er i pretended to be a student in the er writing course that that C-S take er and there were lots of exciting things happening in in that there was music being played and tenners being thrown up scrunched into balls and thrown into the corner and it continues the excitement of the day 'cause we have a a prop which is my Towers of Hanoi okay Towers of Hanoi three poles with a number of discs on one end and the idea is to take these three discs and to move them all to the other end okay third pole by placing taking one at a time moving them across but not putting a smaller disc a larger disc onto a smaller disc okay so that would be an illegal move in the Towers of Hanoi problem okay we can't do that we can only move smaller discs onto larger discs okay so we could solve it in various ways it could be quite tricky could be difficult but it's called the Towers of Hanoi because apparently there's a er a monastery somewhere in the Far East er i am told it's in what is now Hanoi er in Vietnam but i don't know if that's right or not er and the monks in this monastery er have a problem like this with sixty-four discs okay so they've got a stack of sixty-four discs and they make a move every day they move one disc onto a different pole every day and supposedly when the monks finish the problem the world will come to an end so there are these monks somewhere in the Far East taking a disc at a time and moving it across and whenever they finish the problem er the world will end now the good news is that that will take an incredibly long time even if they even if they do it in the most sensible way possible so er we still have a while to go yet but the good thing about this particular problem is that it's a very good example of how to how recursion can make something that looks quite complicated very very simple okay so there's a very simple way to do it if we have one disc how many people could solve the problem with one disc how many people couldn't one disc is very easy 'cause there's no problem you can move it straight to the end very easy now you get the people that didn't put up their hands you can do it with two discs how many people can solve it with two how many people can't okay so two is very easy 'cause we just use the spare pole in the middle and then move it across and then do that very easy how many people can do it with three discs so this is when i get someone to do it who did you did you put your hand up sm0719: yeah nm0718: go for it they're they're not in the right order by the way sm0719: yeah nm0718: so you can sort them out first okay so ss: nm0718: st-, you need to st-, right [laughter] you need to start with st-, st-, shall we start again sm0719: yeah go on nm0718: i dare you sm0719: let's go try again nm0718: start with them at one end that might be easier ss: nm0718: well done thank you er it it's that that was i'm i'm dead impressed with that actually because it's very difficult doing it when there are lots of people watching but er can anyone do it with four too far away i can't reach you anyone we'll have a go at four in a in a in a bit er but if we break this problem down into separate parts it's very simple okay what we're doing is we're saying the the problem with three discs can be broken down into the problem with two discs and then one disc so we need to move these three discs over to here and we can say if we move two discs across okay we can just move the one across there and then we can move the two across to there okay but we can't move two discs across 'cause we can only move one disc at a time so the problem is then how do we move two discs from here to here well that's easy 'cause we know we can just move two discs from one pole to another pole using the spare pole so we want to move two from here to here using this spare pole and we can do that pretty easily 'cause most of you said you could do it okay that's fairly easy the next thing that we can do directly we can move this disc across to here and then the next problem that we have is to take these two and move them across to this pole using the spare pole and we've just done that already the other way round and that's fairly easy and straightforward so we moved it across okay does that make sense how many people think it doesn't make sense how many people think it does hurray okay four discs the problem with four discs is the same as the problem with three discs except we're now going to move three at a time to the middle one then the big one all the way to the end then three across but we can't move three so we have to do it in terms of two so if we were starting with this one and moving them across we would have to find a way of moving three discs to here okay and we'd have to find a way of doing that in terms of two which would be done by moving two discs to here and then we'd have to find a way of doing that which would be by moving one to here one to there one to there so we've now moved two discs if we go back trying to move the two discs back onto here we're okay we can move this one directly and now we're back with the problem of moving these three from here to here okay and we can't do that directly so we have to move two from here to here and then move the big one directly onto this one and then move the two back so we have to go two discs to here okay those are our two discs this one moves directly and now we're back with the problem of moving two from here to here using the spare pole okay how many people think they can do it with five discs how many people think they can do it with six discs okay [laughter] we don't have time for six discs or probably even five discs but it's exactly the same thing the problem to five discs the problem with five discs is the same thing as moving four to the spare pole one across and four back across and we can do the problem of moving four from one to the middle by using the spare pole and then we work that one out in terms of moving three and we work that one out in terms of using two any questions about that so people you all think you can do it in f-, with three discs right anyone does does anyone think they couldn't do it with three discs does anyone think they couldn't do it with four discs if they had enough time is that is that 'cause you don't understand how it's done or because you'd get lost sm0720: did you say could or couldn't nm0718: sorry sm0720: did you say could or couldn't nm0718: couldn't do it in four couldn't do couldn't move four discs across how many people s-, think they couldn't do it in with four discs can i have it hands up again is that if you keep your hands up please er don't want to er is that because it's the problem is difficult or is it because do you think you'd you'd get lost on on the way no answers okay i'll assume that means that you can all do it and it's a very simple thing to do the solution the general solution to this is simply to move the top N-minus-one discs from the source to the auxiliary if we have a source tower a destination tower and an auxiliary tower okay the auxiliary being the one that we don't want to get things to but the one we're going to use in the middle we simply move the top N-minus-one discs to the auxiliary and we can use the destination to do that the next thing we do is move the bottom one to the destination and the next thing is to move the top N- minus-one discs these guys from the auxiliary pole to the destination okay and these green remarks here about which pole we want to use to do that is the spare pole that we will use each time round okay so the Towers of Hanoi is a actually a very simple problem but it gets progressively bigger each time round if we add another disc we double the size of the problem we double the number of steps that we need to take to make it work can i move this okay so how do we do that in Java how many people have found have looked at at least one program that i have made available online in my filestore how many people haven't okay if you want to look at this program it's in tilde-C-S-rat-slash-Java-slash-five- slash-Hanoi-dot-Java with a capital H and this slide is number forty this was given out with the methods slides okay in this program i've set N to be four and N just tells us how many discs we have to deal with so in this particular example we have four discs and i've added a final keyword here because we could make that a constant if we wanted 'cause this value of N isn't going to change inside the program okay this value of N is going to be constant throughout the program so you could and it would be sensible in fact to put the final keyword at the beginning there okay and the main part of this program simply prints out a heading Towers of Hanoi for four discs and then calls a method it's a very old prop then calls a method move to move a disc from one pole to another okay and this is the output this slide over here okay so in this program which you have this method move is the key thing that we are going to use okay and just as we defined the problem in terms of a solution the solution to the problem in terms of the solution to an easier problem so the solution to four was defined in terms of the solution to three we will define a method in terms of er the method itself is that is that a hand sm0721: yeah can you refer to a method before you declare it nm0718: can i sm0721: refer to a method before you declare it nm0718: yes yes you can call a method before it's declared you have to typically 'cause you wouldn't be able to use any methods er unless they were declared afterwards you couldn't use a method in the main method so all the examples that you've seen so far probably have methods that are used before they're declared okay so we've got simply the main method up here which is the main bit of the program and down here we have the move method that we're going to use to do all of the work of this particular program to solve the Towers of Hanoi problem and this method move it's a static method 'cause it's a class method there is no particular object that we're associating with it and it takes one two three four parameters four arguments the first is N which tells us how many discs we want to move okay in the first the first time round we use this the first time we call this thing we've got four discs so N is four and then it takes a letter a character referring to the source the auxiliary and the destination poles which i've called A B and C okay so when we call this first time round N is four source is A auxiliary is B and destination is C okay and trivially we know the answer when N is one if we've got one disc we can move it directly okay everyone can do that 'cause you laughed when i asked if you could and we can write that out directly if N equals one then simply print out move disc and N refers to the the number of the disc which is one from the source to the destination directly okay and because source and destination are variables referring to which have the particular characters that we've got it's fairly straightforward to do that okay so if we just had one disc if N was one inside this program we would just simply have one A B C source would be A destination would be B and we'd simply move disc one from A to B sorry from A to C right but if we haven't got one disc if we've got more than one discs then it becomes a little more difficult okay but using recursion all we need to do is write down the form of the solution okay and that's pretty much all we need to do we simply need to move N-minus-one discs so in the case where we had if i can reconstruct this particular thing in the case where we had f-, four discs the trick is to move three discs to the middle pole which is what this line says move three discs N-minus-one from the source to the auxiliary using the destination okay we've got source auxiliary destination and this says move from here to here using this okay and that's all we're saying there then write out the solution to moving one disc from the source to the destination okay which is disc N disc four in this case that's the bit in the middle and then we simply solve the problem to move three discs from here from the auxiliary to the destination using the source okay that's all that this says but that's easy we know t-, how we can do that 'cause we simply know we simply need to say how do we work out the solution with three discs that's the only thing we need to work out to make this complete solution work and when we hit move again the second time all we do is call this method with this N being set to be the new N-minus- one so this is now the new time we call the next time we call move N now has the value of N-minus-one which is three the source gets assigned to this source the destination gets exsigned gets assigned to the auxiliary and the auxiliary gets assigned to the new destination so when we were moving three discs at the beginning if i can just swap it around okay we wanted to move all of these to here and the way we did that was by moving these three the top three to the middle pole we simply changed the order of the arguments changed the order of the poles so that when we call it again we have to find the solution to moving from the source to the auxiliary okay these three moving to here and if we make those assignments we can check to see if it's one disc that we're moving and it's not it's three so we simply need to do that in terms of moving N-minus-one discs which is two discs from the source to the auxiliary using the destination well the new auxiliary is this one and the new destination is this one sorry the new auxiliary is this one and the new destination is this one so we work out the problem to s-, to moving two across then we can move we can write the solution to moving one directly and then we can work out the solution to moving the last two across again okay and eventually we'll get down to a point where we're only working this out in terms of moving one disc at a time when we're moving one disc at a time we have the solution directly so let's have a look at how that works can you see this at the back okay first thing we do is to move disc one from A to B so it's here to here disc two from A to C disc three from A to B sorry disc one from B to C disc three from A to B and so on okay it should be clear that this solution is correct disc one from C to A disc two from C to B okay disc one from A to B that's moved three across okay this chunk of the solution simply moves three discs across from the source to the auxiliary using the destination but if we examine that in more detail we would have to make a call another move to move N-minus- one discs two discs from A to C using B okay and that's the solution that we've got up there if we change the N here at the beginning of our program to be two we would just get a trace of three moves okay if it was two we would just simply move N-minus-one discs which would be one move the one in the middle and then move N-minus-one discs again which would again be the one okay so the solution to two discs is simply three statements then we would move the one in the middle okay so it would be moving two to here moving the one in the middle and then moving two back again okay and you can see the structure of this as we build it up is there is a solution that is defined in terms of the solution to two smaller problems plus a direct move in the middle so all of this is the solution to four discs the green line indicates the solution to three discs the red line indicates the solution to two discs okay and if we look at the solution to three discs in terms of the solution to two discs it's simply the solution to two discs plus a direct move plus the solution to two discs again if we look at the solution to four discs in terms of the solution to three discs it's the solution to three plus a direct move plus the solution to three again okay and that's all there is this program generates that output and it's probably one of the simplest programs you'll find to do something quite complicated nm0718: another example and this example is in tilde-C-S-rat-slash-Java-slash- five- slash-fact-one-dot-Java and also fact-two-dot-Java how many people don't know what a factorial is okay factorial is simply a very simple mathematical thing four-factorial is simply four times three times two times one five- factorial is simply five times four times three times two times one that's all factorial is okay so iteratively and iterative is just looping around in circles iteratively the solution to N-factorial is simply N times N-minus-one times N-minus-two all the way through to one so the solution to six-factorial is six times five times four times three times two times one and we could loop round in a while loop or a for loop simply multiplying numbers together generating that kind of result we know that N-factorial is equal to one when N is zero okay we're given that we know that and if we wanted to write a method to do that we could simply write this factorial method which starts out by setting F an integer F to be one and then have a for loop looping from one to N so I is set to be one initially we loop round while I is less than or equal to N and each time round the loop we add one to I and inside that loop we simply multiply F by I okay so if we have a look at how that would work okay first of all when we call this method N is five which is what's given to us as a parameter then we set F to be one and then we loop round with I taking values one two three four and five and the first time through the loop we simply multiply F by I and put the result in F so it's one times one which is one the second time round I is two so we get one times two which is two the third time round I is three so we take the new value of F which is two multiply it by three and we get six the next time round I is four multiply that by six we get twenty-four the next time round I is five multiply that by twenty-four and we get a hundred-and-twenty okay and at that point we find that I is no longer less than or equal to N and so we stop this and we can return the value F at the end of this loop as the result of calculating factorial okay so that's just a loop that will loop round multiplying things together now we can also do that recursively recursively where we define the solution to one thing in terms of the solution to a simpler problem okay so we can say that N-factorial is simply N times N-minus-one- factorial so six-factorial is simply six times five-factorial five-factorial is simply five times four-factorial it doesn't matter how we get those results we can define it like that and we can write a solution directly in those terms as long as we have a base case as long as there is something that we understand how to solve directly okay so in recursion you have to have a general case of how you define a more complex problem in terms of a simpler problem and as well as that some simple problem that you can solve directly and we know that N-factorial is one when N is equal to zero and so with a recursive method you have the same heading we simply check at the beginning to see if N is greater than zero if it is we have to do some calculations if it's not we'll return the value one directly okay but if it is greater than zero we simply return the value of N times the value that we get by applying this factorial method to N-minus-one how does that work okay so if N is six we want to return six times the result of doing factorial on five okay and this shows how the recursive method works with five as an argument okay so what we do is we start out by saying N is five is N greater than zero yes so we return five times factorial of four okay but we don't know what factorial of four is yet and at the point at which we hit factorial of four there we simply make another call to this method now with N being four and we do the same thing again okay so we maintai-, we we have to maintain these results bit by bit okay we come down here before we can get the results to use back in these calculations when N is four we return four times factorial of three and we have to go round again when N is three we return three times factorial of two when N is two we return two times factorial of one and at that point when we come round again we do it once more one times factorial of zero and then this is no longer true okay so at the point where we've got zero in the sixth call to this thing we've got a value for one so we've got a value for factorial of zero which we can use when we're trying to work out factorial of one factorial of two factorial of three and so on okay we get a value of factorial-zero which is one we pass it back up to the previous calculation so we now have a fac-, we now have a value of factorial of one which we can use in the next calculation we have a value of factorial of two which we can use in the previous one and so on so it keeps going back up so we have to go all the way down to the bottom before we can use those values that we've worked out substituting them back into these calculations to get out the result at the top how many people understand that how many people don't how many people didn't put their hands up yeah [laugh] always ceases it never ceases to amaze me you know i'm going to ask you a question you know i'm going to ask you at the end how many people didn't put their hand up why you don't beats me okay there's something very important to note about this yeah sm0722: is recursion more efficient than in terms of speed nm0718: we'll get on to that it's a very good question the question is is recursion more efficient and the answer is no but we'll get on to why [laughter] the problem with this is that we have to maintain all these values we don't know what the solution to factorial-six is until we've worked out factorial-five factorial-four factorial-three factorial-two factorial-one and so on and we have to maintain all of these values all at the same time until we find the value of factorial-zero which we can use to find factorial-one and then to find factorial-two and so on so we have to maintain six sets of all the variables that are needed to work this out okay so we have to maintain six sets of that whereas in the previous example the iterative solution we only have to maintain five sets of things sorry we only m-, have to maintain one set of er variables okay so we need much more memory er with six it's not a problem with five we we work these things out on on five with N being five it's not a big deal because it's only about thirty variables okay but when we start using much larger numbers okay then it becomes prohibitive okay so recursion which is very very powerful can take up a lot of space and also it can take up a lot of time to do it can be not very powerful because of that er we're going through all of these iterat-, recursive calls but the key thing to note is that it's much nicer to write down than the other solution the other solution required a for loop we had to work various things out this simply states what the problem is it simply states that if N is greater than zero you got to work out N times factorial of N-minus-one otherwise you know the answer directly so it's much nicer much neater much simpler to do than this one okay i've got another example you don't have could someone tell me what these are er how many people know what these are okay how many people don't they're Fibonacci numbers Fibonacci numbers are simply Fibonacci numbers are simply numbers that are defined as the sum of the previous two numbers so if we start with zero and one then the next one is the sum of one and zero which is one the next one is the sum of one and one which is two the next one is the sum of two and one which is three the next one is the sum sum of three and two which is five and so on okay Fibonacci numbers very simple and this is a again something that's recursive we have to know the previous two numbers to be able to work out the next one you don't have this if you're looking through your through your notes you don't have this but it's pretty much the same as the things we've seen before it's very simple here's the whole program rather than just the method i've just got a heading saying sixth Fibonacci number is and then a call to the Fibonacci method that i've got below okay and this Fibonacci method simply takes an integer N and it has three possible cases one is that N is zero if N is zero then we return zero otherwise if N is one we return one 'cause we have to have two numbers to start with zero and one we're going to start out with at the beginning base case and if not if we're anywhere up further up then we simply return the value that we get by calling the Fibonacci method on N-minus-one added to the value that we get by calling the Fibonacci method on N-minus- two did i say N-minus-two before N- minus-one and N-minus-two okay so we simply work through that and that's all we have to do and that's simply if you look at it it's simply a statement of the problem rather than doing anything complicated anything sophisticated in terms of trying to work these things out simply states how we define Fibonacci numbers and Java will solve that problem for you okay it will go through these reci-, recursive calls trying to work it all out and again this program is in tilde-C-S-rat-slash-five-slash-jav tilde-C-S-rat-slash-Java-slash-five- er - fibo- dot-Java are there any questions how many people think they understand recursion how many people don't okay good let's write a little note about when we would use this can you see that at the back when should we use recursion and when should we use iteration okay because we can always find an iterative way to solve a recursive problem okay we can solve problems either way so the question is why bother to use recursion and the answer is when it's most natural and easily expressed we'd use iteration when efficiency matters okay if we don't have enough memory or if the solution is straightforward iteratively then we would use iteration but recursion is most useful when it's very easy to write it down okay so when it's most natural and easily expressed in every test every second test in the last five years there has been a question on recursion every single one are there any questions okay can i move this off we got one or two things to say about the assignment before we finish today the first is that you will have a new submission sheet it'll be it's a yellow one but it's new and that's because unless you are a student who is not based in Computer Science you will have shortly in your pigeonholes some bar codes okay a sheet of s-, stickers with bar codes on identifying you and what you have to do instructions are given to you but what you have to do is to take a bar code and fold up the bit of paper where it says fold line and then there's a box which will be partially obscured take your bar code and stick it like that so that it holds the paper up that's what you do that means we can't see who you are it's all done anonymously but it'll be more efficient okay so do this if you are not based in Computer Science you will fill it in as normal and hand it in to the secretaries who will then anonymize it for you we will not be giving you bar codes sm0723: nm0718: sorry sm0723: nm0718: ah you'll have a pigeonhole they'll get them to you so it's C-S C-S-E C- M-S and C-B-S will all get bar codes and these are s-, distinct from the engineering codes that you h-, may already have i haven't finished won't take long i don't mind not doing it there are three parts to assignment three you should do as many of them as possible the first part is worth seventy per cent for an extra fifteen per cent you should do the second part and for an extra f-, fifteen per cent on top of that you should do the third part that means that you can improve your mark continually so if you start early you have more chance of getting a hundred per cent okay you should be able to do all of them but i understand that for some of you it might be difficult you will have to use erase which we will cover in the next lecture the output that is given on the sheet the sample output and the output that you should be producing has no trailing spaces at the end of a line and the last line should be properly terminated that means that if you use system-dot-out-dot- print you should make sure that the last thing you do is system-dot-out-dot-print-ln to terminate your last line properly otherwise there will be problems note the new submission sheet and also the bar codes don't lose them if you lose them you will have to pay for more bar codes more bar code stickers okay the problem is in terms of matrices matrices are just collections of numbers it's not difficult if you haven't encountered matrices before there are hints on the back page and your seminar tutor will explain anything to you if you don't understand how to do it i will say a little bit more about this next time thank you