Programming Loops vs Recursion - Computerphile

Key Takeaways

a lot of interesting stuff both from the point of view of the content but also the historical context between you know when were for loops invented well that's what algol called them but prior to that fortune called them do loops and prior to that they existed in assembler so first of all what's the history and what does it get you when you can do loops but when do you run out of steam even with loops and you have to use this shock horror pure mathematicians thing that computer scientists have to learn about recursion it was a real culture shock it really was in the roughly 1940s 1950s to suddenly find out that what the theoreticians have been dribbling on about for years about recursive functions in mathematics actually was a massive massive importance for computer science back in the 40s and early 50s it was all assembler or a slightly dressed up thing called a macro assembler where you could have little routines full of you know packaged assembler instructions which could be called up as and when needed so that sort of served people for quite some time but probably one of the first high-level languages to introduce lubes was good old fortran even though that was published in 65 fortran itself goes back i think for almost 10 years before that it was invented by john bacchus and a large team of people at ibm in the 1950s many of you will know it it's an excellent language for engineering and scientific calculations it is low level i mean when you look at the nature of a fortran loop it's almost like doing it an assembler but not quite they didn't call them for loops call them do loops what i'm saying here is you package all this up were you saying repeat the following sequence of instructions which i've done with my wavy lines here keep doing them until you hit the statement with a numeric label on it of 180. the loop back from the statement labeled 180 back up to here to increment the loop counter which you're all familiar with in languages other than c it wasn't done as it would be in c by saying here's my block of stuff to be repeated it's inside these curly braces here you can see it's a lot more like assembler a lot more low level i mean there's nothing magic about 180 it could be 72 it depended on your labeling system you see implicitly here in a simple thing like this you'd start off at one every time you return back here it would reset i to be two three four so on up to and including ten it's comforting for those who were coming from a similar into high level language to see something that was only slightly higher level in sophistication than assembler was how do loops become more powerful if you like well again even in assembler and even in fortran there's no reason why you couldn't have a loop within a loop so i might have outside of all this code yet another layer of do what should we say 200 j equals one comma 20. so there might be some more statements between 180 and 200 who knows but again you see a numeric label and can you see what's happening is that for every setting of j which will start at 1 and go up to 20 for every single one of those j settings the inner loop will be running through the complete spectrum of settings of i going from 1 to 10. so you will have 200 locations are being affected here basically going through the rows and columns of a matrix all sorts of calculations in physics chemistry and particularly engineering just rely on two-dimensional arrays full of numbers either integers or scientific numbers with a decimal point and so on even hardcore assembler pros had to admit if you were doing heavy scientific programming it was nice to be a little bit more abstract and to have this sort of facility available to you now you might say well what came along to spoil the party then or how did people realize that this was wonderful but not quite enough the compiler of course has got to be tolerant and has got to be capable of compiling nested do loops correctly but what how deep would it let you nest them well i'm guessing i i would suspect that the early fortran compilers probably wouldn't allow it to go more than about 10d maximum and i think you and i sean will just be looking up what are the current limits in c i seem to remember the earliest gcc was something like 32 but i think we looked up there's some c plus nowadays allows you to do nested loops 256 deep and of course there are multi-dimensional problems that might actually need that because it it doesn't take much knowledge of higher maths to realize you've got a loop within the loop the outer loop goes around n times the inner loop is going around n times you are then coping with an n squared problem if you put the third loop inside the other two you're coping with a cubic three-dimensional problem so what we're saying is all these multi-dimensional polynomial going on exponential problems that come up quite naturally you can cope with them in nested for loops so long as they don't need to be more than power 30 or power 256 or whatever it is and you think well that should be enough for anybody there's these multi-dimensional problems you can just do them by nesting for loops and surely 256 is enough for anybody what kind of problem wouldn't it be enough for well a lot of theoretical computer scientists of my knowledge amuse me greatly when those of them that will own up to this back in the 60s people started going to lectures from mathematicians theoreticians people concerned with girdle computability and so on and of course those sort of people were very familiar indeed at a mathematical level with ackermann's function now as you know you and i we've done that one is that the most difficult the most difficult number to compute question mark we set this going four weeks ago nearly now the first few have vanished off the top so what made it so difficult well you write down akam's function and it very clearly ends up with routines calling themselves recursively in a very very complicated way now i think your average sort of engineer would be happy to say there's this thing called factorial which is five times four times three times two times one or whatever and you could do that in a loop as well as doing this fancy recursion thing but a lot of theoreticians admitted to me they saw ackerman's function and said i could try that out in fortran now what they perhaps didn't realize but it became famous by 1960s fortran is wonderful but original fortran did not do user level recursion you could write a thing called ack you could actually get it to call itself in fortran but you might have been expecting that every time it called itself it would lay out a data area for each recursive call they're called stack frames we know that now you get lots of stack frames one on top of another and as you come back through the recursion they're deleted and thrown away and you climb back into your main program fortran doesn't do that it sets aside one stack frame you keep calling yourself recursively it just tramples and it's muddy gum boots over all your data area and you end up with total garbage it no more gives you values of ackerman function and fly the moon so people said you know i then realized the importance of having user level recursion in programming languages to cope with those really hard problems that fell outside nested for loops algol was famous in that its routines could call themselves recursively and could get the right answer and for limited low order values of ackermann function very slow very slow indeed but it would come out with a right answer is there an easy to think of example of a problem or program that because ackerman feels to me like it's it's like the test bed you know when you're testing out a motor car you might take it on the track and see how fast it can go but in day-to-day life that car might only go half that speed yeah what what's the real world kind of equivalent is there such a thing real world equivalent what's something that might need to use recursion that of that complexity not many things is the answer to that i mean yes it's true that uh ackerman as you know was david hilbert's research student and the challenge was on to find something that was so innately recursive that remember is sort of generally recursive they call it as opposed to primitive recursive and simple things like factorial and indeed fibonacci are primitive recursive so i think you're right that you really are just making the point that eventually there are things that will kill you i think the the question in the middle is is there something are there pieces of program you need to write where non-trivial recursion in a sense is needed but not quite to the horrendous degree that ackman did and the answer is yes compilers is where it hit people because although early fortran did not provide user level recursion for you and me nevertheless john backus and his team implemented it in the middle 1950s i think at ibm and bacchus wrote articles afterwards basically saying we didn't know enough about recursion and even though we didn't provide it for the users of our language boy did we need it in the compiler and we invented it we ended up inventing it in orbit name the syntactic structures of what is legal in a language even at the level just of arithmetic statements can be quite recursive because you end up with brackets within brackets within brackets or with a multiplier outside on which order do you do the brackets in and you know how how many levels of bracket nesting can you have and if you don't get things sorted out correctly then you'll get the wrong answer but once again the problem could be that your users would come up with you and present you with a problem just designed to test out your compiler and whether it was robust enough to be able to cope with a high degree of nesting even just in arithmetic statements so by 1960 in algol yeah the there were enough users at the user level who could see that a modicum of recursion perhaps more complicated than factorial but not quite up to full acumen capabilities would be very nice indeed to have within your language again referring back to that original video i had a lot of really interesting mail from various people who said to me okay you said that this is an innately recursive problem and it just had to have general recursion capabilities well i