Not sure I know that video. Do you mean this one? -csXdj4WVwA Cause if so I don't get that vibe from it, more that HTML is strong is some ways and weak in others, which is true of everything! But if its some other video I would like to watch it :D
At first, I thought this was a tree traversal joke (both depth-first and breadth-first traversal are much easier when thinking recursively than with loops).
I actually thought this video would express an opinion on iteration versus recursion, and was pleasantly surprised to receive an overview of the history of recursion in programming languages. For all but the simplest recursive functions, iteration is necessary to avoid stack overflows. Don't forget to memoize or you'll be waiting hours for large fibonacci numbers or factorials.
I love his analogy about running recursive functions with only one stack frame in FORTRAN: "tramples in its muddy gum-boots over ALL your data area and you end up with total garbage!" Brailsford is the best.
I'm sitting here as a Kentucky born speaker of English, hearing that line, and reflecting, "Yeah, computer science did start in England, didn't it?" (This Kentucky boy has traveled to Bletchley Park).
My old IT teacher told us to look up the definition of recursion in his IT lexicon. We checked the index at the back (that wasn’t numbered itself) and it had a number for the page recursion could be found. We started paging through from the middle only to make our way back to the same page…
These videos are amazing and this guy is a treasure. Thank you, and him, so much for putting these up! There is so much noise in compsci, and so many folks who want to prove their intelligence by making subject matter harder than it has to be - it's refreshing to see somebody who knows it well enough that they can explain it like it's simple!
Agreed. Recursions being a loop in a loop makes sense to me. That description is recursive, I think, where a loop is the base. Did I get it right or not? If not, please correct me.
What a beautiful time we live to have a lecture of this amazing human being avaible at any time and anywhere in the globe! I wish he was my grandpa, I would be alredy a good programer when a kid! Thank you so much for this master piece whoever is responsible for that!
Just to say that I'm proud to be part of this band wagon, where I'm just constantly baffled with the ingenuity and humbleness that resides in science that helps me and others to hopefully build better tools that can improve our society. Thank you for your time, passion and kindness.
this man is one of those rare people who you like to keep listening to and learn from!! RESPECT! I wish i could be your student! Really knowledgeable and explaining things really nicely. I must admit I learned from you here, even after almost 17 years of programming experience.
Fortran 77 was still what I used in the 80's in high school. I can remember writing a program that would calculate how many days old you were based on your birth date. Now that may not seem like a lot, but considering leap years and the odd number of days actually in a year (it's like 365.25) it was quite the feat. I can remember at the end of class saving my work to this huge IBM floppy that was like 10 inched in diameter and putting it in a special storage vault that was grounded and static free. Ah..back in the day...
When I was a baby programmer in 1973 (Lanchester Polytechnic, Algol 60, ICL 1903) I discovered the joys of designing on 132 character fanfold stationery. It’s refreshing to see that “real” programmers still use it. Anyone know where I can buy a box in the UK? I code for fun nowadays using eight and sixteen embedded system bit chips, no operating system, and it’s interesting to see how many of the tricks we used back then are still useful today. I still much prefer to write code on paper and think it through before I type it into the IDE. And wide fanfold stationary is just the thing! I love these lectures by the way. Always something new to learn!
+Stephen Farthing great stuff! I got the paper from here: www.paperstone.co.uk/paper/listing-paper-computer/computer-listing-paper-1-part-11-inch-x-389mm-white-green-ruled-box-2000-sheets/p-25782
Realise this was a year ago but some of the big stationers in the UK like Ryman and Staples may stock it online - I was looking at buying about 6mo ago
How on earth does this video only have 1.2M views after 4 years? Very informative explanations by someone who is able to succinctly explain these concepts. I would have thought that on platforms like youtube where so many people want to learn programming, that this would have received so many more views. Take some time out of your busy life watching cat videos and watch this.
I love watching Professor Brailsford videos, he makes me appear super knowledgable at work when we have a tech problem and I take everyone back to (first) Brailsford Principles
I love this historical narrative of concepts and algorithms, what a fantastic idea to capture these in conversation and put them on TH-cam, thanks for sharing.
I have watched so many videos since discovering this channel; fascinating. It's incredible how early in time very advanced features of programming languages were conceptualised/invented
Practical example - The first time I used recursion was to parse a directory structure in C. Using findfirst/next in my function, I would check to see if the file type was another directory (folder). If it was, the function would go into to that folder, then call itself. It would do that until it reached the depth of the current branch of the tree, process the files therein, stop, and exit back to the previous place it had left off. Eventually it would make it's way back to the top. This of course was a memory hog. So I had to track that. To test it I wrote batch code that created massively large file structures. Never had it run out of ram. And that was back in the late 80's using Turbo C by Borland.
256 nested loops in C++... I've often wondered how many inner loops Eclipse ( Java ) could stomach....I become gunshy at just three or four. I like this old guy. I want to be in HIS class. He probably actually knows an instruction set, or two.
@Rooflesoft Games ok, so... Java is a general purpose programming language. The programs run inside something called a 'Java Virtual Machine' or JVM which allows the program to be run on different types of computer. These JVM's are incredibly well written to the point where a typical program can run at almost 'native speed' (That is the speed an equivalent programs would run if it were written specifically for that machine). Java's biggest critics tend not to like the language much, but do like the JVM. Consequently there are a raft of newer languages that also run on the same JVM. If you want to Google them you could start with Scala, Kotlin, Groovey, Jython. There are more. Microsoft's C# runs in its 'run time environment' which is similar to a JVM. It's not as portable, but that isn't a problem as there isn't the same requirement that it should be. The C# run time provides the same memory management functionality as a JVM and faces similar issues. Equivalent programs written in C# and Java run at comparable speeds. Do not confuse Java and JavaScript - although the names are similar they have nothing in common. JavaScript is really just for web applications and normally runs inside a web browser. You would be right to say JavaScript is slow in comparison to other languages, including Java or C#. That said, It does what it does well enough for most users. I hope that sorts the confusion out
@Rooflesoft Games you are right in saying that this is a 'historic reputation'. The complaints you make have not been true for almost 20 years. JIT technologies have largely done away with interpreting byte codes. Ironically the greatest payoff for a JIT would be for nested loops! The garbage collection algorithms have also been rewitten several times and have long since eliminated the problems you describe. If you don't like garbage collection cutting in then you would have to use a much older language, for example C. This is because all modern language, including C#, have automatic memory management. JavaScript does still have these problems, but that is another story.
Excellent episode! I learned some new things about compiler history with this one, and Professor Brailsford's fantastic level of precision and clarity of thought makes this video so enjoyable.
Anecdotal details like: "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 ended up inventing it in all but name" are awesome insights into invention in general.
Not only do compilers need recursion, but many high-level programming constructs such as object-oriented programming mandate recursive constructs. If you can't abstract instances of an object, the entire paradigm collapses.
I've only had one clear instance where recursion was the better option over a series of nested loops. I had to step down branches of a family tree and didn't know the length of each branch..when the branch ended, and the person no longer had any more children, it would recurse back up the tree and go down the next branch. It was probably the most excited I had ever been about any function I ever wrote, haha
FORTRAN IV (FORTRAN 4) was my first computer language. And I had to punch cards. You numbered lines but only those you were interested in. The numbers did not have to be anything special except that subsequent numbers had to be higher. Variables starting with i, j, k, l, m or n were integers. What I liked about it is that you can declare a multidimensional "matrix" rather than the "arrays" that we have now. This made addressing a particular element more logical as you thought of it in exactly the same way that you did in matrix algebra. This was like the DIM statement in BASIC except in FORTRAN, the keyword is spelled out completely--DIMENSION. (I'm not shouting. These words are written in all caps.)
If I may recursion seems to do well when dealing with any tree like structure. For example if you want to know how many files are on your hard drive the simplest way to do it would be to have a function that counts all the files in a directory, and calls itself to count the files in sub directories.
Recursion is cute in theory but some languages have limits on how many calls you can have in a chain (t-sql), it also can chew up a lot of RAM needlessly (because of the calls and their associated data sitting waiting for a return from the from the deepest call.
@@MichaelSmith-fg8xh And smaller microcontrollers with very limited RAM, especially the little eight bit ones. Something like a PIC or MC9S08 or 8051. Something like 2k to 60k of code space in ROM, but maybe 32 bytes or 256 bytes of RAM, including the stack. The stack fills up very quickly on those machines.
@@MichaelSmith-fg8xh Recursion isn't just "cute in theory". It's the only way to traverse trees, where not only the lengths of the loops but even the amount of nesting is unknown until runtime. If your recursive code uses too much memory, you're doing it wrong. It means you're making a recursive call before the current call is finished. The recursive call needs to be a tail call, i.e. the very last computation in the function. That way the currently allocated space in the stack can be re-used.
@@MichaelSmith-fg8xh Baloney. Please explain how or STFU. The various depths and branching ratios in the tree are arbitrary and unknown at compile time. A filesystem, AST, mathematical expression, AI search tree, organizational chart, any tree-shaped data structure.
A lot of the times when you are considering the alternatives loop or recursion, you should also consider "higher-order" funtions, such as map, reduce (or fold), and filter. Example Pseudocode: Take the prices of all items cheaper than $10, multiply them by 0.8 and add them together: reduce(lambda x,y: x+y, map(lambda p: p*0.8, filter(lambda item: item.price < 10, items))) Preferred way in python: sum([item.price*0.8 for item in items if item.price < 10])
The first time I used recursion was during my IT graduating course (1990's). I used it to write a Huffman algorithm based compressing/decompressing program. At that time, I was starting to use Borland's Turbo C, so I was not familiar with it's debugging resources. Needless to say, my first code had a flaw (probably during decompressing) and I used pencil and paper 'Chinese computing' to figure it out (I was loosing track of the recursion level the program was at, so I was not able to identify the tree's root, when coming back from the leaf search). I figured it out, on paper, included a recursion level register and the program run perfectly. To add to my self-pride, I was the only one that came up with a recursive solution (that, to me, seemed more intuitive/simple/practical). Anyway... kudos to the Computerphile team.
Recursive functions are indeed part of Fortran. I used a QuickSort recursive function in my research. F77 supported recursion on some systems, but the recursive attribute did not become standard until Fortan90 and used the keyword RECURSIVE..
When I was a computer science major back in the late seventies we were assigned a program that would load and parse a binary tree. We studied both recursive and non recursive approaches but did not have a compiler that supported recursion. A couple years later we had a system with a Pascal compiler. I wrote the binary tree program in Pascal using recursion and it was far simpler than the original Fortran IV code.
In my CS program in college, the intro courses were taught in a functional language called Scheme. I thought it was bonkers at the time. But over the years, I've realized that recursion is the more essential way of viewing problems. If you can solve a problem recursively, you truly understand it. Then you can transform the solution into iterative style trivially, if you need to (like if you're in a language without tail call elimination, etc.). I wish I knew how to explain this to new graduates.
I find that recursion really forces you to think about the full state your system is in at each iteration in a loop. You have to manage not only the counters, but also keep track of accumulators and the transformations from state to state in a more hands-on way than just letting the language set a variable and run with it. When I write the loop in a tail recursive style, I often find that the operations I was making could be rewritten in a clearer way, or even some optimization could be done at the transformation stage to make the unfolding statement be much more concise. This awareness is what I miss the most when writing loops.
Dr. Brailsford's video caused me to remember learning the DO loop from my self-paced "green book" IBM 1130 Fortran circa 1967 using mark-sense punch cards. There being no requirement for declarative typing at that time, the choice of "I" as the iterator variable was no accident. Variables beginning with the letters I-N inclusive defaulted to integer. When learning DEC PDP-8 assembler a few years later, I remember wondering if I could "park" the state of my program somehow in order to make it re-enterable or to do something recursively. Regrettably it was a fairly unsophisticated TSS-8 time-sharing system shared by a number of local schools and I was a VERY unsophisticated 10th grader with entirely too much time on my hands. Most of my serious experiments resulted in crashing the entire system. Once I figured out how to do it reliably, the learning stopped and the deliberate mayhem began. It didn't end well for me or that particular system. Thank you for the memories Dr. Brailsford !
Sounds to me like the problem is more about the artificial limitations of loops vs recursion rather than any inherent difference between the two. For instance, I tried coding up the Ackermann function in PHP only to find that it also implements a 256 stack frame limit, like the limit for C++'s nested loops.
Recursion is very useful in situations where you have dynamic parent-child-with child- another child- etc relationships. Think of tree structures, recursion is very handy for that.
Programming for 1.5 year and used for: - Backtracking (sudoku solver) - Backtracking (removing all possible sudoku numbers while keeping a single solution) - An react clone (element tree creation, deep comparission, and tree reconcilation) - Literally tree (had to write an quick and dirty "tree" copy in dart) - Contributing on the AST of an language - Pauling diagram (looks cleaner with recursion imo) - SVG parser - SVG renderer - Lots of small utils I absolutely love recursion, wish i had to use it more.
Real world equivalent of Ackermann using recursive techniques is dealing with Bill of materials on complex produced objects. You never know how far down any branch in the tree will go and you need to traverse the tree to, for example, calculate total cost estimate or perform some engineering action on them all. Less of a problem by the time the BOM is finalised because you can flatten it and deal with the flat list but I've had to write recursive programs at work to do this sort of thing in our engineering system. Luv and Peace.
I remember writing a program to draw a dragon curve (A primitive fractal) on a Sinclair ZX81. Took about 60 lines of basic with every variable having to be an array so it could have different values depending on the depth of the recursion. And it had goto jumping out of one for next loop and into another, quite horrid. Did the same thing many years later in 4 lines of logo.
If you don't have recursion, just build the stack yourself. CPUs aren't magic and don't do anything special when they "call a function". They just put the current state on a stack, jump to the function, let it run, then pop the state from the stack and go along. Easily done in a loop. You just build it on the heap instead of relying on the (usually much more limited, at least in the past) system stack.
Trees, best way to update trees is via recursion. Ok you can do it using iteration, but recursion is much nicer. (OK I suppose Professor Brailsford covered this by talking about compiler AST's)
For the most robust implementation, what can be done in a loop should be written so. Recursive function calls only work until a few hundred levels of depth, which is extremely easy to exceed. For example, a linked list is a simple tree, and you can agree that iterating it recursively, you'll run out of memory in less than a microsecond. It's actually pretty easy to traverse trees and graphs using simple loops, without any recursion, once you get used to it, and such code can be very readable and maintainable. Might be a challenge for the first time you're doing it, but easy afterwards. All you need is a container where you can push and pop items, and you're only limited by the physical memory, not by the size of the function call stack.
I should have said "theoretically the best way", but in a practical sense you are right. The stack is only limited by so called "soft limits", (In Linux its usually 8192kb, in windowsNT its a measly 1024Kb) I think these are put in place by the operating system to prevent infinite recursion. There is no practical reason why your stack cannot occupy the all of the memory available in the virtual address space. I agree though when handling large data structures, you have to use loops and stack like container data structures.
Back in my college days I found a way to do recursion in FORTRAN, at least with the HP compiler there. I don’t remember how it was, but wasn’t complicated. I’ve also made a chess playing program using recursion in Pascal, which was very compact. It even had alpha-beta pruning. Academical interest, there is a theorem that proves that everything done with recursion can be done with loops as well.
Well even if a language doesn't have recursion explicitly built in the programmer can code it themselves anyway. I normally avoided recursion because the vast majority of time for a given problem it would be less efficient than other methods. Sometimes tho it is better to use recursion because not using it could involve the code getting ridiculously complicated.
I have used recursive functions in every one of my major programs. About 1 in 1000 of my functions where recursive in well over 1 million lines of code over 45 years. Obviously recursion is MUCH more important than plain Jane loops. I am sure if I had been a professor rather than a developer I would have used recursion more.
As someone who is writing an operating system, this video proved to show me that recursion on the stack can eventually pop. So long as you have a heap fallback, everything should run smoothly. I wonder how much static local variables in C could reduce the amount of recursive intensity recursion brings by allocating more stack frames.
My typical example for something requiring recursion is traversing a tree. Or, since I'd mostly explain this to new students, a file system. (Which is a tree, even if they don't know that) If you can have folders within folders, arbitrarily deep, you have to use recursion.
125m125: Using for loops? Not a chance, recursive is much clearer. If it's even possible with a loop. I'm pretty sure traversing a tree is impossible to do iteratively.
I've seen many for loops that handle trees in JavaScript. It's the usual way to handle the DOM, which is a tree. Granted, it works because each DOM node effectively carries a pointer to its parent node, but that's also true of file systems. I guess if there wasn't such a pointer, you'd have to keep pointers to where you've been. But it still could be done. Documents can contain a lot of nodes, and, even now that recursion limits are removed, JavaScript still can easily run out of memory. It's why I always convert common algorithms to iterative form.
I guess Yndostrui is right that it is impossible with simple counting for-loops. But it is possible with a single while-loop and a stack-like data structure.
When I was in college I was a bit concerned about being called upon to come up with an original recursive solution sometime in the course of my professional career. I finally faced that challenge 15 years later. The requirement was to process a tree structured database and produce an MFC tree UI. I was relieved that I was up to the challenge. Anyway, my main point refers to the GOTO video emphasis on documentation. I made sure that there was plenty of documentation embedded with that code and warning to be very careful with changes here.
Back in university I tried using FORTRAN exactly one day. I started reading the textbook of FORTRAN 77 (or whatever version) and I wanted to try writing a simple "Hello world" type of program with it. I copied one of the first example programs from the book to a file in university's main computer and I tried compiling it. After a few rounds of correcting my typos I finally got it compiled. Then I tried to run it. ERROR. I gave up any ideas I might have got aboout FORTRAN. I had much better success writing C some months later (and ever since).
Professor Brailsford seems to have a very nice collection of books. As a collector of old computers and ephemera I would love to see what else he has in his shelves. I think I spot a teletype manual in the top left shelf. Thank you.
Fortran programmer here. Thank you professor Brailsford for admitting it's great for engineering. You probably already know this, as you called it "original Fortran" or "early Fortran". I'm being pedantic here, but you're using some very antiquated Fortran standards (we have a 2015 standard!). First, Fortran is not so low-level. We have recursive subroutines (or "functions", for you C devs)! We also have user-defined types, implementing everything you can do with C structures. Second, you don't need numerically-labelled do-loops anymore. We now have "do ... end do", instead of "do 180 ... 180". You can even label them with a literal string if you're that kind of psychopath. I would love brackets instead, but not even python has bracketed loops.
He's presenting how loop and recursion first appeared in higher level programming language, using the original format and showing its low-level-ness is the sensible way to go. And as you mentioned, he did say it's "original FORTRAN". --- Another Fortran programmer.
OTOH, python has syntactically meaningful white space. That's kinda the same thing as using brackets. At least when compared to using gotos with either labels or line numbers.
Ok, I want you to use fortran, and make a program that calculates '1000!', it has to do it with normal looping, 1*2*3*4*5*6*....999*1000 Once done, inform me of the first few digits and the last few digits of the answer and most importantly, tell me how long it took for the program to calculate it.
When I first came in contact with recursion - back in the 90s in Turbo PASCAL 7 - it scrambled my mind. I just didn't get it. The same was true for pointers when we used them to create linked lists. But when the teacher got us the task to read the linked list recursive, instead of completely blowing up my mind, everything fell into place. I have to say it took several years since then till I completely understood those concepts.
256 is a recommended minimum for C++11 nested control structures. It's not a hard limit by any means, and is, in the end, implementation-defined. After all, it's easy enough to have a kinda-nested loop with conditionals and goto. Any assembler that has conditional jump has no hard limits on loop nesting at all. Generally speaking, recursion is just a useful abstraction over loops and call stack -- it's entirely possible to code that by hand. Or, depending on your perspective, recursion is fundamental and loops and call stack are implementation detail. So... there isn't all that much difference.
I rewrote a Btree+ altorithm without recursion. It was difficult, but now I know exactly its limits because I can debug it and measure the stack use, thus it's easier to see which is the worste case. With recursion, algorithms are easier to write but more more complex to be debugged and the stack usaged is more complex to be predicted for the worst case.
How to test if your compiler removes tail recursion in favor of a loop: let it run a few thousand times and see if you get a stack overflow or out of heap space error XD
I find it fascinating that such a elemental concept was a novelty back then. Btw. you can emulate recursion with loops if you have implemented a stack data structure. Basically that's what the language does when it implements recursive functions - each "instance" of a function has their own stack frame, and they together form an implicit stack.
4 ปีที่แล้ว +3
In general, loops vs. recursion: - A loop almost always performs better than recursion. - For really easy problems, it's often easier to write a loop than recursion. In this case, use the loop. - For most other problems, except the easiest ones, recursion is often much easier to figure out than a loop, but it typically suffers in performance. However, use recursion if it makes the code easier to understand, even at the cost of performance. Often, the performance cost is negligible, but even if it isn't, difficult code often hides bugs and is a nightmare to maintain or modify. And if performance is critical, it is easier to later optimize code that you understand, instead of writing already optimized, but difficult to read code.
I love the way loops were animated in this video. I've never seen it done that way.
+smergibblegibberish thanks >Sean
me too
Im not even a programmer and that made sense to me
When they were animated like that, I realized I always seem to look at loops like that.
That's the most intuitive way to explain it and actually shows why they're called loops
The depth and breadth of Professor Brailsford's computer science, logical and philosophy pedagogical ability is really astounding
Christopher Willis I resent a video of him explaining why HTML is better than C. Apples and oranges 101...
Not sure I know that video. Do you mean this one? -csXdj4WVwA Cause if so I don't get that vibe from it, more that HTML is strong is some ways and weak in others, which is true of everything! But if its some other video I would like to watch it :D
At first, I thought this was a tree traversal joke (both depth-first and breadth-first traversal are much easier when thinking recursively than with loops).
I actually thought this video would express an opinion on iteration versus recursion, and was pleasantly surprised to receive an overview of the history of recursion in programming languages. For all but the simplest recursive functions, iteration is necessary to avoid stack overflows. Don't forget to memoize or you'll be waiting hours for large fibonacci numbers or factorials.
Christopher Willis
This professor's knowledge of computer programming history is just awesome to listen to.
I love his analogy about running recursive functions with only one stack frame in FORTRAN: "tramples in its muddy gum-boots over ALL your data area and you end up with total garbage!" Brailsford is the best.
englishmen
I love the topics this guy presents. =D
Yeah, I loved that line.
I'm sitting here as a Kentucky born speaker of English, hearing that line, and reflecting, "Yeah, computer science did start in England, didn't it?" (This Kentucky boy has traveled to Bletchley Park).
ok?
This video had some excellent and illustrative animations. The "nested loop" animation was super cool. Cheers to the animator!
false.
My old IT teacher told us to look up the definition of recursion in his IT lexicon. We checked the index at the back (that wasn’t numbered itself) and it had a number for the page recursion could be found. We started paging through from the middle only to make our way back to the same page…
Oh this is great, A first hand experience with it 😂
These videos are amazing and this guy is a treasure. Thank you, and him, so much for putting these up! There is so much noise in compsci, and so many folks who want to prove their intelligence by making subject matter harder than it has to be - it's refreshing to see somebody who knows it well enough that they can explain it like it's simple!
Agreed. Recursions being a loop in a loop makes sense to me. That description is recursive, I think, where a loop is the base. Did I get it right or not? If not, please correct me.
THIS is what the internet has been invented for!
This and cats of course. 🤣
false.
To understand recursion, you must first understand recursion..!
Or watch the movie Inception.
You got exit condition missing. Stack busted.
I'm still working on understanding cursion.
I can understand it if part of it is simple and I understand the rest of it.
or place a mirror in front of another
when an OG like this talks about recursion, you watch and listen
false.
What a beautiful time we live to have a lecture of this amazing human being avaible at any time and anywhere in the globe! I wish he was my grandpa, I would be alredy a good programer when a kid! Thank you so much for this master piece whoever is responsible for that!
Just to say that I'm proud to be part of this band wagon, where I'm just constantly baffled with the ingenuity and humbleness that resides in science that helps me and others to hopefully build better tools that can improve our society. Thank you for your time, passion and kindness.
this man is one of those rare people who you like to keep listening to and learn from!! RESPECT!
I wish i could be your student! Really knowledgeable and explaining things really nicely.
I must admit I learned from you here, even after almost 17 years of programming experience.
true,
but damn
۱۷ سال سابقه
البته الان ۱۸ میشه
so i got curious, i searched your name wish i could see your github page but there was none :(
I thoroughly enjoy this professor's talks. He has an amazing grasp on both the subject matter and ability to explain things.
11:27 - "...and if you don't get things sorted out correctly then \*prff\*..." - I completely agree.
Was that a fart?
no it was a fact
no it was Fartran
Lol. I figured I wasn't the only one who noticed.
I had to rewind it 3 times to check haha
I loved the demonstration of a nested for-loop. Beautiful imagery.
Fortran 77 was still what I used in the 80's in high school. I can remember writing a program that would calculate how many days old you were based on your birth date. Now that may not seem like a lot, but considering leap years and the odd number of days actually in a year (it's like 365.25) it was quite the feat. I can remember at the end of class saving my work to this huge IBM floppy that was like 10 inched in diameter and putting it in a special storage vault that was grounded and static free. Ah..back in the day...
Impressive!! Especially in such a low level language as fortran
what do you do now a days ?
@@ishansinha1336 A mouse and Windows 10. That's it. No computer programming for me
Love the vids with you Pr. Brailsford, you remind me my philosophy professor, like a giant pile of knowledge and wisdom. I could hear you all the day.
When I was a baby programmer in 1973 (Lanchester Polytechnic, Algol 60, ICL 1903) I discovered the joys of designing on 132 character fanfold stationery. It’s refreshing to see that “real” programmers still use it. Anyone know where I can buy a box in the UK? I code for fun nowadays using eight and sixteen embedded system bit chips, no operating system, and it’s interesting to see how many of the tricks we used back then are still useful today. I still much prefer to write code on paper and think it through before I type it into the IDE. And wide fanfold stationary is just the thing!
I love these lectures by the way. Always something new to learn!
+Stephen Farthing great stuff! I got the paper from here: www.paperstone.co.uk/paper/listing-paper-computer/computer-listing-paper-1-part-11-inch-x-389mm-white-green-ruled-box-2000-sheets/p-25782
Realise this was a year ago but some of the big stationers in the UK like Ryman and Staples may stock it online - I was looking at buying about 6mo ago
How on earth does this video only have 1.2M views after 4 years? Very informative explanations by someone who is able to succinctly explain these concepts. I would have thought that on platforms like youtube where so many people want to learn programming, that this would have received so many more views. Take some time out of your busy life watching cat videos and watch this.
Those circles are the most perfect representation of a loop I ever seen.
Hmmm. That’s just how they always looked in my head. I miss programming.
That explanation of Fortran recursive calls trampling existing data and producing garbage was beautifully illustrated.
This is truly fascinating to listen to. I would love to attend his lectures, even casually.
The animations that exemplify the loop was very impressive and self explanatory.
I love watching Professor Brailsford videos, he makes me appear super knowledgable at work when we have a tech problem and I take everyone back to (first) Brailsford Principles
I love this historical narrative of concepts and algorithms, what a fantastic idea to capture these in conversation and put them on TH-cam, thanks for sharing.
It's always interesting to see how things evolved in computer science. Also glad you asked about a real-world "Ackermann" equivalent
I have watched so many videos since discovering this channel; fascinating. It's incredible how early in time very advanced features of programming languages were conceptualised/invented
Practical example - The first time I used recursion was to parse a directory structure in C. Using findfirst/next in my function, I would check to see if the file type was another directory (folder). If it was, the function would go into to that folder, then call itself. It would do that until it reached the depth of the current branch of the tree, process the files therein, stop, and exit back to the previous place it had left off. Eventually it would make it's way back to the top. This of course was a memory hog. So I had to track that. To test it I wrote batch code that created massively large file structures. Never had it run out of ram. And that was back in the late 80's using Turbo C by Borland.
It is fantastic feeling to finally understand something. As it is with this channel after years of my studying.
This guy should narrate nature shows. He's like the David Attenborough of mathematics.
Yes, but there’s already enough about nature. We need more mathematics.
More like computer science. This is computerphile anyways. He is not an official mathematician.
@@brunodosreis Agreed.
false.
I love Professor Brailsford, he's such a captivating educator and speaker.
256 nested loops in C++... I've often wondered how many inner loops Eclipse ( Java ) could stomach....I become gunshy at just three or four.
I like this old guy. I want to be in HIS class. He probably actually knows an instruction set, or two.
Java should be illegal.
@Rooflesoft Games why? It makes perfect sense and is done all the time
Slow compared to what? Java isn't slow.
@Rooflesoft Games ok, so... Java is a general purpose programming language. The programs run inside something called a 'Java Virtual Machine' or JVM which allows the program to be run on different types of computer. These JVM's are incredibly well written to the point where a typical program can run at almost 'native speed' (That is the speed an equivalent programs would run if it were written specifically for that machine). Java's biggest critics tend not to like the language much, but do like the JVM. Consequently there are a raft of newer languages that also run on the same JVM. If you want to Google them you could start with Scala, Kotlin, Groovey, Jython. There are more.
Microsoft's C# runs in its 'run time environment' which is similar to a JVM. It's not as portable, but that isn't a problem as there isn't the same requirement that it should be. The C# run time provides the same memory management functionality as a JVM and faces similar issues. Equivalent programs written in C# and Java run at comparable speeds.
Do not confuse Java and JavaScript - although the names are similar they have nothing in common. JavaScript is really just for web applications and normally runs inside a web browser. You would be right to say JavaScript is slow in comparison to other languages, including Java or C#. That said, It does what it does well enough for most users.
I hope that sorts the confusion out
@Rooflesoft Games you are right in saying that this is a 'historic reputation'. The complaints you make have not been true for almost 20 years. JIT technologies have largely done away with interpreting byte codes. Ironically the greatest payoff for a JIT would be for nested loops! The garbage collection algorithms have also been rewitten several times and have long since eliminated the problems you describe. If you don't like garbage collection cutting in then you would have to use a much older language, for example C. This is because all modern language, including C#, have automatic memory management.
JavaScript does still have these problems, but that is another story.
Excellent episode! I learned some new things about compiler history with this one, and Professor Brailsford's fantastic level of precision and clarity of thought makes this video so enjoyable.
11:28 - "If you don't get things sorted out correctly then..." *shrugs and farts* lol
I can't believe I missed that. 😂
That was his voice, he oozed the air out of his windpipe, like when you are in a doubtful situation.
You grow up.
it was not a fart, it was a mouth thing.
Pete Allen hahaha made my day
This dude is a treasure-trove of knowledge. Keep making these videos, please.
Those who animated the video deserve a raise.
4:12 This nested loops animation is the best I've ever seen! 👏👏
I love when the Professor talks! everything seems understandable :)
Anecdotal details like: "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 ended up inventing it in all but name" are awesome insights into invention in general.
Also, binary search tree's are often a real world example of a good place to do recursion
I couldn’t imagine how painful a google search would be without recursion and BST structure
Parsing (as mentioned) is PURE tree walking (nested, many times)... Parsing is one of the heaven for recursion.
Chris LeeWoo That’s... Not how google works
The function to follow or create the tree need not be recursive.
Yes, you could use a stack to cache the alternate routes and do them later.
Not only do compilers need recursion, but many high-level programming constructs such as object-oriented programming mandate recursive constructs. If you can't abstract instances of an object, the entire paradigm collapses.
I've only had one clear instance where recursion was the better option over a series of nested loops. I had to step down branches of a family tree and didn't know the length of each branch..when the branch ended, and the person no longer had any more children, it would recurse back up the tree and go down the next branch. It was probably the most excited I had ever been about any function I ever wrote, haha
FORTRAN IV (FORTRAN 4) was my first computer language. And I had to punch cards. You numbered lines but only those you were interested in. The numbers did not have to be anything special except that subsequent numbers had to be higher. Variables starting with i, j, k, l, m or n were integers. What I liked about it is that you can declare a multidimensional "matrix" rather than the "arrays" that we have now. This made addressing a particular element more logical as you thought of it in exactly the same way that you did in matrix algebra. This was like the DIM statement in BASIC except in FORTRAN, the keyword is spelled out completely--DIMENSION. (I'm not shouting. These words are written in all caps.)
The moment he said "recursion" and "compilers" in the same phrase, I had chills going up and down my spine.
I could listen to this gentleman talk about computer science for hours on end
I would Love to attend his lectures, his is just some sort of Computer Passionate.
Phrase of the day, 8:30 "Tramples in its muddy gumboots"
I love this overall explanation by Prof. Brailsford
If I may recursion seems to do well when dealing with any tree like structure. For example if you want to know how many files are on your hard drive the simplest way to do it would be to have a function that counts all the files in a directory, and calls itself to count the files in sub directories.
Recursion is cute in theory but some languages have limits on how many calls you can have in a chain (t-sql), it also can chew up a lot of RAM needlessly (because of the calls and their associated data sitting waiting for a return from the from the deepest call.
@@MichaelSmith-fg8xh And smaller microcontrollers with very limited RAM, especially the little eight bit ones. Something like a PIC or MC9S08 or 8051. Something like 2k to 60k of code space in ROM, but maybe 32 bytes or 256 bytes of RAM, including the stack. The stack fills up very quickly on those machines.
@@MichaelSmith-fg8xh Recursion isn't just "cute in theory". It's the only way to traverse trees, where not only the lengths of the loops but even the amount of nesting is unknown until runtime.
If your recursive code uses too much memory, you're doing it wrong. It means you're making a recursive call before the current call is finished. The recursive call needs to be a tail call, i.e. the very last computation in the function. That way the currently allocated space in the stack can be re-used.
@@Raging.Geekazoid You can explore trees without recursion.
@@MichaelSmith-fg8xh Baloney. Please explain how or STFU. The various depths and branching ratios in the tree are arbitrary and unknown at compile time. A filesystem, AST, mathematical expression, AI search tree, organizational chart, any tree-shaped data structure.
It's always a great pleasure to listen to Professor Brailsford!
A lot of the times when you are considering the alternatives loop or recursion, you should also consider "higher-order" funtions, such as map, reduce (or fold), and filter.
Example Pseudocode:
Take the prices of all items cheaper than $10, multiply them by 0.8 and add them together:
reduce(lambda x,y: x+y,
map(lambda p: p*0.8,
filter(lambda item: item.price < 10, items)))
Preferred way in python:
sum([item.price*0.8 for item in items if item.price < 10])
11:32 That fart was perfectly timed, Professor Brailsford!
Excellent animations in this video, as always.
+igNights77 thanks, I appreciate that! >Sean
The first time I used recursion was during my IT graduating course (1990's).
I used it to write a Huffman algorithm based compressing/decompressing program.
At that time, I was starting to use Borland's Turbo C, so I was not familiar with it's debugging resources.
Needless to say, my first code had a flaw (probably during decompressing) and I used pencil and paper 'Chinese computing' to figure it out (I was loosing track of the recursion level the program was at, so I was not able to identify the tree's root, when coming back from the leaf search).
I figured it out, on paper, included a recursion level register and the program run perfectly.
To add to my self-pride, I was the only one that came up with a recursive solution (that, to me, seemed more intuitive/simple/practical).
Anyway... kudos to the Computerphile team.
Recursive functions are indeed part of Fortran. I used a QuickSort recursive function in my research. F77 supported recursion on some systems, but the recursive attribute did not become standard until Fortan90 and used the keyword RECURSIVE..
The professor is really the star of this channel.
I rarely understand anything this man is saying, but I watch anything with him anyway because he is so damn charming.
When I was a computer science major back in the late seventies we were assigned a program that would load and parse a binary tree. We studied both recursive and non recursive approaches but did not have a compiler that supported recursion. A couple years later we had a system with a Pascal compiler. I wrote the binary tree program in Pascal using recursion and it was far simpler than the original Fortran IV code.
I felt warm inside when he mentioned do loops in fortran. I programmed in it fir 4 years.
I barely understand this but just seeing a guy so passionate about his stuff makes me feel good :)
"It no more gives you values of Ackermann's function than flies you to the moon" - Amazing quote.
Finally a comprehensive and simple answer to recursive question!
In my CS program in college, the intro courses were taught in a functional language called Scheme. I thought it was bonkers at the time. But over the years, I've realized that recursion is the more essential way of viewing problems. If you can solve a problem recursively, you truly understand it. Then you can transform the solution into iterative style trivially, if you need to (like if you're in a language without tail call elimination, etc.).
I wish I knew how to explain this to new graduates.
I find that recursion really forces you to think about the full state your system is in at each iteration in a loop. You have to manage not only the counters, but also keep track of accumulators and the transformations from state to state in a more hands-on way than just letting the language set a variable and run with it. When I write the loop in a tail recursive style, I often find that the operations I was making could be rewritten in a clearer way, or even some optimization could be done at the transformation stage to make the unfolding statement be much more concise. This awareness is what I miss the most when writing loops.
Dr. Brailsford's video caused me to remember learning the DO loop from my self-paced "green book" IBM 1130 Fortran circa 1967 using mark-sense punch cards. There being no requirement for declarative typing at that time, the choice of "I" as the iterator variable was no accident. Variables beginning with the letters I-N inclusive defaulted to integer. When learning DEC PDP-8 assembler a few years later, I remember wondering if I could "park" the state of my program somehow in order to make it re-enterable or to do something recursively. Regrettably it was a fairly unsophisticated TSS-8 time-sharing system shared by a number of local schools and I was a VERY unsophisticated 10th grader with entirely too much time on my hands. Most of my serious experiments resulted in crashing the entire system. Once I figured out how to do it reliably, the learning stopped and the deliberate mayhem began. It didn't end well for me or that particular system. Thank you for the memories Dr. Brailsford !
Sounds to me like the problem is more about the artificial limitations of loops vs recursion rather than any inherent difference between the two.
For instance, I tried coding up the Ackermann function in PHP only to find that it also implements a 256 stack frame limit, like the limit for C++'s nested loops.
His understanding of for loop is the BEST!!!!! explanation EVER!!!!!!!
Recursion is very useful in situations where you have dynamic parent-child-with child- another child- etc relationships.
Think of tree structures, recursion is very handy for that.
Programming for 1.5 year and used for:
- Backtracking (sudoku solver)
- Backtracking (removing all possible sudoku numbers while keeping a single solution)
- An react clone (element tree creation, deep comparission, and tree reconcilation)
- Literally tree (had to write an quick and dirty "tree" copy in dart)
- Contributing on the AST of an language
- Pauling diagram (looks cleaner with recursion imo)
- SVG parser
- SVG renderer
- Lots of small utils
I absolutely love recursion, wish i had to use it more.
Could listen to this dude talk for hours
_Excellent_ graphics.
+Matthew Grimshaw thanks >Sean
I could listen to this guy forever!!!
Real world equivalent of Ackermann using recursive techniques is dealing with Bill of materials on complex produced objects.
You never know how far down any branch in the tree will go and you need to traverse the tree to, for example, calculate total cost estimate or perform some engineering action on them all.
Less of a problem by the time the BOM is finalised because you can flatten it and deal with the flat list but I've had to write recursive programs at work to do this sort of thing in our engineering system.
Luv and Peace.
i am an elctrical engineer i i was looking for recursive functions for signal storage I saw your video and I loved it
I remember writing a program to draw a dragon curve (A primitive fractal) on a Sinclair ZX81. Took about 60 lines of basic with every variable having to be an array so it could have different values depending on the depth of the recursion. And it had goto jumping out of one for next loop and into another, quite horrid.
Did the same thing many years later in 4 lines of logo.
I wish I had such teacher. I would have listen to him for hours.
11:32 stackoverflow
Was it robust enough?
What a gem - I must look up more of this wonderful man's work!
I found recursion useful in parsing a tuple in C++, which the compiler inlined.
The circle animation for nested for loops makes them so much more clearer
If you don't have recursion, just build the stack yourself. CPUs aren't magic and don't do anything special when they "call a function". They just put the current state on a stack, jump to the function, let it run, then pop the state from the stack and go along. Easily done in a loop. You just build it on the heap instead of relying on the (usually much more limited, at least in the past) system stack.
amen brother.
I really like this professor. He makes any subject so interesting.
I love when his glasses flash mauve.
I just loved the way explained ... especially the animation to support !
Trees, best way to update trees is via recursion. Ok you can do it using iteration, but recursion is much nicer. (OK I suppose Professor Brailsford covered this by talking about compiler AST's)
For the most robust implementation, what can be done in a loop should be written so. Recursive function calls only work until a few hundred levels of depth, which is extremely easy to exceed. For example, a linked list is a simple tree, and you can agree that iterating it recursively, you'll run out of memory in less than a microsecond. It's actually pretty easy to traverse trees and graphs using simple loops, without any recursion, once you get used to it, and such code can be very readable and maintainable. Might be a challenge for the first time you're doing it, but easy afterwards. All you need is a container where you can push and pop items, and you're only limited by the physical memory, not by the size of the function call stack.
I should have said "theoretically the best way", but in a practical sense you are right. The stack is only limited by so called "soft limits", (In Linux its usually 8192kb, in windowsNT its a measly 1024Kb) I think these are put in place by the operating system to prevent infinite recursion. There is no practical reason why your stack cannot occupy the all of the memory available in the virtual address space. I agree though when handling large data structures, you have to use loops and stack like container data structures.
If you don't know the depth of a tree beforehand how would you possibly search/modify it without recursion?
+Mastikator Loops can iterate over a fixed range or over a generator, that keeps providing new values.
+Giles Bathgate wouldn't the generator then be using recursion?
I'd love to be confident enough in my knowledge to speak as comfortably about a subject as this guy.
Simon Newman yeah, it’s cool when you can 👍
I love professor Brailsford 😇
Back in my college days I found a way to do recursion in FORTRAN, at least with the HP compiler there. I don’t remember how it was, but wasn’t complicated.
I’ve also made a chess playing program using recursion in Pascal, which was very compact. It even had alpha-beta pruning.
Academical interest, there is a theorem that proves that everything done with recursion can be done with loops as well.
Well even if a language doesn't have recursion explicitly built in the programmer can code it themselves anyway. I normally avoided recursion because the vast majority of time for a given problem it would be less efficient than other methods. Sometimes tho it is better to use recursion because not using it could involve the code getting ridiculously complicated.
I have used recursive functions in every one of my major programs. About 1 in 1000 of my functions where recursive in well over 1 million lines of code over 45 years. Obviously recursion is MUCH more important than plain Jane loops.
I am sure if I had been a professor rather than a developer I would have used recursion more.
As someone who is writing an operating system, this video proved to show me that recursion on the stack can eventually pop. So long as you have a heap fallback, everything should run smoothly. I wonder how much static local variables in C could reduce the amount of recursive intensity recursion brings by allocating more stack frames.
My typical example for something requiring recursion is traversing a tree. Or, since I'd mostly explain this to new students, a file system. (Which is a tree, even if they don't know that)
If you can have folders within folders, arbitrarily deep, you have to use recursion.
You don't have to use loops, but it makes it easier to write and read the code.
Mike Meyer: Yes, you are right, of course. I thought of making it more explicit, but I realise I am contradicting myself here.
125m125: Using for loops? Not a chance, recursive is much clearer.
If it's even possible with a loop. I'm pretty sure traversing a tree is impossible to do iteratively.
I've seen many for loops that handle trees in JavaScript. It's the usual way to handle the DOM, which is a tree. Granted, it works because each DOM node effectively carries a pointer to its parent node, but that's also true of file systems.
I guess if there wasn't such a pointer, you'd have to keep pointers to where you've been. But it still could be done.
Documents can contain a lot of nodes, and, even now that recursion limits are removed, JavaScript still can easily run out of memory. It's why I always convert common algorithms to iterative form.
I guess Yndostrui is right that it is impossible with simple counting for-loops. But it is possible with a single while-loop and a stack-like data structure.
When I was in college I was a bit concerned about being called upon to come up with an original recursive solution sometime in the course of my professional career. I finally faced that challenge 15 years later. The requirement was to process a tree structured database and produce an MFC tree UI. I was relieved that I was up to the challenge.
Anyway, my main point refers to the GOTO video emphasis on documentation. I made sure that there was plenty of documentation embedded with that code and warning to be very careful with changes here.
Back in university I tried using FORTRAN exactly one day. I started reading the textbook of FORTRAN 77 (or whatever version) and I wanted to try writing a simple "Hello world" type of program with it. I copied one of the first example programs from the book to a file in university's main computer and I tried compiling it. After a few rounds of correcting my typos I finally got it compiled. Then I tried to run it. ERROR. I gave up any ideas I might have got aboout FORTRAN. I had much better success writing C some months later (and ever since).
Professor Brailsford seems to have a very nice collection of books. As a collector of old computers and ephemera I would love to see what else he has in his shelves.
I think I spot a teletype manual in the top left shelf.
Thank you.
Fortran programmer here. Thank you professor Brailsford for admitting it's great for engineering. You probably already know this, as you called it "original Fortran" or "early Fortran". I'm being pedantic here, but you're using some very antiquated Fortran standards (we have a 2015 standard!).
First, Fortran is not so low-level. We have recursive subroutines (or "functions", for you C devs)! We also have user-defined types, implementing everything you can do with C structures.
Second, you don't need numerically-labelled do-loops anymore. We now have "do ... end do", instead of "do 180 ... 180". You can even label them with a literal string if you're that kind of psychopath. I would love brackets instead, but not even python has bracketed loops.
He's presenting how loop and recursion first appeared in higher level programming language, using the original format and showing its low-level-ness is the sensible way to go. And as you mentioned, he did say it's "original FORTRAN". --- Another Fortran programmer.
OTOH, python has syntactically meaningful white space. That's kinda the same thing as using brackets. At least when compared to using gotos with either labels or line numbers.
Ok, I want you to use fortran, and make a program that calculates '1000!', it has to do it with normal looping, 1*2*3*4*5*6*....999*1000
Once done, inform me of the first few digits and the last few digits of the answer and most importantly, tell me how long it took for the program to calculate it.
When I first came in contact with recursion - back in the 90s in Turbo PASCAL 7 - it scrambled my mind. I just didn't get it. The same was true for pointers when we used them to create linked lists. But when the teacher got us the task to read the linked list recursive, instead of completely blowing up my mind, everything fell into place.
I have to say it took several years since then till I completely understood those concepts.
256 is a recommended minimum for C++11 nested control structures. It's not a hard limit by any means, and is, in the end, implementation-defined. After all, it's easy enough to have a kinda-nested loop with conditionals and goto. Any assembler that has conditional jump has no hard limits on loop nesting at all. Generally speaking, recursion is just a useful abstraction over loops and call stack -- it's entirely possible to code that by hand. Or, depending on your perspective, recursion is fundamental and loops and call stack are implementation detail. So... there isn't all that much difference.
Sudo? Did you mean pseudo?
Likely so. Not a native speaker. Thanks for pointing it out. Edited.
This guy is awesome. If only every professor could explain things as well.
I am quite interested in things like this, very nice to know, thanks for this video, much love, keep it up, brother :)) hearts*..
I rewrote a Btree+ altorithm without recursion. It was difficult, but now I know exactly its limits because I can debug it and measure the stack use, thus it's easier to see which is the worste case. With recursion, algorithms are easier to write but more more complex to be debugged and the stack usaged is more complex to be predicted for the worst case.
Tail recursion is it's own reward! lern you some erlang!
How to test if your compiler removes tail recursion in favor of a loop: let it run a few thousand times and see if you get a stack overflow or out of heap space error XD
I find it fascinating that such a elemental concept was a novelty back then. Btw. you can emulate recursion with loops if you have implemented a stack data structure. Basically that's what the language does when it implements recursive functions - each "instance" of a function has their own stack frame, and they together form an implicit stack.
In general, loops vs. recursion:
- A loop almost always performs better than recursion.
- For really easy problems, it's often easier to write a loop than recursion. In this case, use the loop.
- For most other problems, except the easiest ones, recursion is often much easier to figure out than a loop, but it typically suffers in performance. However, use recursion if it makes the code easier to understand, even at the cost of performance. Often, the performance cost is negligible, but even if it isn't, difficult code often hides bugs and is a nightmare to maintain or modify. And if performance is critical, it is easier to later optimize code that you understand, instead of writing already optimized, but difficult to read code.
Learning from history is really cool, give you pre-context to current day. Love internet hosted videos. Such a boon to learning!