Programming Loops vs Recursion - Computerphile

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

[@smergibblegibberish]

I love the way loops were animated in this video. I've never seen it done that way.

[@Computerphile]

+smergibblegibberish thanks >Sean

[@pagola]

me too

[@MrMrEvin]

Im not even a programmer and that made sense to me

[@nadadada3938]

When they were animated like that, I realized I always seem to look at loops like that.

[@MechaOrangeStudios]

That's the most intuitive way to explain it and actually shows why they're called loops

[@BeCurieUs]

The depth and breadth of Professor Brailsford's computer science, logical and philosophy pedagogical ability is really astounding

[@Puzomor]

Christopher Willis I resent a video of him explaining why HTML is better than C. Apples and oranges 101...

[@BeCurieUs]

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

[@AySz88]

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).

[@aaro1268]

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.

[@jtveg]

Christopher Willis This professor's knowledge of computer programming history is just awesome to listen to.

[@chrismcgee2211]

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.

[@pagola]

englishmen

[@RecklezzMusic]

I love the topics this guy presents. =D

[@KnakuanaRka]

Yeah, I loved that line.

[@AlanCanon2222]

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).

[@ryanaiden]

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…

[@daniellewilson8527]

Oh this is great, A first hand experience with it 😂

[@kkakroo]

To understand recursion, you must first understand recursion..!

[@onjofilms]

Or watch the movie Inception.

[@giwatech3330]

You got exit condition missing. Stack busted.

[@Cynthia_Cantrell]

I'm still working on understanding cursion.

[@Deschutron]

I can understand it if part of it is simple and I understand the rest of it.

[@MrTega1975]

or place a mirror in front of another

[@Anonymous-nj2ow]

when an OG like this talks about recursion, you watch and listen

[@esond]

This video had some excellent and illustrative animations. The "nested loop" animation was super cool. Cheers to the animator!

[@josemvacar]

11:27 - "...and if you don't get things sorted out correctly then \*prff\*..." - I completely agree.

[@javierbg1995]

Was that a fart?

[@Qwertype315]

no it was a fact

[@ExtremalMetal]

no it was Fartran

[@anteconfig5391]

Lol. I figured I wasn't the only one who noticed.

[@villipvp]

I had to rewind it 3 times to check haha

[@TheCALMInstitute]

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!

[@daniellewilson8527]

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.

[@AlbatrossDude]

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!

[@frankindude]

I thoroughly enjoy this professor's talks. He has an amazing grasp on both the subject matter and ability to explain things.

[@valuedhumanoid6574]

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...

[@corsicanbread7276]

Impressive!! Especially in such a low level language as fortran

[@ishansinha1336]

what do you do now a days ?

[@valuedhumanoid6574]

@@ishansinha1336 A mouse and Windows 10. That's it. No computer programming for me

[@MrCOPYPASTE]

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.

[@neonz2712]

I loved the demonstration of a nested for-loop. Beautiful imagery.

[@doresearchstopwhining]

This guy should narrate nature shows. He's like the David Attenborough of mathematics.

[@brunodosreis]

Yes, but there’s already enough about nature. We need more mathematics.

[@carbrickscity]

More like computer science. This is computerphile anyways. He is not an official mathematician.

[@davecrupel2817]

@@brunodosreis Agreed.

[@LukiaTheTrue]

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.

[@soraaoixxthebluesky]

Those who animated the video deserve a raise.

[@nO_d3N1AL]

It's always interesting to see how things evolved in computer science. Also glad you asked about a real-world "Ackermann" equivalent

[@xplinux22]

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.

[@garvit8015]

11:32 That fart was perfectly timed, Professor Brailsford!

[@carlb3715]

This is truly fascinating to listen to. I would love to attend his lectures, even casually.

[@MrVasteel]

11:28 - "If you don't get things sorted out correctly then..." *shrugs and farts* lol

[@Barnardrab]

I can't believe I missed that. 😂

[@hamzaelouakili2438]

That was his voice, he oozed the air out of his windpipe, like when you are in a doubtful situation.

[@cortalectin]

You grow up.

[@coconutbliss1444]

it was not a fart, it was a mouth thing.

[@jonathonhoggarth6473]

Pete Allen hahaha made my day

[@bariswheel]

I love this historical narrative of concepts and algorithms, what a fantastic idea to capture these in conversation and put them on KZbin, thanks for sharing.

[@gggfx4144]

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

[@BeCurieUs]

Also, binary search tree's are often a real world example of a good place to do recursion

[@ChrisLeeW00]

I couldn’t imagine how painful a google search would be without recursion and BST structure

[@garryiglesias4074]

Parsing (as mentioned) is PURE tree walking (nested, many times)... Parsing is one of the heaven for recursion.

[@ThisWorldOfEpicness]

Chris LeeWoo That’s... Not how google works

[@tetrabromobisphenol]

The function to follow or create the tree need not be recursive.

[@Dante3085]

Yes, you could use a stack to cache the alternate routes and do them later.

[@Rsharlan3]

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.

[@atlaslife3800]

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.

[@sige333]

It's always a great pleasure to listen to Professor Brailsford!

[@koushikrakib7605]

I love when the Professor talks! everything seems understandable :)

[@DsiakMondala]

Those circles are the most perfect representation of a loop I ever seen.

[@21ruevictorhugo]

Hmmm. That’s just how they always looked in my head. I miss programming.

[@josephfatur1747]

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.

[@dannygjk]

Java should be illegal.

[@John-Smith-999]

@Rooflesoft Games why? It makes perfect sense and is done all the time

[@policy308]

Slow compared to what? Java isn't slow.

[@John-Smith-999]

@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

[@John-Smith-999]

@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.

[@swiftfox3461]

I love Professor Brailsford, he's such a captivating educator and speaker.

[@counterculturecocks]

I absolutely loved the visualizations. Thank you for doing these videos.

[@nonomnismoriar9601]

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

[@AtomkeySinclair]

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.

[@NeilRoy]

Love Professor Brailsford's videos. Always very interesting and very well explained. Thanks.

[@leunsafeleunsafe9316]

The animations that exemplify the loop was very impressive and self explanatory.

[@StephenFarthing]

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!

[@Computerphile]

+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

[@gggfx4144]

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

[@thenerdyouknowabout]

"It no more gives you values of Ackermann's function than flies you to the moon" - Amazing quote.

[@zimbit]

What a gem - I must look up more of this wonderful man's work!

[@teh_jibbler]

This dude is a treasure-trove of knowledge. Keep making these videos, please.

[@igNights77]

Excellent animations in this video, as always.

[@Computerphile]

+igNights77 thanks, I appreciate that! >Sean

[@mayukhdifferent]

11:32 stackoverflow

[@jacobdecoursey5829]

Was it robust enough?

[@beck64]

That explanation of Fortran recursive calls trampling existing data and producing garbage was beautifully illustrated.

[@finkergamer8557]

It is fantastic feeling to finally understand something. As it is with this channel after years of my studying.

[@simonbode7356]

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..

[@Hostile_Design]

I rarely understand anything this man is saying, but I watch anything with him anyway because he is so damn charming.

[@kimiaazizollahi18]

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.

[@0xdead982]

true, but damn ۱۷ سال سابقه البته الان ۱۸ می‌شه so i got curious, i searched your name wish i could see your github page but there was none :(

[@vinogradovawinery]

This is one of the top five most informative and interesting videos I have seen on youtube.

[@AmokBR]

I felt warm inside when he mentioned do loops in fortran. I programmed in it fir 4 years.

[@IceMetalPunk]

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.

[@rikvdmark]

Nice visualizations! Beautiful to watch and very informative. Thanks!

[@ozzyfromspace]

Glad I found this video! Excellent discussion, Professor Brailsford! :) Cheers!

[@goummoboris5194]

I would Love to attend his lectures, his is just some sort of Computer Passionate.

[@aarondavis5386]

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.

[@MichaelSmith-fg8xh]

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.

[@dale116dot7]

@@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.

[@RagingGeekazoid]

@@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]

@@RagingGeekazoid You can explore trees without recursion.

[@RagingGeekazoid]

@@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.

[@trevorvillwock4846]

Could listen to this dude talk for hours

[@ct92404]

I really like this professor. He makes any subject so interesting.

[@TheJaguar1983]

I found recursion useful in parsing a tuple in C++, which the compiler inlined.

[@SniperNinja115]

I am quite interested in things like this, very nice to know, thanks for this video, much love, keep it up, brother :)) hearts*..

[@seanhall2771]

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.

[@loam]

Always love to hear from that man!

[@donaldasayers]

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.

[@bumpty9830]

_Excellent_ graphics.

[@Computerphile]

+Matthew Grimshaw thanks >Sean

[@AnJo888]

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.

[@poojabannikuppemahesha7990]

I just loved the way explained ... especially the animation to support !

[@therugburnz]

I love when his glasses flash mauve.

[@nlgatewood]

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

[@nealpatel7696]

The circle animation for nested for loops makes them so much more clearer

[@augustuscrocker9328]

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 !

[@kevinbee4617]

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])

[@lipslide101]

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.

[@pedrokalil4410]

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.

[@lawrencetate145]

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.

[@dsuess]

Phrase of the day, 8:30 "Tramples in its muddy gumboots" I love this overall explanation by Prof. Brailsford

[@PeGaiarsa]

The moment he said "recursion" and "compilers" in the same phrase, I had chills going up and down my spine.

[@trailblazingfive]

I love professor Brailsford 😇

[@Maya_s1999]

I could listen to this guy forever!!!

[@grayswandir47]

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.

[@ianedmonds9191]

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.

[@DustinRodriguez1_0]

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.

[@garretgang8349]

amen brother.

[@Ownig3]

His voice's so nice to hear. thank Teacher!

[@Maithil_NutanJha]

Great way of explanation sir 👍

[@OldieBugger]

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).

[@GilesBathgate]

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)

[@tamasdemjen4242]

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.

[@GilesBathgate]

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.

[@Mastikator]

If you don't know the depth of a tree beforehand how would you possibly search/modify it without recursion?

[@GilesBathgate]

+Mastikator Loops can iterate over a fixed range or over a generator, that keeps providing new values.

[@Mastikator]

+Giles Bathgate wouldn't the generator then be using recursion?

[@Playncooler]

The professor is really the star of this channel.

[@mkteku]

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.

[@justgame5508]

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

[@garretgang8349]

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

[@mlhbro]

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.

[@0MVR_0]

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.

[@shereefmohammed6596]

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.

[@jmendoza7507]

macaroni italic ¿

[@clarkd1955]

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.

[@TimmyMoza]

Very cool. Learn something new every day. Cant wait for my next happy hour and bring up the points in this subject....

[@raf74hawk12]

I could listen to him talk about this stuff for days

[@Glottris]

Tail recursion is it's own reward! lern you some erlang!

[@turun_ambartanen]

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

[@dand5990]

Watching loops in 4k. Future is now.

[@GiordieTN]

I barely understand this but just seeing a guy so passionate about his stuff makes me feel good :)

[@seggremalac]

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.

[@JohmathanBSwift]

11:30 Mmm, must have complied itself into a fart.

[@miguelmondardo2741]

2:32 He looks like those dragonball characters that use a special glass to detect a enemy's power lol

[@dragonbasky8281]

His understanding of for loop is the BEST!!!!! explanation EVER!!!!!!!

[@goosemontv]

I could listen to this gentleman talk about computer science for hours on end

[@Madcowe]

11:31 did... did he just fart? xD

[@ZipplyZane]

I don't get the depth limit of for loops, as long as you have enough variables. You can implement a FOR loop with just conditional jumps and incrementation. As long as you reset your iterators before the loop, this should scale to any depth. And, in practice, it seems that I can always do more iteratively than recursively. I'll hit recursion limits with a recursive function, but I never hit any limits when I convert it into an iterative function. Can you explain this?

[@phiefer3]

The depth limit for loops would be built into the language (or more accurately the compiler), as in it's a limit of the compiler to keep track of that many nests, or the limit may be put in place for memory/resource purposes. Think of it similar to how he described recursion in early Fortran, a function could call itself but the language/compiler wasn't really designed to create a separate stack for each call. This wasn't the result of some fundamental limitation of recursion, only a limit of how the language/compiler was designed to handle it. And keep in mind that the depth limit for loops is a limit of how many nests you can do, and not at all related to the number of iterations.

[@ZipplyZane]

Okay, so it's a limit of the compiler. That makes sense. But the video presents the nesting limit in iteration as a reason why proper recursion (with stacks) needs to be added. That doesn't make sense to me. Adding recursion would seem to make that particular issue worse, because proper recursion takes up more memory. It would make more sense to remove any artificial limits on iteration. Just let it fail when you run out of memory for the iterator and pointer. That's not to say that adding recursion doesn't make any sense, as it can help with a lot of things. But it does not seem to be a solution to that particular problem.

[@chrisfredrickson1085]

"It would make more sense to remove any artificial limits on iteration. Just let it fail when you run out of memory for the iterator and pointer." That's kind of what recursion is. Recursion is not limited the same way loops are; stack overflows happen when you run out of memory for the recursion's bookkeeping.

[@RWoody1995]

But wont recursion run out of memory earlier than iteration? ZipplyZane wasn't saying its different to recursion if you removed the nesting limit but that it would be more efficient at run time for things that aren't inherently recursive but require a huge amount of loop nesting.

[@chrisfredrickson1085]

That depends on the language and the compiler (and its settings). A lot of things can be written tail-recursively, which means the recursion can use a constant amount of memory. (It's up to the compiler to be smart enough to recognize that, and for the optimization settings to kick in.) But for anything that can't be written tail-recursively, an iterative approach would also use a non-constant amount of memory, so it's just a question of which memory usage increases faster. I think that's really up to the compiler.

[@klankab]

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.

[@SimpleExcelVBA]

I wish I had such teacher. I would have listen to him for hours.