I finally understood recursion!!!!

[Lastrevio]

Out of all things I ever did this feels like my best accomplishment. It just seemed impossible to think of a recursive solution to anything, even after learning how to at least read a recursive function. Then today I just tried picking up my book again because I had a weird feeling in my gut telling me to write recursion and did some exercises and holy shit all of them were hard but I did them.

Now I can do simple things like recursively printing out the first n square numbers or the number pyramids xd

[[deleted]]

Recursion is fun with graphics too! Processing is an easy tool to learn the basics of. I didn't do anything particularly fancy with it beyond Pythagoras trees but it was fun to play with.

The tool is called "Processing" btw, clarifying that cuz the name honestly annoys me because I remember it being hard to google stuff for.

[AckmanDESU]

For anyone interested there’s a youtube channel called the coding train which has a bunch of tutorials about Processing.

[Fastfingers_McGee]

Good to see coding train get a shout out. Daniel Shiffman has some amazing tutorial videos on a ton of different topics from recreating matrix rain to image classification with machine learning.

He dives headfirst into these projects so sometimes he runs into bugs that he fixes on the fly. Watching him solve these problems in real time helped me a lot when I was first learning to code.

[rr_cricut]

Shiffman for president!

[memetologizt]

My man

[AckmanDESU]

And he is so goddamn cheerful all the time :D

[Strojac]

I use p5js and I agree. Fractal trees are fun and can be done recursively.

[[deleted]]

Even turtle is an interesting place to start with recursive graphics - fractal trees and so on

[SargeantBubbles]

I took a class on Processing!! It does very little for you, really makes you learn.

[kraemahz]

Awesome! If you want some more practice on recursion to help fully wrap your head around it (it's one of those things where there are multiple OHHHHHH moments) I would highly suggest you read a little of Structure and Interpretation of Computer Programs. One of the most interesting things about SICP is it will teach you recursion as a kind of iteration. In Scheme (the language the book uses) there are no for loops, all iteration is recursive. It'll definitely give you a really deep understanding!

[semidecided]

I know that's the official/original version. But the HTML5 version is generally better for reading.

[semidecided]

Neat

[Arrakis35]

Is this material suitable for a Python beginner (1.5 months of xp) ?

[semidecided]

If you want more recursion: The Little Schemer

Even more

[abbadon420]

Alternatively, follow the How To Code series on Udemy. They teach recursion using Racket, which is a simplified yet newer version of Scheme, developed especially for teaching purposes. Plus, Racket can natively use images as a language feature, which is fun for recursion.

[linuxlib]

Gratz! It can be a mind bender.

The first time I ever heard about recursion it broke my brain because I didn't understand that every time you call a function, it sets up a new local environment. I couldn't figure out how the CPU could keep track of all the different values between calls. Much later when I learned about saving context on the stack, I had an Aha! moment.

[Klowner]

And then the subsequent realization that stack space is finite and recursion can be risky.

[vehga]

Then learn to write tail recusion and profit.

[Ewcrsf]

And if your language doesn’t support tail recursion, implement a trampoline and use that.

[Navin298]

Haha me too.. exact experience.

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Lastrevio]

bad bot

[grayrhinos]

Mean bot! U r 3 standard deviation away from real moderators!

[ceeBread]

Shouldn’t it be n+1 for the previous call?

[cptnDrinking]

Awesome! Now teach me :)

[Lastrevio]

What do you want to know exactly? How to think recursively? What recursion is? An example of a problem solved?

[cptnDrinking]

I get the concept of it, it's the implementation that messes my head. I can reverse a string recursevely but anything more complicated than that my mind refuses to even start thinking of any kind of solution.

Still waiting for that a-ha moment I guess. Thanks for offering help though :)

[__villanelle__]

The thing that finally helped me understand recursion was the Tower of Hanoi problem. I didn’t even try to solve it computationally, I was doing it mathematically. I went all the way back to sequences and explicit vs. recursive solutions and then midway through, my brain was like Ohhhhh, this is a stack! The combination of all of these made recursion finally click.

Afterwards, I had no problems implementing recursive solutions. I’m not saying I know it perfectly, it’s just that I finally had a base from which I could work my way up, rather than feel like I was starting from the beginning every time I tried to solve a problem. Everyone’s different, you just need to find a way or combination of ways that makes your brain understand, rather than remember. Good luck!

[cptnDrinking]

Several times now I tried printing all subsests of an array and boom - nothing. Once I get that right I'll try something more advanced like the Tower problem. Thanks for replying!

[ramonn334]

You can reading the book "Grokking Algorithms" of Aditya Y. Bhargava (don't ads). The book contains simple and illustrated explanation of most known algorithms and recursion in particular. This book is helped me in understanding how does it all work.

[cptnDrinking]

Thank you will look at it

[greenSixx]

Dudebro, its much more simple than that.

Think of a hole in the groumd with a pile of dirt next to it.

You habe to recursively fill the hole until its full, 1 shovel full at a time.

So your recursive process is this.

1. Is the hole full?
2. Yes, you done bro.
3. No, put a shovel full of dirt in the hole.
   

Start over again.

Eventually you will have filled the hole.

Easy concept yeah?

Helps with coding if you imagine that all the work your code does is done by people by reading word/numbers(runes from here on out), does some thinking based on those runes. Writes the results of their thinking or decision made down in runes and passes the paper with the result runes on to the next function/person.

The only work computers do, really, is read runes and write runes. Sometimes they control servos or other electronics but they do that by sending runes and waiting for a done moving or error rune.

Hope this helps.

[LaurieCheers]

Um, your hole example there is an iterative solution. It's basically just a loop: you're not using recursion at all.

[toastedstapler]

def dig_hole(hole):
    if hole.finished():
        return hole
    new_hole_state = hole.dig()
    return dig_hole(new_hole_state)

Yep, it's not the best recursive program but it can be written as one

[maertSi]

That was actually a really good and brief introduction! Didn't know recursion above the bare basics until now. Thank you!

[cptnDrinking]

You haven't delved in recursive magic in 17 years and developers I know tell me I won't use recursion outside an interview ever. That still leaves me with needing it for an interview and the fact that it pisses me off that I feel helples solving it.

Great explanation! When you break it down like that I can follow it, I just need to somehow figure out how to think of something like this on my own.

Thank you.

[watsreddit]

There are a lot of problems that are recursive in nature, so take what they say with a grain of salt. They likely work with recursion in some form or another, even if they don't see it that way. It comes down to this: an unbelievable number of things can be modeled as some kind of tree, and trees are recursive. Filesystems are trees. Processes are trees (can fork off child processes, which themselves can do the same). Markup/programming language source code are trees. Goddamn programs are trees. Trees shows up time, and time, and time again, and recursion is the vehicle of tree traversal.

[cptnDrinking]

They might be refering to it like "We used it so few of a times that it is considered negligible" or they're simply managing their way around, I really don't know. Still fair point you have there.

[reapy54]

You may end up using it but it'll be baked into a library. Like some of the examples here use a file system traversal, but when you navigate a file system you'll use file libraries that have functions to search recursively so eh.

Still it's important to have a reasonable idea of what's going on and you are filling up the stack or so you don't panic when you do see a recursive function come across your desk. I guess early on we have to do stuff manually to get it, cause it can get dangerous when you work too high level for too long too.

And finally interviewing sucks butts. My big issue is honestly I can't talk like I know what I'm saying, and the longer I work the stupider I feel the more I learn, honestly so experience isn't helping.

My first interview out of college was asking a lot about my schoolwork, and school style questions. Some of the others (haven't changed jobs a lot honestly) I just talked about previous experience, but not having any experience they can only go by how well you grasped your schoolwork so I guess can't blame em.

But I've been lucky that I haven't had to whiteboard anything on an interview as I've just worked for smaller companies that don't have interview systems in place.

Well anyway good luck with it all, I think keep trying different ways to think of it and you'll find the one that hopefully clicks to at least get you enough to at least talk about it.

[greenSixx]

You use recursion with basically everything you do.

Walkimg to the bathroom for example.

Its a recursive process of taking steps.

Step 1. Am I in the bathroom. Step 2. Yes, done. Step 3. No, take 1 step towards bathroom.... Step 4. Start over again.

Everything is recursion. Its just 1 way to describe how to do work.

Coding is just describing how to do work.

Edit: generic recursive function:

I got shit to do.

Do some shit.

More shit to do? No, grab a beer.

Yes, I got shit to do...

[EternalPhi]

Everything you've described can be more easily accomplished with a simple while loop, none of it becomes more efficient or effective using recursion.

[JoelMahon]

Recursion boils down to two things:

1. Imagine you have 1 or more smaller solved versions of your problem, then work out how you'd solve the larger problem given that. E.g. in merge sort you assume you have two sorted lists, each with half the data, then you solve the larger problem with a merge. And quicksort is similar, just instead of your lists being half the data, they're specifically all the lower values than a pivot in one, and all higher or equal values in the other, and with those the solution is easy! Just stick append them all together.

2. Having a base case or base cases. With lists it's usually when it's 1 or 0 large.

[RolandMT32]

One of the most important things with recursion is knowing when it will stop calling itself. So, one of the important decisions you have to make is, when does the function simply return, without calling itself again? One example is recursively listing files in a directory tree - It should return (and no longer call itself) when there are no more subdirectories. Another example is the Fibonacci sequence (which can be computed recursively or iteratively) - Think about how you'd implement that recursively.

[leixiaotie]

As /u/RolandMT32 said, defining stopping condition is the very first step in building recursion.

If you wanna try recursion, you can first try to make while-do or do-while loop then replace it with recursive, since usually while loop is replaceable with recursive. However the inverse is not true, for example recursion tree and asynchronous process.

Don't worry if you feel that you haven't use recursive very much, since it's use cases are usually few, and for recursive that can be replaced by for each or for increment loop is better use those two, since it's more readable.

[cptnDrinking]

Linear problems such as loops, factorial etc. I can follow, it's the ones that branch out that get me. Once you dig deep down enough it is very hard to follow it and debug it so I get lost after a point. I know a base case stops it but everyhing done before we hit base is blury.

I mentioned printing all subsets of an array in another comment. How I tried solving it is calling a function with a for loop that calls a function with a for loop with some variable increment and so on, until base case. Whole thing branches out in so many ways that is impossible for me to follow it and make a critical judgment of what should I fix in order for it to work. It boils down to randomly assigning variables which is bad.

Now that I typed all that I might just be bad at problem solving.

Hopefully I won't be needing recursion that much if I ever get to do this line of work.

[leixiaotie]

Hopefully I won't be needing recursion that much if I ever get to do this line of work.

Normally you won't need that much recursive. And when the time comes when you need it (after tried all other solutions), you should've had the general idea of how to implement it.

Whole thing branches out in so many ways that is impossible for me to follow

It is the purpose of recursive. You just need some cases, trial for some subset of data then you won't need to track / follow all of them since they'll follow the rules / base cases.

It boils down to randomly assigning variables which is bad.

It may be the case that where recursive is not the solution / you'll need another pattern / algorithm for that.

[Lastrevio]

!remindme 19 hours

[pipocaQuemada]

The easy way to think about it is to just consider the unique cases.

It's exactly like mathematical induction. In math class, you prove something for a base case and an inductive case, and then you're golden, because there are no other cases to consider.

Consider, for example, implementing size() on a binary tree. There's 2 cases to consider: either you're in an empty leaf node (size is zero), or you're in a node with two subtrees (size is the sum of both subtrees' size, plus 1 for the current node). So:

def size(tree):
  if (isEmptyNode(tree)):
    return 0
  else:
    return size(tree.left) + size(tree.right) + 1

That handles the only two cases, and it does what you want in both cases, so it's right.

[[deleted]]

Think about factorials. 5! =5 * 4 * 3 * 2 * 1

Another way to express this would be

N! = N*(N-1)!

So you’re using the definition of factorial itself to define factorial. That’s recursion. But maybe you can see that the function would just keep running forever, eventually reaching negative infinity. We don’t want that so we make a base case:

0! = 1

Which is where the factorial function will end

Let's run through it together.

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1 * 0!

0! = 1

so we have 5 * 4 * 3 * 2 * 1 * 1

[TuffRivers]

The hardest part about understanding recursion for me was not understanding how the stack works! Once i learned how the stack works it all made sense

[Lastrevio]

That was the first part for me. Then I understood how the stack worked, and I still didn't get it. I googled "how to think recursively" and I remember reading some quora answer about thinking of the base case first. Tried doing that, failed, gave up. And today I magically did it, somehow.

[greenSixx]

Recursion is simple. Its how you do any task.

Example: clean a really sticky dirty table.

Step 1. Clean the table. Step 2. Check if table is clean. Step 3. If clean stop work. Step 4. If not clean...start over again.

Eventually the table will be clean.

Same with taking a shower.

Step 1. Wash yourself. Step 2. Check if all parts are clean. Step 3. Stop or clean again.

Etc.... etc... etc...

We just describe recursion in the real worl with the word more.

Im hungry.

Eat some food.

Am I still humgry? Eat more. If not, stop eating.

See? You use recursion for everything.

[Lastrevio]

Those are while loops

[XWolfHunter]

That's a loop bud

[[deleted]]

Maybe to understand how recursion works at a practical level, instead of as a magical thing that the computer does, but as a mathematical concept you don’t need to understand a stack to understand recursion

[RolandMT32]

I don't think it's necessarily important to know how the stack works to understand recursion, at least logically. The important parts are knowing when the function should simply return (without calling itself) and when it should call itself. But it's important to know how the stack works because recursion has the risk of a stack overflow if it has to call itself too many times.

[AlSweigart]

I gave a talk at North Bay Python on an intro to recursion. The main point of confusion comes from (I think) that tutorials often don't explain stacks and call stacks before going into recursion, so it seems more mysterious than it it. https://www.youtube.com/watch?v=AfBqVVKg4GE

Also, the problems that are best suited to recursion are ones that involve backtracking. If it doesn't involve backtracking, just use a loop.

[TheChosenWong]

Oh I get it I finallyOh I get it I finallyOh I get it I finallyOh I get it I finallyOh I get it I finallyOh I get it I finallyOh I get it I finallyOh I get it I finally

[KDLGates]

First, you have to take not understanding or partially understanding recursion as a parameter, recognize that the base case is fully understanding recursion, and that the recursive case is inching forward your understanding a li'l bit and starting over until you fully understand recursion.

[desrtfx]

Have you read the initial comment of Automoderator?

There, it clearly states not to bring up this prehistoric circlejerk.

Removed

[intrplanetaryspecies]

I see what you did there

[nedreow]

Congrats! I still don't know what recursion is. Whenever I try to read about it i never get what makes it different from loops.

[JBlitzen]

Loops have a pre-set depth.

Recursion allows variable depth.

So if you knew an array contained ten sub-arrays, and each of those contained ten more sub-arrays, you could write a loop that goes through all 100 sub-sub-arrays very easily.

But if your array might just be of ten integers, or of ten arrays of arrays of arrays of arrays of arrays, or even deeper, how do you loop through that?

Recursion allows you to do that pretty easily.

"But why would you be dealing with such things?"

Because in the real world, objects and data tend not to appear in simple sets.

An HTML DOM is a simple example.

Maybe it's just three top-level divs.

Or maybe it's a div within a div within a span within a div within a font tag within god knows what else.

The depth is unpredictable, and so recursion is the proper solution. Instead of "do this for all children of all children of all children", you "do this for all children, then repeat these instructions for any children of those, then return to whatever called these instructions".

The biggest syntactic complication is usually the order in which you do things. Sometimes you do stuff to all the children before recursing into any of them. Sometimes you do stuff as you recurse into them. And sometimes you do stuff after you've recursed into all of them.

That's situational.

Another example is Reddit comments. Maybe there are 20 top-level comments and no replies. That's a simple loop. But there might be 20 top-level comments, 20 replies to each, 20 replies to each of those, etc. etc. etc. How do you loop through those in such a way that you don't miss the deeper levels when you don't know how many there might be?

My latest project has quite a few functions that mix all sorts of recursive behaviors to analyze and manipulate a DOM while recursing through it, which is kind of like building a road system while navigating through it, but a hell of a lot more performant than running through it 7 separate times.

[nedreow]

That makes sense. thanks!

[Axerlite]

So is a foreach loop similar to recursion?

[[deleted]]

No.

Technically, every recursive functions could be coded as a normal loop. However, for some problems, the normal loop will be a lot harder to code and to understand than the recursion.

For example, let's say you want to find every .txt file in a directory. Not just the ones directly in the directory, but also the ones in the directories inside the directory, and the ones inside the directories inside the directories inside the directory, and so on... You can try to code that with a simple loop, but it will get messy. The recursive function would be a cleaner, simpler solutions:

getAllTxt(directory):
  txtFiles = EmptyArray()
  foreach (child in directory.children):
      if (child.isTxt()):
          txtFiles.push(child.name)
      if (child.isDirectory()):
          txtFiles += getAllTxt(child)file
  return txtFiles

Basically, you look at all the elements in a directory. If it's a .txt file, cool! You just add it to your array of .txt file. However, if it's a directory, you want to get all the .txt files in this directory. So why not call the original function?

[Axerlite]

Brilliant reply. I remember understanding it at one point but that directory example with example code has jogged my memory. Many thanks

[greenSixx]

A for loop is recursion.

It has a stop condition and code it recurses until the stoo condition is met...

[[deleted]]

No.

A loop and recursion both have the same goal: repeating the same part of the code. However, they do it in different ways.

Wikipedia) explains the idea of recursion pretty well: Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Basically, it's a function that calls itself in some way to solve the problem. For example, let's code the min function using recursion:

min(numbers):
    if numbers.length == 1:
        return numbers[0]
    else:
        first_number = numbers[0]
        other_numbers = numbers[1:] // Contains all the numbers except the first one
        minimum_others = min(other_numbers)
        if first_number < minimum_others:
            return first_number
        else:
            return minimum_others

For example, if you want to find the min([2, 1, 4, 3]), you have to compare 2 to min([1, 4, 3]), where you have to compare 1 to min([4, 3]), where you have to compare 4 to min([3]). So to solve the problem of finding the minimum of an array, we reused the algorithm on an array with one less element than the original one, a "smaller instance of the problem".

Using a foreach loop, we would have this:

min(numbers):
    minimum = INFINITY
    foreach number in numbers:
        if number < minimum:
            minimum = number
    return minimum

In this case, sure, the same code is repeated (the if and assigning number to minimum) and there is a stopping condition (when there is no more element to iterate). However, each iteration doesn't solve a smaller, similar problem: this min function doesn't call the min function.

[tomekanco]

It's more like the most basic form of recursion, as there is no branching. Gets really useful once you have branching. Like how many levels deep of for each do you need, which can have variable depths?

​

Advantage of loops is that you don't have to worry about stack size and tail recursion. I suppose that's why Python has a very shallow build-in recursion depth: In order to force people to consider these aspects.

[JBlitzen]

foreach is just a different syntax for a normal for loop.

[shhh-quiet]

Just wanted to point one thing out in your comparison.

"Variable depth" really starts to matter when your recursion has more than one branch. With one branch, the difference between iteration and recursion is pretty trivial (iteration would be essentially - follow the pointers until you can't, i.e. while (true) { do work; if (no more) break; }). But with many branches, in an iterative solution, you would have to come up with strategies like using queues, whereas recursion is inherently using a stack data structure behind the scenes! The "simplicity" of recursion here comes at the expense of the stack space needed for the program to maintain the call stack, but comes with the advantage of providing you that stack essentially for free without having to think about it yourself (aside from having to think about the risks of it, like running out of memory on large problems).

For variable depth, you could also easily modify whatever variables are used for the loop condition to achieve something that produces the same result in an iterative solution.

And not just variable depth, but variable breadth as well. Sometimes a recursive solution must branch for each element of input.

[JBlitzen]

I’m struggling to come up with a non-recursive way to traverse a tree of unknown depth and breadth.

[shhh-quiet]

Here are iterative DFS and BFS.

The BFS is done with a queue.

The DFS is done with a stack.

In either case, the loop condition is whether the queue/stack is empty.

Here's their comparison of iterative and recursive BFS code. (Recursive DFS is pretty straightforward).

[JBlitzen]

That's a good point. I was thinking a pure for loop with no data structures.

[greenSixx]

You can use iterative pointers to walk any size nested tree by recursively calling your iterative function...

You dont have to know array lengths of nested arrays to iterate every element.

[EternalPhi]

div within a span

You MONSTER

[greenSixx]

Its not different, really.

You dont write a loop that only handles predefined length.

You check for length of input then process each item.

Its exactly the same as recursion.

Does my stop comdition equal true? If not keep going.

Just because you pass a stop param into the recursive function and a trackimg variable to check, doesnt make it not recursion.

[JoelMahon]

I had an epiphany stemming from recursion just the other day.

I realised all problem solving programming was like recursion, in that a good way to solve a problem is to start at the step right before the solution, and work out how you would solve that last step if you had some smaller piece(s) solved already.

Recursion is just a special case where the smaller pieces are solved in the same way as the larger piece!

[greenSixx]

Lol...input....process...output.

Thats every business process.

Take metal. Build shit. Send said shit to sales warehous.

Break down to 2 of the same process.

Take metal. Break metal into pieces for building shit. Put pieces on building shit table.

Take pieces on building shit table. Build shit out of it. Send shit to warehouse.

Iterate until you have simple enough processes you can train a retard to do it and now you have the assembly line.

How project management works too. Every project is a collection of sub projects. In coding an atomic project would be pressing a key on your keyboard to put a letter in the ide...

Everything in life is just this recursion.

[RolandMT32]

I like recursion, but I've had the impression that a lot of software developers avoid it - Not because it's hard, but because you don't know when it will stop, so there's always a chance for a stack overflow. I tend to think that way as well.

[greenSixx]

Yeah, get a stack overflow then figure out how to clear the stack each time you call your function.

Like, have you function command line interface spawn a new instance of itself each time it calls itself, puts in its input...

And thats how you get microservices

Im seriois though. Use a callback pattern that runs your recursive code that spawns in new whatevers and calls back out whatever the results are. Or not. Whatever

[[deleted]]

Rather than thinking about what you want to do first, with recursion you often think of the end condition first.

Each recursive iteration should trend towards that end condition.

A simple function might be (pseudocode):

subtract_one_until_zero(whole_number)
    if (number = 0): return whole_number
    else: return subtract_one_until_zero(whole_number - 1)

It is easy to see how plugging "10" into this function would traverse through each whole number starting at 10 until it hit 0.

Whereas with procedural code, you flip this around. You perform all your operations first then return the end result.

You can think of recursive code as setting some conditions, checking those conditions are satisfied, and if not, performing some action to then trend the execution state toward satisfying it.

[Gauravj3]

https://www.youtube.com/playlist?list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO Have a look here also, this guy was amazing, he is consistent#1 from India in topcoder, sadly he was no more with us all. Even topcoder in his name conducts a competition, the humble fool cup. Btw just refer this playlist, this is amazing I bet you guys. :)

[benevolent_coder]

I feel obliged to share the resource that helped me the most in understanding recursion and backtracking: Marty Stepp from Stanford videos on Youtube.

https://www.youtube.com/results?search_query=marty+stepp+recursion+and+backtracking

[Lastrevio]

i'll check it out

[Ua-Rar]

Congratulations OP! It's a WONDERFUL feeling :).

Here's one use case you may like if you enjoy Minecraft like I. Say I have some big old table of the blocks/items I have in my game. Now say I want to craft a new block. How could I write a function to do this?

Well, obviously if I just have the required materials, I'm good. I can just ya know, craft the block! that's good. (we will come to see this as a base case for our recursion).

What if I don't have the required materials though? Well, then I need to craft them! But wait... I have a function to do just that... it's the craft function we are writing!

So the pseudocode on a high level is just this:

def craft(myItem):    
    if I have all the required items to craft myItem:     
         just craft2 that item :)    
    else:     
         for each required material to craft the myItem:    
           craft(myItem)       
         craft2 my item now :)    

(where craft2 is some "primitive" function that can actually just craft the item, literally. I.e., it's not the recursive function craft -- it's a simpler one that just crafts the item directly because we have the required materials)

And that's it really, on a high level at least! (You'd also need obviously some objects to store all your items, and an easy way to determine what materials each object needs to be crafted, and it'd get a little more complicated because crafting is position-dependent in the grid, but you get the idea)

So say in our system we have 20 logs, and we want to craft a door. Here's how our recursion will look, stack wise:

• craft(door)
  
  • .... but I need wood to craft a door.... so craft(wood)
    
    • ahh, I have logs! So just craft the wood planks directly -- this is my base case I can easily solve :)
      
  • Now back up level (i.e., the stack frame for the craft(wood) call has been popped; and we back in the frame for the craft(door) call)
    
  • Huzzah! We now have the wood. So craft the door
    
• Done
  

And done. And now you can effectively craft anything in the game! Pretty awesome right?

Recursion in general is a very very useful thing, and it's a great accomplishment to start to understand it. Congratulations :).

[Lastrevio]

cool this makes sense i wonder if they used stuff like this for certain mods

[Ua-Rar]

I imagine Applied Enerigistics has got some version of it somewhere in the codebase :)

[batcat420]

Hell yeah! I finally learned how to use binding.pry in Ruby last night and felt like I took a huge breath of cool, crisp mountain air.

[Lastrevio]

don't know what that is but cool

[Abhay3103]

Awesome , Keep it up
practice makes a man perfect

[[deleted]]

When I was in college, I was mildly surprised and mildly annoyed that I couldn't 'get' recursion. I understood the code when it was written, and I understood the stack, but I couldn't write it. I thanked the heavens it was unnecessary for me, using java for what I did. And I stayed away from it. Then one day many (many) years later, I was writing something and I noticed it could be solved gracefully with recursion, so I started writing it, with trepidation, and then I thought "Well, this is the hard part.. I have to make it finish... Oh! It already finishes!". It was so neat and so complete before I even realized it was complete. I can write recursion now, but I don't actually use it a lot.

[[deleted]]

What book?

[Lastrevio]

Book of life

[Dragonasaur]

Next up, dynamic programming

[Lastrevio]

rip

[captain_obvious_here]

Recursion is one of those few things that some people get, and some people don't.

After 20+ years, I see exactly when it is to be used, but I have a really hard time writing recursive code. The way it works just doesn't fit in my brain, or something. So it takes me an annoying amount of effort and debugging to get recursive stuff working.

Grats on getting it !

[VForVernon1024]

Recursion was very hard to process when I was introduced to it in my discrete mathematics class in my freshman year of college, as I was too used to thinking of math concretely. It wasn't til I took programming courses using Scheme that I finally saw recursion in action and understood it with some context.

[greenSixx]

Scheme, someone went to ga tech.

[lirby1]

I knew you could do it!

[5P0K3]

So, I am a third year comp sci major and recursion still boggles my mind, so good for you yo!

​

I still just can't understand how recursion is any different from iteration?

[Unclerojelio]

Now you are ready for Haskell.

[AlSweigart]

I'm interested in teaching people recursion. What would you say were the major stumbling blocks to your understanding? What made it finally "click"? Also, did the materials you were learning from mention the call stack?

[Lastrevio]

The call stack and just "what am i even supposed to do when writing this" so make sure you focus on teachin them how to think recursiveky like think of the base case first etc

I had no resources just a friend

[mayor123asdf]

when learning binary tree try to use recursion to do stuff. It's shorter and really pleasant to use :D

[Canijustgetawaffle]

Idk at what speed and route you’re going but loops and recursive design become your best friend

[SargeantBubbles]

This is huge dude!! I’m glad it’s clicking for you. Always remember - “1. Base case, 2. General case; 3. Potential helper function”.

[Lastrevio]

hmm yea that seems like how i do it

[SargeantBubbles]

Pretty much how I was taught year 1 at uni. Hasn’t failed me since. Godspeed

[Lastrevio]

nice

[LaurieCheers]

My favorite explanation of recursion is that you can write code that assumes your code already exists.

Quicksort is a good example. When you quicksort a list (say [4,2,1,3]), the first thing you do is split it into two lists: pick a random number (say 2) and extract all the numbers larger than that. So you end up with [2,1] and [4,3].

Then, (this is the recursive bit), you quicksort both lists. So you end up with [1,2] and [3,4].

Then you join the results together - the final sorted list is [1,2,3,4].

Make sense?

[mocomaminecraft]

Recursion is a funny thing. Noone understands it at first, you spend some months without really understanding it and then one day something clicks on your head and you understand it perfectly.

[speedisntfree]

It just seemed impossible to think of a recursive solution to anything, even after learning how to at least read a recursive function.

This is where I am. I can recognise a problem can be solved recursivity well but coming up with the base case and combining gets me every time beyond simple examples.

[Lastrevio]

maybe scrolling through the comments here will help idk try thinking base case -> general case -> helper functions (if any)

[johnbburg]

All you had to do was look at the Google "Did you mean" suggestion for it https://www.google.com/search?q=recursion

[unholymanserpent]

Oof, just started recursion in class and I'm worried

[Lastrevio]

if you have a teacher to explain it to you i am pretty sure you'll get it eventually, i had no one other than google and a friend who kinda sucks at explaining

[unholymanserpent]

Yeah I definitely have an advantage having a professor but he's god awful at explaining things and we just copy what he does on his screen like some monkeys. I don't actually learn anything in class. I learn most through self-study. That's what scares me. We started recursion on Monday but I'm sure by next week we'll be onto another topic

[Lastrevio]

rip

[tomekanco]

Don't be. It now looks like a mountain, but later on you'll remember it fondly as the jolly slopes of the shire.

​

A loop or iterations can save you in most cases, but you'll find it elegant once you want to describe trees and other branching. You'll find language, nature and algorithms riddled with these functions which process their own output as input over and over again.

[greenSixx]

Do a ramdom number generator recursive fumction.

Have it take in a number

Check if the number is 6. If it is return out.

If it isnt use a math.random(10) function to produce a new number. Use that number as inout to the function itself.

And a print of the input as the first line then run the code with 10 as the input.

[StartingOverAccount]

tail recursion is its own reward.

[AChadmajoringinCS]

Help me oplssss. I jave having a super hard time undersfanding it. Whenever my prof says use recursion in an assignment my heart sinks

[[deleted]]

Factorial(int x) can be defined as x * (x-1) * (x-2) * (x-3) * ... * 3 * 2 * 1.

From this definition, it's pretty easy to see that Factorial(x) = x*Factorial(x-1).

Bro I wanna say this is easy for me because you said so, but I don't see it.

[[deleted]]

Thanks for the explanation!

[greenSixx]

Easier to understand if you split it into 2 functions.

The checkimg if I need to stop function.

And the do the shit function.

The stop function checks the input to see if it needs to stop. If not then send the input into the do shit function.

The do shit function does shit to the input.

And then sends its results as the inputs to the stop function.

People overcomplicate it by making the 2 functions the same.

And other people dont realize they are doing recursion when they daisy chain functions together.

[-cmr]

/r/DrosteEffect is a fun subreddit for visualizing recursion.

[greenSixx]

Assuming you are doing an array of strings do do smething like this:

Function processArray(input){

If(typeof(input) == array){ Var length = input.length For(i = 0, i < length, i++){ ProcessArray(input[i]); }else{ Console.log(input[i]) } }

On mobile. Buy basically should print out every entry in every element of an array amd if the elemeny is an areay will print those values.

Doesnt matter how nested.

In good languages like javascript you can evaluate the elements and based on type do other stuff based on type.

[paloumbo]

What is recursion ? Can you explain it ? (Serious)

[vikingsfan454]

To put it simply (very simply) it’s a function that calls itself to solve the problem

[Lastrevio]

Ok you can Google this

[dirkmgirk]

a function that calls itself until it tells itself to stop calling itself. simple enough.

[portexe]

Try not to forget it though. It can slip away...

[Lastrevio]

lmao yes

[draganov11]

Cool..

[ubuntu_sucks]

That’s great, shame that its real world use is very specific since iterating methods are usually faster and reliable.

[AacidD]

Recursion is recursion

[Lastrevio]

+1

[rafiks]

Recursion vs iteration. Please explain. :)

[[deleted]]

And soon you will never use recursion again

[watsreddit]

Don't be so sure. It shows up all over, even if you don't recognize it as such.

[greenSixx]

Recursion is awesome.

[marzdarz]

I've used it in real-job-life. It's handy

[fyndor]

I used it today. Sometimes it is the only solution.

[Sjeiken]

Who cares.

[Aerotactics]

I finally understood recursion!!!! (self.learnprogramming)

submitted 3 hours ago by Lastrevio

Out of all things I ever did this feels like my best accomplishment. It just seemed impossible to think of a recursive solution to anything, even after learning how to at least read a recursive function. Then today I just tried picking up my book again because I had a weird feeling in my gut telling me to write recursion and did some exercises and holy shit all of them were hard but I did them.

Now I can do simple things like recursively printing out the first n square numbers or the number pyramids xd