Programming Throwdown - 163: Recursion

Episode Date: August 14, 2023

Episode 163 - RecursionIntro topic: Electric CarsNews/Links:Snake Game in 101 Bytes in a QR Codehttps://www.reddit.com/r/programming/comments/15ab4ct/my_qr_code_snake_game_is_now_only_101_bytes/Superconductor Rumors aboundhttps://arstechnica.com/science/2023/08/whats-going-on-with-the-reports-of-a-room-temperature-superconductor/OpenWormhttps://github.com/openworm/OpenWormCreator of vim passes awayhttps://news.itsfoss.com/vim-creator-passed-away/Book of the ShowPatrick:Little Book of Common Sense Investing by Jack Bogle https://amzn.to/43YqANRJason: Mistborn Saga: https://amzn.to/3DJkUN8Patreon Plug https://www.patreon.com/programmingthrowdown?ty=hTool of the ShowJason:reMarkable https://remarkable.com/Patrick: Stellarium (iOS and Android)Topic: RecursionWhat is itDivide-And-ConquerFibonacci numbersHow to (not) teach recursionPractical ApplicationsGraph operationsTree retrieval, balancingGraph SearchSpatial partitioningPitfallsStack sizeHow to solve problems with recursion(1) Consider the base cases(2) Build the recursive step(3) Look for ways the recursion will not terminate and fix(4) (rest are optional) Remove global contexts(5) Add memoization(6) Build solutions incrementally ★ Support this podcast on Patreon ★

programming throwdown episode 163 recursion take it away patrick i was trying to come up with a good intro topic for the show and and I decided to harass Jason. So I apologize. No, no, I'm just teasing. I want to talk about electric cars. So electric cars have always been about to be a thing. I actually am not strongly opinionated about whether they will be this sort of exponential adoption thing that I feel like a lot of tech people feel this is like what will happen like it'll just become more and more inconvenient to go to the gas station there

won't be gas stations and then overnight you'll blink and everyone will have electric cars i don't know not going to get into that per se but i have noticed a lot more people uh driving electric cars so jason and i were talking about it briefly but basically so i drive a plug-in hybrid which i actually really really like i drive a honda version called a clarity i don't even think they make it anymore um but what's the plug-in part mean yeah okay plug-in hybrid so that's great so a prius most people know about the prius is just like a hybrid it means that you have a you know electric motor to drive your wheels but you have a gas engine to run effectively as a generator to make the electricity and in something like a prius it just sort of does this all the time but it has batteries

it can short-term kind of store the energy and deliver and i might be mistaken i may have changed over the years about priuses but as a an abstraction this will work so basically it runs the gas engine and it can store um sort of power but every time you turn your car off and turn it back back on you're sort of more or less starting from scratch like it doesn't intend to build up a lot of uh energy so it doesn't have big batteries because batteries are pretty expensive they're also pretty heavy um and so your engine will run from from time to time so there's not really an expected mode of operation where you would go on an entire trip and not use your engine um and so it's sort of more along the spectrum of like even

modern cars when you stop at a stoplight will just turn off the the engine and has like a little bit of i actually don't know how they did it but like you know a little bit of it can kind of start quickly and get you going without you kind of noticing so it's just a more extreme version of that although it predated it um and then it kind of reminds me of the formula one cars like the formula one cars have a battery and uh whenever you hit the brakes it charges the battery and so that builds up and builds up and then when they're ready to pass somebody they turn on the battery and the motor and then that makes them super fast yeah so regenerative braking is this like using the motor that's sort of attached to the the spinning part

of the the wheels to charge up to to basically act as a generator which of course pulling the energy there's you know conservation of energy kind of thing like you know charging the battery makes it harder to turn the motor, which makes you slow down. And so you're recapturing some of that energy, which is a really good idea, which is why it's pretty efficient. So the plug in idea is, like most of the original Priuses, you couldn't like plug them into the wall wouldn't do anything, there wasn't like a large battery to charge up plug in hybrid sort of is that it's just sort of like an electric car where you can plug it in, and you plug it in to charge it up and there's a battery that lasts some amount of miles in my car it's something

i i forget the range i think it's like 30 or 40 miles so most of the commute you know like oh i just go you know up to the grocery store i go to you know the office or whatever just like briefly these things are only you know for me like eight miles. So I can go there and back and I don't have to use the gas engine at all. So I have a very small gas tank. It's only like seven gallons, I think is what it is like very, very tiny. Oh, wow. And hardly ever use it. Like I go months and months and never hard. And when I get home at night, I plug the car in the plug in hybrid. But if I'm going to go on a trip, not to worry about finding a charger. So it's on the spectrum of electric cars versus if you go to like a Rivian or a Tesla or something like that. There is no gas engine.

So I used to have a Nissan Leaf. It was the same thing. No gas engine. Had about 100 miles range. So the range of the battery was further. But if I wanted to go on a road trip, I would have had to, you know, stage charging, you know, stops along the way. And so it's on this sort of spectrum, but my observation is just, you know, I'm actually really excited because I think the diversity in the market, I think, you know,

being able to find abundance of choices, not that there's anything particularly wrong with Tesla, but just having more competitors in the market in general i think is is really awesome and it's exciting to see these electric cars start to come out and start to to kind of like make it easier for people who have them to more likely to find a charger somewhere because people are more incentivized to build chargers still sometimes i'll show up somewhere and like charge and people kind of look at you like oh that thing gets used i thought that was just like a reserve spot that you know has the charger added at the mall like some of the economies around that are a little weird still but uh just

you know it's kind of exciting there's lots of debate about where the energy comes from in the ecological the uh environmental impacts there we go of uh you know making the electric cars versus making gas car trying to get into all that but just as a like convenience and i don't have to go to gas stations there's like less sophisticated moving parts in a fully electric car uh versus you know the kind of hybrid is it's got more because that's you know kind of a lot of the traditional stuff and the electric car stuff um but you know it's kind of nice that in general not having to go to the gas station you just kind of forget how inconvenient it is especially where we happen to live now for whatever reason they just haven't like looked at the census data who knows to like build a gas

station so there's like no gas station on any of our like regular occurring routes so we have to like go visit the gas station to get gas which is horrible going to the gas station so when you say you plug it in it's a plug-in hybrid did you have to get the 220 volt adapter for your house yeah so this is a good question so we don't so we just charge it off of regular thing like i i know we could do it we could pay we price it out we just chose to do regular because our battery is small enough that we can charge it up overnight basically if you have a you know 300 mile range like fully electric vehicle it would take you sort of i don't know i'd have to look probably like 30 hours or something 20 something hours to charge so if you drained it

all the way down and there's no backup right so um that would that would definitely be a call for a quick charge versus for me it's only if i like went somewhere far in the morning and came home having 220 would only be useful to like get it back up so i could go again in the afternoon versus now if i do that i just have to use gas yeah i mean i think this is super exciting um if you go on a long trip with a seven gallon tank are you refilling very very often or how does work? So the car basically reverts to being a normal hybrid. So it still gets, I don't know, whatever. The mile per gallon stuff is a little weird. Anyway, it goes to whatever the normal mile per gallon you would get on a hybrid is.

So it's still very efficient. It'll still shut off the engine. It'll still, you know, do regenerative braking like you were saying. So I think I get something like 40, 50, 60 miles per gallon. Oh, that's great. So it's still very efficient. So that's a nice fallback not pitching poigan hybrids they all have their thoughts just kind of like you heard it here first no no and i think like i said i think honda stopped making my car so they don't even make it anymore oh no and where i live they never sold the car in this state so um actually

it's like very unique i've only ever seen one other of this car in the entire you know time i've been living here because we moved from california so in california they sold a lot of them here they don't so actually i'm like the only one with that car yeah i think in california um you can't have a combustion engine car after some time like yeah pretty soon they're going to change it yeah yeah that uh it's really interesting yeah i have a friend another friend who has a fully electric car i can't remember what it is not a tesla but it's something else but it is fully electric and um um you know he was he i think it is a honda uh does honda make a fully electric as well or no uh is that the ionique or something maybe yes it could be but oh no that's he would he was saying

that uh you know the nice thing is you know it's just as you said you never have to think about the gas station and uh you know plugging it in when you get home is is so much more convenient than the gas station plus you know the gas station causes some like latent anxiety it's like you watch it's like a half full a fourth full an eighth full and then you go in but that whole time you know you have to kind of keep it in your mind um so yeah i think uh i have a feeling like the next car we buy once one of our cars finally kicks the bucket is gonna have some type of battery in it well your car has a battery in it now to be fair okay yes i know what you're saying some type of battery powered engine propulsion electric propulsion of some sort yeah i think uh

um i think the hybrid is you know has a lot of nice advantages so i have a feeling the hybrid is probably what about the gasoline like if the gasoline sits in the car because you're not using the engine is that bad do you have to every now and then just go on the highway or something? Yeah. I mean, if you probably like over the course of very, very long time, but I do notice I,

I'm not a car nerd as anyone who is probably already is, is owning and passporting, but the, the, the gas tank is like, I think it's pressurized or something to help avoid that. So like when you push the gas tank release button, it actually takes like a good five seconds before it like makes kind of a special noise and then opens up so i think they do something to keep it like a more sealed thing to

prevent which makes sense then yeah you know a lot of the issues you might otherwise have um you know so don't pop up but i've never had an issue with it and we do routinely run it you know every so often um so we do go fill it up every couple of months it's not like we go two years and never you know never use it so very cool all right interesting we'll have to see well actually we'll end it with a prediction like uh at the end of this year how many what percent of cars will be either hybrid or electric actually i don't know the percent right now here let me look at this this sounds this sounds sketchy no i'm just gonna say i think it's like you i think the prediction is like what will and there's no way to like get a metric for it it's just like what percentage of people

will seriously consider uh like let's say sort of on the spectrum a plug-in hybrid to electric like something that can drive you know some tens of miles without using gas uh is that going to be you know a third of people a half of people i think some people like you're going to buy a pickup truck because you work construction you're not probably going to consider very strongly a fully electric car maybe that'd be great but so i like in the next five years what percentage of car purchase car purchasers will consider like a fully electric vehicle wow this is nuts i don't know if this includes hybrids but it says this is april 3rd of this year electric vehicles account for less than one percent of vehicles sold in the u.s

i feel like that maybe you know it's just perception bias but man it feels like that that number is a little low um all right anyways on so yeah i guess now that i've seen such a shockingly low number it's hard for me to have a prediction so we'll just table that you want to just take one percent yeah yeah my prediction is two percent oh that's pretty good that's doubling more than doubling that's actually how we do math on programming throwdown all right time for news you have the first news go for it yeah i do so i actually have a great article for this which is like some running thing that i was observing i think it's kind of the same

person or people uh we've talked about code golf in the past um and this interesting spiral this person was posting a sort of ever declining number of bites that they've managed to make the game of snake you know where you like turn left right up down like eat the little pixel i guess it's supposed to be a fruit a snake don't eat fruit but you know like the snake going around and eating and growing slightly longer until you you know crash into yourself um so someone has been trying to get that uh assembly version of that lower and lower and lower in number of bytes they were at the one i have here linked in the show notes they made it to 101 bytes pushing for that you know getting below triple digit number of bytes to encode the snake game but they've been putting it in a qr code and boy did this get

people very divisive about this so uh really yeah so i i am aware of a lot of security kind of concerns but i'm not overly uh i want to say paranoid that adds a negative stigma to it but i am not overly uh cautious about maybe stuff i do i probably choose convenience more than i ought to i'll say yeah same here um but people were saying oh my gosh why would you try to tell people to like take a picture of a untrusted unauthenticated like qr code especially one that you intend to run like who knows what exploit in it and then just like people coming out now to be clear i don't know what percentage of computer professionals would be represented by the noisy people in the threads but basically like how it is a terrible idea to ever take a

picture of a qr code because it could just be like an exploit waiting to happen right like could take you to a payload it could take you to whatever like you're asking you're basically clicking a link and everybody would say oh don't click a link emailed to you but most people would say oh you know qr code what's the worst that can happen now i don't know how many vectors or how many proven sort of like problems have come through people randomly snapping qr codes like out in the wild but it is a concern but i thought this is sort of one of those like unintended rat holes or whatever or like you think you're going to read about someone like you know clever ways or people collaborating on other you know optimizations they could do to get their

size lower and lower or just being happy or oh how cool this is or references to demo scene you know 4k demos or whatever and those those things were there. But then this whole other like brigade of like, QR codes are the worst. It was Yeah, I've seen I've seen some video where somebody basically showed how to exploit this where they were at a restaurant and they stuck a sticker on top of the QR code for the menu, then like sent them to their own site but uh but yeah i mean i i mean what you're hint what you're pointing at is interesting it's like the serendipity of the internet where um you know i had i mean you don't have any social media accounts patrick so i'll have to lecture you i have to lecture me about it please i i i had a post on linkedin basically this is years ago but i was just really excited that I got promoted.

And I was based on my post. The gist of my post was, you know, I never thought that I would really make it this far. I was really happy and, you know, real thankful. And I think like, you know, like some professors from like a long time ago and stuff, right? And it was, it felt really good to make that post. And that post went viral and got tens of thousands of likes on linkedin and then uh basically there was a whole ton of comments about how my university is like a crap university and and uh i you know it was the thing where like uh i wasn't mentally equipped to like to like uh you know moderate something like that so i basically just left it and uh it turns out linkedin is really good at moderation because i went back

months later and all those comments were gone i don't know how that happened it wasn't me i didn't delete interesting yeah so so there's something some kind of uh moderation going on there but um but same kind of thing where it's like yeah i made this post just to talk about you know just celebrate something and it turned into like this whole like back and forth about like where i went to college and uh you know that's just the internet i mean it's it makes it like kind of scary to say anything oh dear yeah i don't know yeah i'm probably doing the right thing youtube videos and i see the comments and i'm just like oh i don't know i could never be a youtube creator i would just

have all my comments turned off uh just yeah about the littlest things there's no like sense of collaboration or like yuki said you know people just move on like why do you need to take pot shots at someone's university so yeah i mean i i think uh um we had comments initially on the blog and uh there's a lot of spam and and there was like some divisiveness and so we just decided to turn it off and yeah comments i mean that's a whole separate rat hole but like whether you should have comments or not i mean someone should write like a dissertation on that yeah i there's some i'm not much into the like uh publicize your podcast i was listening to a podcast the other day and the podcasters

on the podcast were talking about another podcast where they were saying the person's thesis is sort of like you want to be really controversial because like the stuff like you're saying you should have actually leaned into it and like doubled down on it and like gotten people riled up because then people will make other posts that link to your post which will make your post even even more important and like basically you should be like controversially optimizing so even if you don't really believe it you should like make a follow-up post saying where i won't say because you didn't say it the name of your university is like the best university because now you know like the yeah right you

have been given a pearl you have been given a surprise treasure which you now know that your university is apparently divisive therefore you should double down on it and start more controversy and this will like propel you to fame and theoretically fortune or success or whatever these people are optimizing for yeah they call this the attention economy right i mean i was listening to something about um i listened to this board game creators podcast because i think people who make board games for a living are just fascinating um you know and uh they were talking about how to do well on kickstarter and basically a big part of it is already having an audience so so i mean you know one sort of really odd way to get there is to start a bunch of controversy, uh, build up a lot of followers

and then bring them all over to Kickstarter to buy your stuff. Oh, we should. Okay. I don't want to get under the Kickstarter. Yeah. That could take forever. All right. Yeah. All right. My, my, my news is superconductor rumors abound. So room temperature, superconductors. So, um, I'm sure you've heard about this,

Patrick. Uh, there's this thing, I think it's LK 99 or 77 or something. Okay. 99. It's, it's,

uh, some kind of, and you, when I read the instructions of how to make it, it didn't look that weird. I was kind of expecting the instructions to be like, you know, like build a nuclear bunker, you know, hit chemicals with nuclear bombs or like something crazy like you'd see from CERN or something. But no, it's actually like here, take these materials, do this stuff. And it seemed like, yeah, like relatively straightforward um and so uh they're claiming that you'd have a room

temperature superconductor which you know i think if true like opens up a ton of different possibilities i mean just one and i'm sure patrick you have even better ones but just off top my head you know think about how much power is wasted in getting electricity from the power plant to your house right i don't know the number but it's got to be very high amount of power is wasted and you know if you had room temperature superconductors you could theoretically bring that to zero or at least get it a lot closer to zero um and that's just one of you know people are saying you could have gpus that don't get hot and stuff that i'm not totally sure how that would work. But there's definitely huge application for it.

And now everyone's rushing to see. Oh, and then there was all this controversy around, I guess, the way they announced it. They didn't go through the typical channels. And so, you know, people are not sure whether it's real or not and uh uh it's just kind of a crazy situation right now i oh man uh like this is similar to what we were just talking about opening sort of pandora's box uh which of the random threads should we pretend to be experts on so the amount of like people coming out of the woodwork claiming to know things about super conductors or like what their implications are or like whatever on on sort of i'll guess we call it

x now about like right on x on x uh twitter uh the the social media network everyone's on x we have a serious uh epidemic oh no uh but yeah so so i i mean like a couple of things just to like like my my sort of like thoughts to your thoughts we have heard a lot of the same stuff um a lot of weirdness around like how this was announced a lot of debate that i've seen which is kind of interesting around like should we go through the normal peer review process or is this actually like better this distributed stuff and people sort of countering? Well, this is a big waste, because if this truly is a fake, or like a dead end, then like all of this, like random people stopping what they're doing startups putting money

into this, and like this race to all become the first to market or whatever, is like a waste of resources on a global level, it's much better to have like one or two very focused people sort of proving it out. Other folks saying, well, well no that's the way you just end up with patents and then it like is protected very interesting discourse i'm not an academic person so i have no i have no uh pony in that race so moving on to the next one but like you know like your your sort of claims like oh imagine like wasted power lines well so just the whole thing of like economics like even if you took it to zero the thing still has to be as cheap as copper wire and even then it has to be a good point so even like even if it was a room temperature or even high you know above far above room

temperature it might not be very ductile it may not be able to be put into wires right easily or economically and then things like you were saying people were talking about oh batteries that never run out and your phone and like gpus that don't get hot and then this descends into which which i was telling people land hours principle and reversible computing which is this idea like if you destroy we we have referenced this before but if you like make a computation like an and gate is one and zero zero and zero zero and one all have the same output of zero so information is lost you had two bits of information now you have one and there is a theorem sort of saying that losing that bit of information has a minimal threshold of like wasted energy because of the lost bit of information which says even if you had superconductors even if you had new

silicon whatever gpus would still get hot maybe not as hot maybe you don't need a fan but they're not going to be it's not like a you know zero end game there is still waste energy your iphone your android phone in your pocket still will consume energy and so there's like a lot of this like you're sort of saying oh we'll just you know put put electrons into the superconductor in a big loop and then we'll have you know basically better batteries so folks are pointing out actually superconductors have like this quenching property which is if you if the magnetic flux again not this is not my background basically exceeds some amount basically put too much electron circling around they build a magnetic field the magnetic field actually sort of quenches the

superconducting ability the thing that makes the superconducting above a certain magnetic threshold like causes it to fail and this is a big concern actually in mri machines the large hadron collider had a quench event that apparently like the magnetic flux and one of the big magnet coils that are superconducting that they have that they chill to very low temperatures today had like a over too high of magnetism and it basically destroyed the superconductor and caused like a large portion of the hadron collider to need to be repaired so there's like all these like second order phenomena so people just hear something akin to like perpetual motion or free energy and get like

whoa it's like well hang on it is a huge market it is it is going to open up applications we don't know of today but it's not like every bit of history is like rewritten because of you know the magic material but still very interesting i watch it every day i log on to see like has someone been able to there's a lot of weirdness and how it gets made and no one really knows how to do it and uh so is it true is it like meaningful and you know can we actually figure out a way to produce it may be a decade before like even the first practical applications come out even if it turns out to be the sort of like holy grail everyone was seeking yeah here's what i think we need to do patrick i think you and i need to start a petition

saying that for the next six months we need to have a moratorium on uh on superconductors and only we can work on it for the next six months then we need to petition that one i didn't know where you were going we need we do superconductor safety is like a primary government license that's right yeah and everyone except us should be banned from uh doing work on superconductors are you gonna at least tell people what the joke is there yes that's that's a reference to the uh six month moratorium on ai that was proposed. I think even Elon Musk signed it. A whole bunch of people who would definitely not stop for six months signed it. But they want you to stop for the next six months.

All right, on that note, Patrick, you want to talk about OpenWorm. What is OpenWorm? Okay, now on to something completely different, but I also don't know about. But I found this is fascinating. So I've seen this for a few years. It came up again recently. They made some progress. So open worm is a project to attempt to create,

I think it's, I don't even know what the C stands for, C. elegans, some kind of like little flatworm that is composed of a few thousand cells. And they want to make a simulation of the worm now many people have made like simulators of worms before but they normally kind of go top down so they sort of start with the behaviors and then they make like a simulator or model that like does those behaviors right i mean we all play video games is basically how video games work like when you have a video game you know enemy that you're chasing around a level

they are not simulating the cells of the organism. They're like taking the behavior and then like applying behavior to a sprite, right? It's kind of more top down, but here they're actually trying to go bottom up. So because this elegance, I don't even know if I'm saying that right.

Worm is so, so simple. They have done what they call like the connectome. So the neurons that, uh, you know, are the, the worms intelligence, the neurons that uh you know are the the worms intelligence they know how each of them are connected to each other and so here they're trying to model the actual like chemicals flowing between the neurons the electrical impulses back

and then saying things like i move this this cell is a muscle cell so if it gets this kind of level of chemical it's going to shrink in size or grow in size and that's going to move against the environment and then that's going to cause pressure on this sensory nerve which is going to uptick its chemical output and sort of doing this entirely bottoms up sort of not at the like atomic level like there is still you know some amount right picking something in the middle but there's much more sort of cellular level model each cell and then sort of see if you have the emergent property again of like basically a silicon simulation of the worm that could one day even you know find mates and have eggs and those eggs could grow up in this environment and even

amazing refine their genes and pass on stuff and you could just but right now computationally this is like even for as far as we have for a simple simple worm like that's actually i don't say cutting edge to kind of do this bottoms up for a few thousand cells and you can sort of go watch the videos not in real time but of the the sort of worm wiggling around its environment and trying to make its way uh and it's just like a really fascinating like something at first you'd be like this is really silly and then you're like whoa i don't even like it would take me probably a month of or more reading to actually even appreciate what they're actually doing here yeah this is wild i'm trying to figure out who actually uh is behind this oh like uh like what group

yeah well it's actually like uh they have a board of directors um wow it's like a ton of folks it must be uh some kind of um it's a not-for-profit corporation this is wild yeah folks should definitely check out this video at first i thought when i saw open worm i thought it was going to be like a worm virus you know like computer virus i thought the same thing i was like someone put source code up for like uh you know computer virus yeah exactly this is phenomenal though it really looks like a worm the way it moves because they're modeling it as such a law so it did how do they reverse engineer the brain i guess i mean that so i think this is like it's a well-studied organism so for like one of the muscle cells people have isolated it and like observed what

stimulus makes it do what output right and so they have models for most of the cells and like i mentioned people talk about like the the genome or like brain scan, but this connectome, which is like neurons are very, these isodendrites and the whole thing, right? These neurons are very long and spindly. This is not how neural networks work in the sort of like large language

models, but in, in sort of biology, there's like these very long tendrils and those tendrils overlap and touch each other. So if you sort of freeze very cold, like the sample, and then you slice it very thinly, and then you apply like computer vision to it, you can figure out this cell touches that cell there. So they can

pass chemicals between an emitter and a receptor. And so you can figure out the sort of network of all the cells together. And then they're basically attempting to simulate that and this is a relatively simple organism and so it's uh it's sort of attainable wow that is wild very cool folks should definitely uh go to the show notes check out the video this is pretty awesome um all right my news this is a relatively short one but a sad one the creator of vim passed away um so he was in his 60s so he wasn't that old 62 um bram i'm probably gonna get this wrong mulinar um and uh i don't i'm assuming he had some kind of health issue um i don't know if it really said oh yeah here we go medical condition that rapidly progressed it didn't say exactly what it was but um you can actually see on github you know he has all this

activity um and then you know right around i think september of october or september or october the activity just stopped uh that that point he must have got some kind of diagnosis or something um so you know yeah i mean i actually uh i wouldn't say i've never used vim um you know it's been on the computer sometime and i've used it because i didn't have emacs i've been more of an emacs person but uh i know vim's been just incredibly influential on everything did you ever were you a vim user patrick i mean only by like i don't want to say necessity i've never hardcore developed and i have edited files in vim and i know how to sort of get around but i've never customized it or attempted to use it as my ide

yeah same here but uh um oh it looks like he's from holland um originally but uh yeah so uh you know uh best wishes to his family and uh you know someone who really created something really special for the community and time for book of the show patrick what's your book of the show my book of the show is the little book of common sense investing uh definitely a good book uh pretty like i would say easy reading but more importantly sort of like what it represents i guess anyways this is a book by a man named jack bogle who passed away a few years ago but jack bogle uh probably most famous for uh starting the vanguard group and so vanguard group which a little united

states focus for a minute but also i mean has applications to i think a lot of financial markets but basically um his philosophy was rather than doing sort of trading or picking individual stocks he sort of espoused the idea of index funds and of diversification and buy and hold. So rather than sort of, there are lots of other philosophies we can talk about in a minute. Anyways, he sort of had this like, just keep it simple, you know, have, you know, what you think your, you know, allocation should be and sort of just like invest in it. And this will save you fees, it will prevent you from getting into market timing, which he thought wasn't, you know, a thing worth doing. So like a lot of core principles, I feel like now they've gained a lot more traction than

even sort of 15, 20 years ago. This was a little bit more outlandish. People didn't have 401ks that auto invested in target date funds. He was really part of the group that like helped make that uh a sort of like uh thing and so retirement funds being just in some some allocation of equities and stocks uh he has there's a group of people who are very diehard into this sort of like way of doing they call themselves bogel heads after after anyways uh so a deep rabbit hole for sort of investing but the little book of common sense investing comes with a lot of other sort of like

ways of thinking about money i would say uh in addition to just sort of like the investing and savings but just the importance of that um there is a a bunch of rabbit trails to run down here without turning it into a finance podcast about uh just interest but i will say i was uh i saw some statistic the other day just talking about how much growth there has been in sort of broad index investing across the world but but in the united states we have something like the s&p 500 or the russell 2000 the biggest 500 by market cap companies and the amount of people investing just in all those 500 rather than not and they call this sort of passive where you

just buy right don't care if it goes up or down you'll sell when you retire or you need the money but you're not trading the amount of passively invested money there's a lot of uh interesting debate about has this changed market dynamics is there like an end game where markets are somehow like messed up because it doesn't matter what your company reports as its earnings, like everybody's gonna still buy it because it's part of the S&P 500. There's a lot of debate about what sort of changing I won't get into sort of my thoughts there, the efficient market hypothesis, there's a lot of a lot of stuff around this. But anyways, a lot of folks listening, you know, early in your career or not, and sort of wondering of a way of thinking about how many you could do a

lot worse than picking up this book and sort of wondering of a way of thinking about how many you could do a lot worse than picking up this book and sort of thinking about just diversified holdings, not trading, just being really sort of straightforward, not making it over complicated. And this is this is sort of like the vast way of, I think, modeling how I think as well, to in part because of him and others in a similar vein. Yeah, that makes sense. I mean, just a short story. If you don't diversify, if you take huge risk, you could potentially get huge reward, but you could also get completely wiped out. I know if you are going into industry and they're paying you in stock, then you're potentially going to end up with a lot of shares of stock of your company

that you already work at. And, you know, I've heard stories where people said, hey, you know, I've worked at the same company, you know, I was one of the first employees, I've been there for 10 years, the company's doing amazing. And I never sold any of my shares, and it just exploded. And that's because they took this huge risk, and they got this huge reward. And that's great. You don't necessarily hear the stories of the people who worked at companies, company rose up, the company went public so that they could sell their shares. They held on to everything. And then inevitably in the next five years, 10 years, 15 years, at the next point in time, at some point, the company collapses and that person loses everything. That does happen more often than as a community, we want to admit. And those stories aren't amplified because no one wants

to do that. So you really have to be careful. And yeah, I'm with Patrick on this. I think, you know, reading some sort of you know it doesn't feel like much you know a little bit here a little bit there but then when you keep doing it year after year and i think it's actually a philosophy i feel mirrored and how i think about my career growth as well is just i'm never looking for like so i'd have this oh we see this now with large language models coming out people jumping on like oh i'm going to be a prompt engineer i'm going to figure out you know how to use you know this or we're talking about okay 99 i'm going to go like figure out how to synthesize your super okay but like that is a way i'm not saying you can't it it has a a more dispersion and sort of like your outcomes you might do really well often you probably won't the average case probably not

that great but i feel like in your career just looking for incremental each year what's you know one two three things you can do or learn that add on to what you already have i feel like this is a way over the course of a career 10 20 30 years all right you can be really really good at stuff by the end if you're just making sort of compounding incremental progress but maybe that's a a broader totally agree totally agree also uh just just to riff on that a little bit and then we'll move on but um a lot of the times these like rags to riches stories are kind of bs and and and when you see something small turn into something really big there actually was a really big concerted effort to make that small thing big and so you know actually a good way peter teal puts a pretty good way he basically says if you're a big company you want to not seem like a monopoly

because you don't want to get broken up and if you're a small company you want to seem really big because you want the investors to get really excited and so it creates this really weird parabolic effect um and so a lot of a lot of uh um a lot of of small companies actually maybe had a lot of of push from the outside and they weren't actually that small and so i give you the impression that like yeah in your basement you could start x billion dollar company but but when you actually dig into the details a lot of the time there's like huge institutional backing even from day one um all right we'll move to my so patrick i did this for you um yeah i see this i'm excited let. Let's go. Yeah. So I decided to read more fiction. My son, basically the way this happened, my son finished Harry Potter the second time.

He read it, threw it twice. And one of my coworkers suggested Brandon Sanderson because he has a book. Who's that? I think it's called Skyward, the one for kids. Yes. And so I did that and I thought, you know, I really should read more fiction. I read all these programming books. I read some economics books, philosophy books, you know, and I just need something lighter,

especially I knew I was going to be on an airplane a bunch the past couple of months. And so I got into the Mistborn saga and it is awesome. I am a big fan. I remember you talking about this years ago and not wanting to spoil it but but uh just to recap what Patrick said many years ago there's people who can manipulate metal um in a way that's really magical and um there's all sorts of uh things that that that are spun off from that one idea. And I think I've only finished, I'm about halfway through the second book. So I still don't quite understand why.

I mean, I'm not spoiling anything here. You know, why there's ash all over the place. Like what actually caused the earth to be destroyed like this? Like I haven't uncovered any of these secrets yet, but I'm a book of an and a half in i'm i'm really uh excited and uh it's um it's something that uh i've been really enjoying so so it feels good to get back into fiction i think i'm going to keep it up yeah they and now like you know this is the original trilogy but then there's also now like additional books that are set after the that trilogy but then there's also now like additional books that are set after the that trilogy so you actually have a lot of runway ahead of you uh and then now that

you're in the uh brian's that brandon sanderson like thing you'll find out that the system he's applied here is actually part of a meta system so like the way that metals sort of work here is similar to how other things let's just say work in other locations in the universe of his books and so the there's a treatment of metal in sort of this that is handled by other things in other series and so and there are sort of like intertwinings between the series as well they're not completely isolated so um yeah just to kind of like set the stage like to dip your toe and then not to get scared but like yeah you can keep spiraling further and further out from uh from where you are but yeah i mean those first ones it's some of those nostalgia like you almost miss miss going back and like that first kind of

like oh what that's just so crazy and it's so cool yeah i remember it's those are good they tried to make it into a video game i think but i believe it's stalled out i yeah i think it's stalled out yeah oh yeah i thought um um i thought that was a clever way of saying it basically like imagine if this whole section of the periodic table was like off limits it's like kind of like a weird thing to think about, but it's like a good premise behind building a universe. You know, it's really because it's,

you know, one thing that, that I try to shy away from are things that are like futuristic, like star Wars. And it's not that I do, I have any apathy to that or, or not an apathy, but any,

it is really apathy. Like when it starts getting into laser beams and spaceships and stuff i just it just not doesn't really kind of engage me the same way but here it was you know it was real enough for me that i could kind of see it in my in my mind's eye and uh um i might end up getting into the into the i know that that there's skyward and all these space ones i might end up getting into them, into the, I know that, that there's Skyward and all these space ones. I might end up getting into them mostly. Well,

I'm excited. You have to keep us up to date. Yeah, totally. And I've been jumping into tool of the show. I've been reading this on my remarkable, which I've been really happy with. Do you,

do you have one of these Patrick? I do not. I do not. I do not. So I, I've been wanting, I had a composition have one of these patrick i do not i do not i do not so i i've been wanting i had a composition book full of notes and i'm constantly flipping among different notes i had basically a page in this book for each person on my team i had pages for different topics and so you know if someone would say something that i would need to tell someone else i would flip to that page in the book.

And it just felt kind of silly in today's day and age to be doing that. But the reason I was using a composition book was that the act of writing really helped me remember. Not only remember the content, but remember that there is something on that page that I need to take care of. And also I could go back through and cross things out which I know you could do that at google doc but um I just found the writing part really really useful so so I thought I would get one of these kind of uh note-taking tablets um there's a bunch of options there's a books there's uh amazon has a scribe which looks pretty good I settled on the remarkable because I was it was recommended by a couple of coworkers. And I think it's great.

You can read books on it. You could take notes with it. It has some other features like OCR and stuff, which I haven't really found them that useful. But the core functionality is extremely nice. And I'm usually not one of these people who has any type of fashion sense or any modern gadgets or anything like that. But I will say when I pulled out the Remarkable on the plane, the people who sat on either side were very impressed. It is kind of like a very large Kindle, but it's extremely well manufactured.

It's very thin. The contrast is extremely nice. And yeah, I would highly recommend it. So e-ink, right? Oh yeah, we should talk about that. So it's e-ink, which means, I think the way it works is some electricity is forced in a certain frequency and that tells the ink to reveal itself or not and that happens per pixel and so that means is like it takes a little while so like for example you can scroll but when you scroll it's scrolling at

like half a frame a second or something and so it's kind of a weird feeling. It makes much more sense like flip page to page. But then the nice thing about it is, is the battery lasts for basically months. And, and while you're not doing anything, it's not using any energy. And in fact, if you leave it for 30 minutes, it will turn off the Wi Fi, turn off the processor basically totally go to sleep and not use any energy but you still have the whole screen like whatever you were looking at 30 minutes ago is still there um it just put a little icon next to it saying it's asleep um so yeah i mean i rarely have to think about charging it and uh yeah i read whole books on it and used like 5% of the battery. So yeah, it's a good product. I will say the Amazon Scribe has backlighting.

This one doesn't. And so for an airplane, that's fine because you have the overhead light. But you can't use this at night without having a light next to you. Now, just imagine if you had a remarkable and lk99 just imagine the battery it's like i start using it at 50 and then i have to turn it off because it overheats from your hand yeah all right my tool of the show is stellarium i think that's how you say it but but just more broadly there's a the class of uh i'll say sort of astronomy apps i've always had this thing like i was never big into astronomy i don't know if you ever were jason billy i had a telescope once

but i was never very good at it uh so i started to get interested in it again and i one of those things i think i downloaded when i first got a smartphone where you like point your phone up in the night sky and it tells you, you know what? Oh yeah. I still use that. Yeah. Not by image recognition,

but just by like compass and accelerometers and understanding pose. But they just, I don't know. Like, I guess I just continued to work on it and I feel like I used it and it's just like, Oh, this is actually really cool.

And then also being able to know like, when is something I want to see, I want to show my kids Jupiter or whatever, right? Like, Oh know like when is something i want to see i want to show my kids jupiter or whatever right like oh well when is jupiter going to be in the sky and just like having it's just very cool and i was uh i'm trying to gonna try it's been really cloudy here so i got this idea that i'm like i'm gonna do this i had an old telescope i got out and like then it's been cloudy every night so it hasn't worked yet but i haven't been taking this still airing out and like trying to look up and like imagine what the stars would be uh and uh you know

it's just pretty exciting one of those things i kind of forgot existed even though i mean i guess probably lots of people will use it i think most of these are free solarium as others are free to download they i think they charge you for like additional entries in the star database or, you know, if you want to search for certain things or do predictions about, I guess they're not really predictions, understand when something is going to occur. But in general,

you can normally use them and poke around them for free, which is, which is pretty cool. So if you've never tried that before and you have a smartphone, which probably do, if you're listening to this, then I would recommend, recommend checking it out.

Yeah. I mean, I had my first moment where I felt like my son who's 10 is like just light years ahead of me in something. And he's really into science, all kinds of science, biology, astronomy. He's constantly reading books on it. And I was pointed to this star that was really bright and he goes oh yeah he's looking around the sky he's like i'm pretty sure it's venus and i thought you know a 10 year old's

like they're just making stuff up all the time right so i pulled out i don't know if i'm using the same app as you but i pulled out one of these apps and it was venus and like it totally blew my mind um but uh but yeah that stuff is is super super fun it's a great time if you're ever watching fireworks or ever in a situation where you're out at night it's really fun to pull that out and see all the constellations and everything yeah i when it has all the constellations on there i'm just like oh yeah it turns out i don't know anything about any of this if you had pointed out a bit like be like, yeah, star. And then I wouldn't have been wrong. Oh, man.

All right. On to the topic of recursion. The scariest topic for every first or second year CS student. No. I mean, not for me either. But I think that in aggregate, people got more scared about recursion than anything else. And I think, you know, we're going to jump around a little bit in the notes, but I think the reason why it was scary is because the way that it was taught, at least at my university, which as we know from LinkedIn is a crap university. I actually love my university.

I went to UCF, University of Central Florida. I loved loved it there it's a great school for CS but they're kind of being the butt of today's episode so you know people were taught sorting right and so sorting it's kind of like this tool like you immediately see how it's useful like you could see I have a list of things and I have a sorted list of things. It makes sense. And then they're taught structures like, uh, you know, a linked list and, uh,

uh, you know, what's another entry level structure, maybe a binary tree. Yeah. It's just like, okay, these are structures and I don't really know how they're useful yet,

but, but, but, but, you know, it's like, I could see the structure and the geometry of it and understand it right. And then recursion, it's kind of like they're trying to fit that mold to teach recursion and it never really works.

So what will usually happen is they'll say, well, you know, the one I think they use is the making change. So they're like, OK, in the American system system you can greedily make change where you just give people as many quarters like let's say you need 74 cents in change i just give you quarters until it's less than 25 and then i give you dimes until it's less than 10 and we just keep going right but what if there's this crazy you know coin system where like there's a seven cent coin and a three cent coin and a one cent if i give you the seven cent i can't give you the three cent and yeah i mean i guess patrick's like head is exploding right now well no they taught you the knapsack problem as like an introduction to recursion

that's very brutal yeah and it's like you know here's how you make change with you know and here's here's why you can't do it the normal way because you're not in normal currency and the whole thing was just like didn't make any sense right and it didn't really relate to other stuff i feel like um i think the reason they do this is if they were to connect it to other things and you didn't grasp those other things now you're just kind of falling even further behind right so if they said well here's recursion and how it applies to sorting but like the kids didn't understand sorting that well it's like then you know they kind of totally lose them but uh i guess in general maybe to step back a bit recursion just wasn't in general i feel like isn't taught very well and that's what makes it so scary to so many people i would agree i wasn't taught that like to be clear the problem you're introducing is

this is pretty difficult so we were taught it with i think you you uh you probably encountered as well but how to calculate the fibonacci sequence uh which for me was demotivating in a different way which is it was such an obviously horrible way of computing the Fibonacci sequence. Like it is not a, like that is like not the way as someone who I guess started in like a more optimization C like low level coding way. As soon as you tell me that you're going to like,

I understand what you're talking about with recursion. And then I'm like, no, you do not want to do this. This is not very efficient. And so it bothered me for a different way i think though you're right i think this is not a it is a natural phenomenon but not in a sort of like intuitive way you would encounter perhaps before you would be encountering this so if you've not encountered fractals or self similarity before this idea that you have a function and inside that function is an

invocation of the function itself this like self-similarity self the recursive isn't something you would be have been introduced to in math although it does exist in math you would probably not have seen it in the math you would have taken at that time unless you moved to computer science very late in your college career and so i think approaching this like hey and we're going to talk about in a minute but like hey you're going to just infinitely go down and down and down and down or forking all your way down you just start to get this mental model that's very difficult because it's not this sort of iterative uh you know imperative way of programming anymore in fact right like functional programming

itself it bears a lot of semblance this versus imperative programming so you think you get a lot of those ties and then also the failure case when you mess up your sort of end condition is your program crashes and it doesn't crash with like a good error it crashes like out of memory which for you know if you're in j Java and not sort of C or C++, where you've already encountered 1000 memory leaks, you're probably like, Oh my gosh, like, what is going on? Like, what does this mean? Right? Like you're like a 10,000 pages of a stack trace or something. Yeah, exactly. Like, you're not getting useful debugging information when your program crashes. And when you try to print something like jason is saying

you just immediately get like you know pages and pages of logs until your stack overflows and then you crash so the like interaction with recursion at least in most of the languages that i'm familiar with being taught in college uh is or high school uh it's a bad experience yeah that makes a ton of sense you know it's um um it's a really really really good point that there isn't a print function which like keeps track of the stack there isn't a print function that's like like okay here's this variable and here's the same variable you know in the parent function and the parent of the parent all the way to the root call of this function you can't see that all on one line unless you you know build that into your program which is not trivial um and so you're right what you're

looking at is you know i see all of these prints and they're all from different invocations imagine like the fibonacci sequence and maybe i'll take a little bit of time to cover what that is so i think it's f of x minus two plus f of x minus one something like that yeah okay so fibonacci sequence um so there's it's it's a function of x x has to be an integer and so it's a discrete function and f of zero is is one, f of one is one. So those are your base cases, right? But then f of two is going to be f of zero plus f of one. So in this case, it's going to be two. f of three is f of one plus f of two, right? f of one is one and f two, we just calculate as two. So f of three 3 is 3 but then you can kind of imagine

how this is going to start growing really quickly because you know you're adding these numbers that they themselves are getting larger and larger and so it grows in probably some kind of quadratic way or exponential way um and so if you want for example f of 100 then that is f of 99 plus f of 98 now if you've already computed those in the past then that's fine but if not you know you have to compute those which means now you have to call two more functions for each of them and you can see it turns into this this binary tree and all the leaves of this tree are going to be either f of zero or f of one but as you kind of climb up this tree you're getting larger f values and you're getting a lot of repetition you could potentially be calculating f of four you know thousands and thousands of times to get to f of

100 um and uh uh you know and once you finish you know uh you know computing this whole tree then you get your answer but you know depending on how you write the recursion, you're kind of going through this tree in kind of different orders that might not be very natural. And so if you think you have some error in your Fibonacci function and you put a print, that print's going to give you all kinds of different numbers from all kinds of different numbers from all kinds of different

contexts and it's very hard to debug i mean i'm not a teacher and i'm not an academic so i've not attempted to teach recursion fibonacci sequence knapsack prompt i don't know i think maybe we talked about sorting i think actually attempting to teach something like a binary search or a merge sort which is not how i first encountered it but where you have actually like a binary search or a merge sort which is not how i first encountered it but where you have actually like a fixed length list bounds the problem a bit right where if you screw up your indexes a simple print statement would sort of tell you you're either repeating an index or you have like your lower bound is flipped with your upper like some very simple detective work would sort of reveal to you that you've encountered this

problem and i think the exploration of a tree or of all possibilities which is sort of the knapsack problem and the fibonacci sequence feels like mentally more of a a large step than this sort of uh divide and conquer right like i'm splitting something into smaller pieces and even though i guess it's kind of the same thing it's a quantized very quantized thing right like i have a list of eight integers and then i have two lists of four and then four lists of two i'm gonna mess it up i keep doing this anyways and so i feel like this is a more i don't say intuitive maybe for some it's not but i feel like uh that is the other like piece of teaching the the recursive is using

it for sorting and binary search and and we're not even getting into trees or this just yet but i feel like that setup maybe maybe sort of the sorting itself like why a sorted list emerges from merge sort is a bit harder to grasp maybe but the sort of like operational bit of it makes a lot of sense yeah i think you're right i think you know the reason why they use fibonacci and knapsack problem is because you know if you're doing um like a tree search then you don't need any memoization right because you look at something once and if you got your answer you're done and you didn't, then there's nothing to really remember because you're never coming back. And so they try to teach, you know, recursion, memoization, and the ultimately like the sort of, I don't know what you call it, agglometric way of doing

recursion all at the same time. So I'll explain what that means so so fibonacci numbers right we just talked about if you have f of three it's f of one plus f of two but f of two is f of zero plus f of one so you see f of one is there twice you need it for f of two but then you also need it for f of three and so you know if f of one was really expensive to compute then you're paying that cost twice right so you could do something called memoization you can say well i'm going to start with f of 100 um and when i compute f of 98 um i'm going to store that somewhere just in global memory somewhere on the computer it's like i computed f of 98 it's whatever it is a zillion whatever um and i'm going to store that

in a table somewhere then when i go to compute f of 99 and it needs f of 98 i just go to my table and fetch it i don't have to compute f of 98 more than once because i know there's no side effects every time i compute this function every time a 98 comes in exactly the same number is going to come out so if i could just store this then uh uh then i would only have to for f of 100 i'd only have to compute 100 things because even if i'm calling f of 98 twice, I'm only computing it once. And so that gives you a really nice bound on how much work you're going to need to do. And in the case of Fibonacci sequence, you know, f of 100 could actually take a while on a computer doing it the naive way. But as soon as you do this memoization, it goes from taking seconds or even

minutes to like taking you know i don't know 80 nanoseconds or something like an insanely short amount of time um then you can say to yourself okay well you know i still have to deal with like the whole recursion thing and the call stack and calling and what happens if i even just doing, if I do F of let's say a hundred thousand, I need my recursion limit to go at least a hundred thousand levels deep, even with the memoization. Right. And so maybe my computer can't handle that. So what if I was to instead do something a little different? What if I was to say, okay, F of zero is zero f of or sorry one f of one is one um and and i already have those those are in my table let's say i put those in first so now what is f of two well i don't have to do any recursion because i know that anything less than two has already been computed so i i

just say well f of two is f of zero plus f of one and not literally calling f in that time but just pulling those numbers out of my global array and sticking the two answer in right same thing when i go to compute three i already know that that zero one and two have already been computed and so i could just write the answer for three and write the answer for four. And so you don't even need recursion. You have recursion in a mathematical sense, but you don't need it in the computer. You just have a for loop from one to 100,000 and just write 100,000 answers. That's even better, right? And that's the, I'm using the word agglometric, which is just a fancy word for saying, you

know, bottom up, but that's the way to do, where you don't even need to have the call stack. I thought you meant something different. I didn't, I'm not familiar with that word. But the adjacent thing, I think, to what you're saying, in the same realm of like stuff taught here, is the sort of duality, not just with the math but also is saying recursion what is recursion at like a computer level uh that's my background more than maybe the sort of analytical side at a computer level what you're saying is store where you were jump i mean all functions are this way sort of stare store where you are on the on the stack and put information about the how you want to invoke the function so for fibonacci you're saying hey i want this other fibonacci and you give it a number an index or

whatever right and you're saying calculate that so i need to communicate to the new function of where i'm going jumping to uh that information but i need to store all of my state so when you do this in your computer program all local variables basically need to get put onto the stack uh so that you can go do this again right and that's what jason is mentioning if you do a hundred thousand you get this hundred thousand deep stack well that's because of all the extra overhead uh the chances of you blowing up your computer resources are a lot higher when you do it that way but you could also say hey there's no difference between using the sort of the data structure stack instead of

q and so what do i need to know i just need to know that i want to at in a loop i want to you know either compute where i am or put new things on the stack and then pop things off the stack, right? And so the stack here has a duality. There is an actual data structure stack in your like CPU and RAM that your operating system is maintaining. But we're also saying like the stack is this sort of like concept of, you know, descending down in your recursion and you end up with this kind of like fluid set of words that kind of describe all of them at the same time interchangeably but sometimes you can get around the limit of you know an operating system depth of stack by just maintaining a stack yourself and pushing items onto it and popping

them off the back and the evaluation order would be identical to your recursive definition in your program but you've removed recursion well have you or haven't you i mean i guess it's a a terminology thing but this is the other uh sort of way of thinking about it and so all of them are roughly equivalent like all of them are the same you are doing the same operation but it's just sort of operationally how you end up achieving those results yep yep that makes sense and so yeah this whole thing where you kind of like reverse the problem like the the fibonacci example where you want f of 100 but you just start computing from f of zero and you stop when you hit 100 that way of sort of reversing it, you know,

it works for Fibonacci and it works for the knapsack problem, but like the vast majority of problems, it doesn't work that way. Like, like you can't say I'm going to, yeah, I'm going to search for a number in a binary tree, but I'm going to reverse the problem where I'm going to check all the leaves

first. Like it doesn't, it doesn't make sense, but because they want to teach that reversing part they can't use trees and binary search and these things as examples and to your point that forces them to pick these really esoteric examples um and i can tell you from personal experience like i've done a lot of recursion in different contexts mostly when dealing with graphs and stuff like that i have never ever done the thing where you reverse it like uh yeah where you reverse it and you say like i'm gonna

go from the base case and build this breadth first thing in the base case i've never ever had to do that um you know hash tables are so so fast now um that you can do the recursion with memoization you have never needed to go hundreds of thousands of levels deep in the stack so a lot of these are kind of like not real problems and and i think uh to your point if they had done if if they teach uh recursion without that last step they could open up the aperture a bit um and yeah kind of with that in mind we can talk about you know what are the times you know practically like in our careers where we've used recursion you know i talked about in my case the biggest one is graphs um there's many times that

i've had to deal with graphs i worked at this company where we had this big social graph that was uh that was kind of important. But even more important were all the process graphs. So if you say to yourself, you know, I have this process, it's going to run and it's going to produce an artifact. I have process B that's going to produce another artifact. And I have process C that's waiting on those two artifacts and it's going to produce you know a third artifact so now you can kind of imagine this graph this acyclic graph where you have all these processes and whenever you know the conditions are met for your process you can get started and those conditions form a graph and you often need

to do all sorts of things that graph to say you know how long is this going to take or or uh you know if this part failed what needs to be regenerated um anytime you're doing anything with graphs you're almost certainly using recursion because you want to see you know what are all the connections not just the first hop but you know if this process fails what are all the nodes that can't run and and so it ends up fitting very nicely with recursion what about you patrick i'm kind of curious you you might have zero recursion or you might have a lot i really don't know we're going to find out yeah so it was the thing i was bringing up so i mean a couple observations is

so one is not too too much uh but for binary search is a big one so the sort of night way but then as soon as you are like oh i'm gonna do binary search i'll do recursion you're like i'm doing it in a loop uh so um yeah it is the recursive modeling in your mind but doing it sort of like with index tracking especially as jason mentioned if you're only gonna you only need to go one way sort of in the the Fibonacci sequence this happens, but in other stuff like binary search as well, like once you get to your end result, that's tail recursion, right?

Like basically if you get to your end result and all you're doing is returning up what you found, then to be fair, the recursive part, unlike a sort of I'm computing some metrics on a graph and I need to preserve both and I need answers from two different paths and some computation and make some decisions this is more complex if all you're doing is looking for something in a tree and you're sort of you each decision in the tree you're only sort of having a singular sort of evaluation going on and

then you get to your end and you just pop pop pop pop pop pop pop these ones become very suitable for for moving into loops almost trivially and in fact some compilers and in some programming languages this is sort of like a first class handled thing to do so so binary search i've used it a fair amount to do that and then like you mentioned as well sort of sort of exploring graphs but i would say actually exploring graphs is a model for a variety of things. So lots of things kind of turn into graphs depending on how you sort of do. So some geometry problems

where you sort of have like, imagine a polygon and it has edges around the side. If you're doing traversals, that can end up looking like graph traversals and have a similarity. But even when I'm mentioning you have an array that's sorted and you're doing binary search, even if you're doing a recursive it ends up being a tree right you're treating the the array as a tree in place so it also becomes a form of acyclic graph it may

not ever be that way but it is a duality of the problem it's just a different representation and so in that way um kind of the same things you're saying because i would say almost all problems that get handled this way have a lot of similarity to each other yeah that makes sense when you um um in some of these languages like c++ is there like a memoization library that you can use or is there anything i mean is it mostly just coding it out of hash tables yes uh i mean this is one of the things i know in python you can add a decorator which i was blown away the first time i saw this to memoize and i was just like what this is crazy uh this is voodoo but uh yeah i know in c++ it's just yeah mostly an unordered map and then making some structure

for your function arguments and caching them yeah you know the thing about not to go on too much of a tangent here but like you know imagine if you have a function and it all it does is it does some work up front it calls your it calls another function and then does some work afterwards uh you can you can make that a decorator so in python like a decorator can do just about anything um and uh and so yeah the decorators are extraordinarily powerful we recently at work um we created a decorator where you know you do at sign i don't remember what they called it but you know and what it will do is take the output of your function and before returning it will like store it in a database um and so you could do all sorts of really fun stuff

with with decorators but under the hood i think um what python takes advantage of is the fact that everything is hashable um i think with c++ um how does oh yeah i think with c++ there's like a something you have to implement right there's like an interface interface like a hash type or something like that yeah you need to override if you want to insert it into a standard hash table so ask the either hashable or you have to provide a way of it being hashed got it okay but yeah i guess just to kind of uh wrap wrap that part of it up so you know we talked about the feminace example where you know you go to compute f of 98 and you see in your table that oh the 98th element has something in it so So that means I've already computed that. What if your recursion is like the arguments are a lot more complicated, right? Like

what if it's a list of people's names that you've already looked at? That is the input to the recursive function. Well, you have to have a way of saying, oh, I've looked at this set of people already. And so what that means is ultimately is hashing. You need to have some type of hash table, some type of one-way hash where you take the input, regardless of how complicated it is, you turn it into a single number,

and so then you can go back and look for that item again. Before we finish our discussion of Fibonacci sequences to save someone from writing us in, but Fibonacci sequence is like a very common, I don't know why it gets taught in CS, or actually I do. It's this like interesting property

where it's associated with phi, where you divide sequential Fibonacci numbers and it is a closer and closer approximation of this numerical constant phi. So this is very entertaining to people, but this is a broader part of the Lukas sequence, L-U-C-A-S, which is just all these recursive functions defined this way, and Fibonacci happens to be the one where it's two consecutive, and the first two numbers are one. But this is the one that gets talked about but there's also really other

fascinating properties and a lot of the other i think i'm saying that right luca numbers uh i think there's like if you watch number file youtube there's like a number file video about this where they go into it's sort of one of those uh what is it it's tau versus pi right like tau is superior instead of pi and anyways it's like one of those like uh debates that get raging online that's right if someone's here like ah they're giving more credit to fibonacci sequence here's your shout out to the lukas sequence yeah there was somebody at work who was celebrating tau day and it caused me to go down this internet rabbit hole where i don't know if i came out of it any smarter but i learned a lot about tau um so i guess i like frantically googling what are they

talking about now yeah um i you probably remember this like tau is some type of constant like pi is is uh it's two pi it's just that's all it is oh Oh, okay. It's twice pi, or pi is half tau. However you prefer to like give precedent. Got it. Yeah, there's, oh man, we should definitely do a show. It's a little out of scope here. I'd love to do a show on fractals and the whole like, you know, the points on the space where the fractal goes to infinity and where it doesn't go to infinity.

I'm totally drawing a blank on uh what is that thing called it's like those those plots those fractal plots like a syrin penske gasket like what are you no it's a mandelbrot set that's what i was thinking of so yeah the mandelbrot set is you imagine if at every point on some grid you plotted like how long it takes for if you use that as an input how long it takes for the output to reach uh infinity or whether it reaches infinity or not something like that i think it's uh because oh that's one thing we didn't really talk about is you know fibon Fibonacci, you know, has a has a base case. And so eventually, you know, it kind of results in some number. But you can imagine if you kind of went the other direction, it would just explode to infinity unless the numbers you're adding are also getting infinitely small.

So if you add, you know, half plus a third plus a fourth plus a fifth, a fifth, the numbers you're adding are getting infinitely small. And so even though you're going to infinity, you're actually approaching a constant. It's kind of a weird thing. Yeah, so the Mandelbrot set is you're taking the X and Y value of a Cartesian plane and using them as inputs to complex numbers. And when you multiply complex numbers, sometimes they end up converging and

sometimes they don't and so that's what like you're multiplying over and over in this sort of recursive relationship and where it diverges very very quickly diverges slowly converges and if you plot those out you end up with a very surprisingly complex shape yeah exactly exactly i think i i don't know if this is helping anyone well we'll do a whole show on fractals fractals are really really fun um we'll give our brain some time to rest from recursion and we'll do a fractal show in a few months um so yeah i think uh you know maybe we could kind of walk through you know how to solve problems with recursion kind of a step-by-step way so imagine you're you know in the elite code competition of a lifetime or something and you have uh uh you know or even you're in your day job and you have to to uh solve a problem with recursion the first step you always tell folks is to write out the

base case and make sure it's really comprehensive so you know one thing i'll see a lot of problems is where it's like okay f of x minus 10 plus f of x minus 1 let's assume we have that kind of function if i have that then you know what's my base case for like negative 6 like what happens like if i call f of four and that causes me to call f of negative six like is that is that okay if i can't have f of negative numbers now four needs to be a base case like i need to handle that in some special way so like make sure that there aren't any holes and that you always end up landing in one of these one of these pockets where you're returning a constant

or something that can be easily computed. Once you have the base cases and you've kind of looked at this and said, oh, this is comprehensive, then you build the recursive step. And similar to what I said before, when you're building that step, it's a good time to make sure that you're not you know that you're all of your base cases are covering all the ways you can call that and it's very hard to do this you have to rely a lot on intuition and just reading the equation carefully then I would say you know once you have that then you could optionally add memoization um you know if you are doing things in a global context like if you're reading from a file or if you're you know checking the internet or something well then you can't memoize because maybe you call f of four twice you get two different answers and and if that's by design now you can't memoize so ideally you take whatever that

external thing is that's causing your f of four to be different and you and you make that one of the inputs so one of your inputs is you know the weather today or something like that so you make it so it's i think the word is idempotent you Make it so that every time you call the function with these inputs, you get exactly the same output. Then you add memoization, and you should be good to go. As far as testing recursive things, Patrick, you should definitely chat about how you test yours in your context. But in my case, I usually have a way of generating uh inputs and outputs

so most of the time if you're doing this like this example with um trying to see how long a job is going to take um you can if you for example the job is a good example you can say well i have i want this job to take 60 seconds i want the answer to be 60 and i'm going to just divide i'm going to put portions of this number 60 in my graph so i'm going to have you know uh a chain in this graph that's going to add up to 60 and then i'm going to make a whole bunch of other chains that have like one e to the negative six time where i know that they're never going to take as long as that 60. And then I run my unit test and I should get back 60. If I don't, then something has gone horribly wrong.

And nine times out of 10, when I write a test like that, it actually is horribly wrong. So testing recursive stuff is really, really important. Yeah, testing is important. I would say like, I'll riff on it a bit and say like for me, especially at least in the beginning and with whatever your languages contracts are for,

which is basically adding checks for like what level of depth you're at. So keeping a counter and saying, Oh, Hey, I'm at level, you know, a hundred or whatever. Is that something expected or something unexpected?

And just adding something that gives yourself a nice helpful print statement or an assertion that says these things shouldn't be ever more than 100 or have more than so many results in your memoization map or whatever right and sort of adding some bounds checking at least initially just to make sure you don't get into that frustrating loop where you know you're computing thousands and thousands of things and it's just breaking and you can't kind of figure out why so i think that's very helpful um or jason was kind of alluding to it before that it doesn't do it for you but as you've been developing for a while coming up with creative ways to visualize the like call graph either you know in your debugger which can still be pretty difficult

but like in your outputs like having some ascii pattern or something that tells you what level you're at or how the stuff is nested or adding more spaces to the beginning i've done various things i think this can be really useful so not in the unit testing context so much but in the like uh-oh something has gone wrong like how do i you know get it back under control i think these these kinds of things can be very helpful yeah that's a phenomenal phenomenal point like in general if you you should write your program such that it never runs forever um because that is the most painful thing to have to debug and so um especially if you're giving your program to someone else like this is a piece of software that people are going to install in their computer and it just runs forever and you know

burns their battery or or just you know it keeps their computer from going to sleep these are all things you should avoid and so paddock is exactly right every single recursion i've written in practice always has some type of check that says hey you know i've called this function you know 10 000 times that that can never happen i i never expect someone to have a workflow of 10 000 units long and so i'm just going to abort i think where we get bit by that sometimes is uh people will do what they think is like a mathematical thing so every so often we'll run across uh a some computation that doesn't have a closed form solution that is there isn't a direct way of solving it in a finite time and so you'll use newton's method to solve it which is we didn't talk about this but this is basically the same

we talk about it iteratively but it is also somewhat recursively defined and in fact often people will define them recursively and you won't terminate because you'll end up in some state where you're oscillating between two values because of numerical stability and floating point or whatever yeah and so like making sure that someone is keeping track of like we say how long but often that can be expensive or difficult to do but just like how many iterations you've gone and just set some like maximum iteration count that's reasonable and if it didn't work either report that there was an error or just say look you're close enough like it just deal with it um but yeah i think like making sure code like jason i i have i do occasionally write while true or for ever uh it always really scares me because i'm like this is really i should just write I do occasionally write while true or forever.

It always really scares me because I'm like, this is really, I should just write while, some counter is less than a million or something. Because it's really scary to write just a loop forever. Even however many years I've been programming, I still get scared to write loops that don't have an auto exit condition because you'll mess something up and it'll just run forever. And that's a very frustrating thing for people after you bumping into.

Yeah, I mean, one practical example of this recently was I was writing some code that was interpreting JSON. So I had this JSON object and json object was recursive you could have modules that had modules um so you could have objects that have objects and uh and but you know the recursion was pretty limited like you'd never really go more than three levels deep but i had a bug where you know i was reading my object and then instead of reading all the children objects i read my own object oh no that many times for however many children there were and uh um yeah and it just never ended and and the worst thing too is the way because it blew up the call

stack it caused like my computer to act all weird and you get these kind of weird things or your mouse slows down if you start blowing up the memory and everything so so yeah just yet another data point for uh putting some type of constraint like if you know you're never going to call us more than 10 times you know 10 levels deep and just add one of your inputs you know uh how deep am i and uh, and if it's, you know, 20 or something, you know that you're in trouble. Cool. All right. Well, that was a recursion. You know, if you have any other questions, don't hesitate, you know, leave comments, reply to us on X, or send us an email. i'll be happy to to continue the discussion over

there but uh yeah i want to give a huge thanks to all of our patron uh patreon patrons all of our subscribers thank you so much for all of your support and uh we'll see you all next time no we'll see them in episode 163, Recursion. That's amazing. See you all later. See you guys. Music by Eric Barndollar. Programming Throwdown is distributed under a Creative Commons Attribution Sharealike 2.0 license. You're free to share, copy, distribute, transmit the work, to remix, adapt the work, but you must provide an attribution to Patrick and I and sharealike in kind.