Programming Loops vs Recursion - Computerphile
ฝัง
- เผยแพร่เมื่อ 27 พ.ค. 2024
- Programming loops are great, but there's a point where they aren't enough. Professor Brailsford explains.
EXTRA BITS: • EXTRA BITS: Loops, Ack...
The Most Difficult Program to Compute?: • The Most Difficult Pro...
What on Earth is Recursion?: • What on Earth is Recur...
Reverse Polish Notation & the Stack: • Reverse Polish Notatio...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
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
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 😂
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
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).
This video had some excellent and illustrative animations. The "nested loop" animation was super cool. Cheers to the animator!
when an OG like this talks about recursion, you watch and listen
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
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
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!
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.
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.
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.
I thoroughly enjoy this professor's talks. He has an amazing grasp on both the subject matter and ability to explain things.
11:32 That fart was perfectly timed, Professor Brailsford!
I loved the demonstration of a nested for-loop. Beautiful imagery.
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.
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.
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
Those who animated the video deserve a raise.
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.
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.
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
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.
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.
It's always a great pleasure to listen to Professor Brailsford!
This is truly fascinating to listen to. I would love to attend his lectures, even casually.
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.
It's always interesting to see how things evolved in computer science. Also glad you asked about a real-world "Ackermann" equivalent
What a gem - I must look up more of this wonderful man's work!
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 love when the Professor talks! everything seems understandable :)
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
It is fantastic feeling to finally understand something. As it is with this channel after years of my studying.
That explanation of Fortran recursive calls trampling existing data and producing garbage was beautifully illustrated.
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
11:32 stackoverflow
Was it robust enough?
I love Professor Brailsford, he's such a captivating educator and speaker.
The animations that exemplify the loop was very impressive and self explanatory.
Excellent animations in this video, as always.
+igNights77 thanks, I appreciate that! >Sean
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.
@@RagingGeekazoid 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.
This dude is a treasure-trove of knowledge. Keep making these videos, please.
I absolutely loved the visualizations. Thank you for doing these videos.
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])
"It no more gives you values of Ackermann's function than flies you to the moon" - Amazing quote.
Love Professor Brailsford's videos. Always very interesting and very well explained. Thanks.
I really like this professor. He makes any subject so interesting.
I rarely understand anything this man is saying, but I watch anything with him anyway because he is so damn charming.
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.
I just loved the way explained ... especially the animation to support !
Could listen to this dude talk for hours
I would Love to attend his lectures, his is just some sort of Computer Passionate.
_Excellent_ graphics.
+Matthew Grimshaw thanks >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.
Nice visualizations! Beautiful to watch and very informative. Thanks!
I felt warm inside when he mentioned do loops in fortran. I programmed in it fir 4 years.
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..
Glad I found this video! Excellent discussion, Professor Brailsford! :) Cheers!
I could listen to this guy forever!!!
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
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.
The circle animation for nested for loops makes them so much more clearer
I could listen to this gentleman talk about computer science for hours on end
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.
The moment he said "recursion" and "compilers" in the same phrase, I had chills going up and down my spine.
Phrase of the day, 8:30 "Tramples in its muddy gumboots"
I love this overall explanation by Prof. Brailsford
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.
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 found recursion useful in parsing a tuple in C++, which the compiler inlined.
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.
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 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 love when his glasses flash mauve.
His voice's so nice to hear. thank Teacher!
Always love to hear from that man!
I am quite interested in things like this, very nice to know, thanks for this video, much love, keep it up, brother :)) hearts*..
I love professor Brailsford 😇
Very cool. Learn something new every day. Cant wait for my next happy hour and bring up the points in this subject....
I wish I had such teacher. I would have listen to him for hours.
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?
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).
I could listen to him talk about this stuff for days
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.
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.
I don't get why recursion is made out to be an extremely difficult thing, it's not. You just have to think for a minute or two and plan out your code instead of typing like a maniac and hoping for the best
I have found that incursion is actually the real beast. Because an incursive version of a recusive problem is very complex, whereas a recursive solution to an incursive problem is simplicity;
I have found that the only way to have simple coding (coding that requires no planning) is to limit your code to a single function that might have a single loop in that, after that without planning coding becomes difficult
JustGame:
Recursion is difficult for a lot of people because it's taught really poorly in almost every single case.
What they'll usually do is start by reviewing mathematical induction, so they can turn around and say, "Okay, look! Recursion is just like that! Now you understand recursion!" Which doesn't help at all. It is not necessary or pedagogically appropriate to bring mathematical domain knowledge into that learning process. It gives the impression that, if the student doesn't understand some complicated math concept, they can't understand recursion, which is false. Actually, I'd far more readily do the reverse, and use recursion to teach mathematical induction.
In any case, after that they usually trot out some canned, but incredibly poor example, like factorial or fibonacci. These are fine. They "work" as examples. But they tend not to give the student much insight about why recursion works, because the concept is not introduced as an outgrowth of the self-referentiality of the underlying data. In the case of factorial and fibonacci, the reason why recursion is natural is because the natural numbers are inherently self-referential. A natural number can either be 0, or it can be (1 + [a natural number]). In other words, "natural number" occurs within its own definition, and this is what implies a recursive processing technique. Or if you have essentially a linked list, the definition is that the linked list is either empty, or it is a list of ([some element], [a linked list]). The self-referentiality of that definition implies recursion. And both examples also contain their base cases (0 for natural numbers, and empty for the list). If you teach recursion starting with data definitions, it's easy for students to see where the base case and the recursive step come from, and why they make sense. Data defined recursively makes sense to process recursively.
Some other problems commonly encountered in the teaching of recursion is that the teacher will instruct the student to try tracing the recursive calls. While this can be mildly illuminating in simple cases, it leads to the misconception that programmers come up with recursive solutions by understanding how the individual calls unravel. In fact, this is only going to confuse you, because it quickly turns into Inception-level brainfuckery, and also gives you exactly zero insights as to how to design a recursive solution. The main trick of recursion is that you are supposed to *assume the recursive call returns the advertised result*. You take it for granted. It's how you form the combination of that recursive result--which operates on, say, the rest of a list--with the first element of said list, that determines whether your function will work correctly or not. Follow the recursion one time, for a simple case, just to get the curiosity out of your system. Never do it again, after that. It does not lead to any important insights, and nobody who writes recursive code designs their solutions by following the recursion.
Yes, the faith in that assumption [the precision of the recursive code deeper beyond one iteration] is the hardest thing for programmers to develop. Linearly defined script, being easy to follow, allows for absolute knowledge in both logical operation and resultant computation. Recursion permits understanding of only the logical operation, the structure of how a result will arrive, not often the resultant itself. Taking it through one computational exercise is great advice and is incidentally something I practice outside of coding. Once a pattern has been recognized or established, assume its potential reproduction. Any further inquiry into its nature, structure, organization, etc is one of technical engineering (which has its place), not scientific comprehension.
macaroni italic
Your comment is the most inciteful and helpful comment I've seen on youtube. You really helped me umderstand why I'm having difficulty with recursion AND validated my "faith that the function delivers what it is designed for deeper than the 1st level" approach that I naturally developed as a workaround.
macaroni italic ¿
I barely understand this but just seeing a guy so passionate about his stuff makes me feel good :)
His understanding of for loop is the BEST!!!!! explanation EVER!!!!!!!
11:30 Mmm, must have complied itself into a fart.
11:31 did... did he just fart? xD
The professor is really the star of this channel.
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 !
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.
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 love him!
It was a very nice video thank you!
The professor reminds me one of my programming teacher. Actually the only one who made impact on me ever. He was an older guy with fantastic knowledge and also was a very nice person.
Great way of explanation sir 👍
Watching loops in 4k. Future is now.
10:58 "booooooooooooooooooooooooooooooooiiiiiiiiiiiiiiiiiiiiiii"
Best thing ever
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.)
Huge respect for your knowledge sir...