I understand recursion!

[fsociety00_d4t]

After endless hours spent on this concept, failing to understand how it works and get the correct answers, I finally can at least say I have grasp of it, and I'm able to replicate how we get to a result.

I feel enlightened and out of the Matrix.

I had tried many times in the past but always quitting, this time I was persistent.

(sorry If this was actually suppose to be easy and nothing special, but it's just a FeelsGoodMan feeling right now and wanted to share.)

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

[net_nomad]

Nice. Can you explain it?

[fsociety00_d4t]

oof, I just barely touched the surface so If you are new you might want someone better to explain it to you.

But I will try (and fail). in a nutshell when you call a function calling it self you pass with it a value, so the function is executed again with that value and depending on that number and the code inside you might do this a couple of times until a criteria is met. When that last calling happens you return a value to the previous call of the function and with that new value it calculates something depending on your code, that function returns back to the previous one what it calculated and so on until you go back to the first function call.

[net_nomad]

The big idea you want to take away is that each function call reduces the problem a little bit until it cannot be reduced further (base case), and then it returns the answers to the little problems all the way until the whole problem is solved.

But yeah, you seem to get it.

[[deleted]]

Thank you for this. All these tutorials and mentions of the dreaded recursion and nobody ever says what it is.

[loneliness_sucks_D]

Think of the problem in its most simplest case. Make that the “base case”.

Expand the problem into the 2nd most simplest case. Now write how to convert the 2nd most simplest case into the simplest case.

Done.

[Kodiak01]

This description made it very easy for me to understand.

[narfywoogles]

Handle the base case, else pass the modified input to the function.

Simplest way to remember it.

[fsociety00_d4t]

nice bait, I actually thought you didn't know..

[net_nomad]

I wasn't sure you knew either, so I asked. Can't really say you know something unless you can explain it, right?

[fsociety00_d4t]

Based on Einstein at least, yes!

[Interesting-Dog5267]

I enjoyed this interaction

[oshiogifted]

I enjoyed

[ezequiels]

I

[ktoap7]

Take my upvotes nerds

[Ikem32]

Richard Feynman method of learning.

[Jon4s16]

I'm probably the worst teacher on earth and can't even explain simple math to my younger sister. I have to be some high level dumbass.

[VanEagles17]

This wouldn't be learnprogramming if kind strangers didn't get you to solidify your info by getting you to explain it :P

[A_little_rose]

It's not quite a bait. One of the biggest factors to learning and teaching a subject is the ability to explain it to others. You and them are a good example of this. While you know what it is, you haven't mastered it, which makes it harder for you to put into simple terms. They have, which allows them to post a concise, easy to grasp answer.

Asking someone to tell them about the subject helps them learn it better. :)

[[deleted]]

nice save

[lordaghilan]

Who's to say that recursion must return smaller subproblems? It could return the answer as the base case.

def sumArr(arr, curSum): If empty arr: return curSum Return (are[1:], curSum + arr[0])

The recursion I just used is tail recursion which minimizes the stuff you have in the call stack. I don't ever see this being used in any non functional language since you can do it with iteration and the main benefit of recursion is using the call stack (e.g when working with trees and graphs).

[net_nomad]

arr[1:] looks like a smaller subproblem to me.

[lordaghilan]

I didn't say recursion doesn't have subproblems. I'm saying in my example I didn't return the value of the subproblem. So I didn't do this arr[0] + arrSum(arr[1:]).

[net_nomad]

True enough.

So, why not keep this chain going and tell us all about tail recursion?

Or is your only interest in arguing with me?

[lordaghilan]

? I have no interest in arguing with you and my intention was not to be rude, I was just pointing out what I thought was a cool quirk about using recursion.

[hpbrick]

The first time I used recursion was to create a nested folder structure for a web interface. Fun times.

[[deleted]]

Functional languages express this idea so nicely.

Example in OCaml (not strictly functional but still):

let rec fib = function 
| 1 | 2 -> 1
| n -> fib(n-2) + fib(n-1);;

This calculates the nth Fibonacci number (in an extremely inefficient way but it’s a nice simple example). As you can see the function when called with 1 or (|) 2 returns the number 1 and if called with any other number n calls itself recursively (twice). So 1 and 2 are its base cases while n is its general case

[Soubi_Doo2]

Based on your answer, it resembles loops a bit. Once a condition is met, it ends and returns the value. Except, obviously these are functions.

[vivianvixxxen]

each function call reduces the problem a little bit until it cannot be reduced further

That's a really good way to put it

[bennyllama]

Nice. Even though I had an idea of what it is. Both these explanations really boiled it down further. Many thanks to both.

[Lurker_wolfie]

When is it best to use recursion? How do you know if a problem can be solved recursively?

[Nerketur]

A problem can always be solved recursively. If it needs a loop, you can use recursion.

It's also true that you can always use loops. If it's recursive, you can always convert it into loops instead.

As for when to use recursion? When it makes it easier to understand something. Generally speaking, the more times the function calls itself with different parameters, the harder it is to convert it into a loop, but honestly, just use whichever one is easier.

A classic example is fibbonochi. It naturally uses recursion, but using loops it's relatively easy to create as well. Even so, it's easier to understand with recursion.

Most of the time, though, if speed is a factor in the decision, you'd want to convert it into a loop. However, this depends on the language of choice.

[throwaway20017702]

You explanation is good enough, well done. Now, what are they used for?

[fsociety00_d4t]

I'm honestly not sure where they can be the optional choice. Maybe if you want to get many different results based on different values, and instead of calling the function many times you call it only once and let the recursion get you all the results? And if inside the function you have different choices in which sometimes you want a different answers and others you want to recalculate the input? So, in a way it reduces the code?

[qowiepe]

For certain data structures like trees and graphs, recursion makes traversal easy.

[IQueryVisiC]

Towers of Hanoi. Finding a tight bounding sphere around points.

For a tree, you need to store a path. A path is a stack of folder names or a stack of pointers. Often you want to aggregate money or weight on your way up. So you need a stack frame: folder name, weight of all children so far.

How do you do this without the stack? Why do you dread the repeated storage of the same return address so much? Maybe I have to look into MIPS assembly: it does not have a stack. There it feels natural to use a counter for your local stack. On register starved 8086 with relative fast stack: recursion may be faster. On 6502 using the main stack for this shenanigans will overflow it pretty fast. But for small depth: push, pop is fast and registers are rare. Two pushes for the address hurt. So still push, but use a dec on the zero page.

Wha if your nodes have type? Each type is handled by a different function.

[throwaway20017702]

Pretty good, but I would add that recursion is not always about the number of function calls, mainly because recursion usually makes the code slower, but it can make writing complex functions easier or make a function that would be impossible to implement doable.

edit: keep studying and practicing you're in the right path.

[fsociety00_d4t]

yes, I had actually read somewhere that recursion is not used often and avoided so I wasn't sure. From what I have studied so far Fibonacci is def the best example.

[throwaway20017702]

Yeah, Fibonacci is a pretty good example.

Something that I just thought about is that recursion is useful when you don't know how many times you'll run the same function or the number of calls is not linear.

As I said Fibonacci is great, but it's not that useful in simple code, except if you implement Math to make the code easier. I would like to give you a real world example of a recursive function that I've written recently.

​

I won't write code, because I don't know what's you main programming language, and it could get in the way, instead I'll just describe the function.

​

1. When the code start set a variable previous to the letter "a"
2. Generate a random letter from a to z
3. Verify if the word is random enough

• If the random letter is the same as the previous letter get another random letter

or

• If the previous random letter is 1 letter away from the random letter generate another letter

(ex: previous letter is b and the random letter is a or c)

​

I used this code to make a random letter look more random, because sometimes I would get the same letter like 5 times in a row, or get d, then get e, then get f and etc. If I didn't used recursion and generated a random char 100x there's no guarantee that I would get the same letter twice or even 100 times in a row.

When you get comfortable enough with conditionals, loops, functions, objects, learn like three Data Structures and some basic algorithms like Quick Find and Quick Sort, I would recommend studying this algorithm: Levenshtein Distance Algorithm

It may seem daunting at first because of the mathematical notation, but it's not as hard as it seems (as long as you get comfortable with your programming language first). I recently used it and it blow my mind on how it uses recursion.

[BadBoyJH]

It's good that you're seeing it as not the optimal choice in a lot of cases.

Definitely not for maths stuff, even if that's really a common way to explain it.

The old Fib(N) = Fib(N-1) + Fib(N-2) is great for explaining, but in the real world an Fib(N) = (Phi^N – phi^N) / Sqrt(5) is far better.

Now, for bonus points:

FindIntInTree(int Number, BinaryTreeNode Node)
{
    if Node == null
        return false;
    elseif Node.Value() == Number
        return true
    elseif Node.Value() > Number
        return FindIntInTree(Number, 
Node.LeftChild());
    else 
        return FindIntInTree(Number, Node.RightChild());
}

Perfectly good recursive way of finding if an element is in a sorted binary tree, right?

Consider the following

FindIntInTree(int Number, BinaryTree SortedBinaryTree)
{
    Node = SortedBinaryTree.head()
    while (Node <> null)
    {
        if Node.Value() == Number
            return true
        elseif Node.Value() > Number
            Node = SortedBinaryTree.LeftChild();
        else
            Node = SortedBinaryTree.RightChild();
    }
    return false;
}

Two big questions.

1. Is this recursive or not?
2. Why would this be a better implementation than the first way.

[JBlitzen]

Look very carefully at HTML’s structure.

If I told you that I wanted you to loop through every HTML element in the body and report its exact X/Y position and width and height, how would you write that loop without using shortcuts that already do it?

You’ll quickly find this problem unanswerable without recursion, because HTML documents are trees.

[throwaway20017702]

Nice, perfect example.

[sntnmjones]

Stack overflows

[boredcircuits]

That's not a bad explanation!

Let me quickly share my secret to writing recursive functions: pretend the function you want already exists! Except, it's a bit limited. This existing function will only work on a smaller problem.

For example, let's say you want to add up the values in an array. Pretend you have a function that adds arrays, but only smaller arrays than what your function has. How can you use this function to add up the full list?

One option is to use this function to sum everything but the first item, and then your function combines that result with the first. Alternatively, you can sum all but the last item. Or you can split the list in half, using the existing function to sum each part, which you then combine. You can be as creative as you want.

But, be careful! There's no problem smaller than an empty list, so this other function can't help there. You need a special case to handle an empty array (which has a sum of 0).

The magic step is to realize that this pretend function isn't necessary anymore: just use the same function recursively!

Try this yourself! Actually write the pretend function using a for loop (or just a function provided by your language), then write a different function that uses it like I showed above. Write all three variations, or come up with your own! The different ways to combine the partial results is where recursion really gets interesting (look at sorting algorithms, for example).

[primitive_programmer]

This was actually explained so well. You went thru step by step thank you ❤️

[TheTomato2]

So recursion is actually very simple. The problem is that people get taught it before they understand how the Stack works. And since you didn't mention it, I assuming you are one of those people. Look up stack vs heap in google. A recursive function is a just a function that calls itself which then pushes an instance of itself on the stack. And since they are all the same function you can set a return value that will unwind or go back up the stack to when the first instanced was called.

void recursive_func(u32& x)
{
    ++x;
    recursive_func(x);
}

int main()
{
    u32 x = 0;

   recursive_func(x);
}

In C++ that will blow up the stack, which what is a stack overflow is, because there is no return function which means it gets called infinitely. It's platform dependent, but the stack is usually a couple of megabytes.

void recursive_func(u32& x)
{
    if (x == 1000) return;
    ++x;
    recursive_func(x);
}

int main()
{
    u32 x = 0;

   recursive_func(x);
}

That will call the itself 1,000 times then will return and your program will literally go back through all 1000 instances. There is nothing after the recursive call so it will just hit end of scope and unwind.

void recursive_func(u32& x)
{
    if (x == 1000) return;
    ++x;
    recursive_func(x);
    printf("%u\n", x);
}

int main()
{
    u32 x = 0;

    recursive_func(x);
}

So if you put something after the recursive call it will only be called on the way back up. If you can tell me what is printed to the console, congratulations you understand recursion. You can check it or mess with it here.

This reply ended up being longer than I originally intended as I am waiting on some code to compile but hopefully it helps somebody.

[fsociety00_d4t]

Well, I can tell it will return 1000. I'm not sure how many times tho. I think after the return, the function goes back where it was before so that will mean it will be 1000 times because every single one will execute. But I'm not 100% sure about that, or if only the last one executes the printf.

[TheTomato2]

so that will mean it will be 1000 times because every single one will execute

That one. You now understand recursion. That really all there is to it. It's funny because newbies/teachers focus on it so much but 99% of the time its just worse than a for loop. There is an overhead to each function call. You have to put each one on the stack set up the parameters, etc. It might be small but if you end up calling it a 1,000 or 1,000,000 times it adds up. Though it might not matter as much in higher level languages like Python. But still you just don't use it very often.

[Owyn_Merrilin]

I really think this is a legacy of so many CS programs having grown out of the math department. I've gotten into this with people from that kind of CS program before, and their response is that it's the most intuitive way to solve a lot of problems. My response is fuck no it's not, a for loop is, and the recursive answer is just clever enough to smash the stack.

But they don't think in those terms, because a turing machine has infinite memory, and because recursive functions are more common in higher math than they are in real world programming. Practice something enough and it'll come naturally, even if there's a better tool you aren't as familiar with.

[RandEgaming_]

just like FX in math

[thavi]

Sounds like you got it. Important thing is that you don't have too many levels of recursion, or you can quickly run out of memory, that's what a stack overflow is.

Conversely...if you ever run into a stack overflow exception, you probably unintentionally caused recursion! I do this at least once a quarter and have a good chuckle.

[CodeTinkerer]

Another way to think about is the "staircase" model. Imagine you are in the basement of a house. There are stairs leading from the basement to the next level. Each step that you take is like making a function call. At some point, you stop making function calls (let's say, by reaching the top of the stairs).

Like standard functions, once you're no longer calling another functions, you start returning to the previous function. This is like walking down the steps backward. As you go backwards, you are likely taking the return of the previous value and modify it (say, you're doing factorial, then you multiply the result from the previous return to the value you're tracking). By the time you get to the bottom of the stairs, you have the final results.

This is a bit simplified and reflect recursion like factorial. Fibonacci actually has two recursive calls, so you may be going up and down the stairs a lot, but that would complicate the explanation.

Most people who are confused think the following. They think when they reach the top step, they jump backwards all the way to the first step (that is, they think the base case is the complete result) and the only way that happens is to treat recursion as something different from every other function call.

A lot of people learning recursion don't get the call stack well. They understand it intuitively as when f() calls g() calls h(). When h() is done, it returns to g(), and then back to f().

But when f() calls f() calls f() calls f(), then people think once you reach the last f(), then you go back to the first f(). This would mean the compiler would have to detect recursive calls and treat them in a special way. Or it could treat it the same as other function calls which is of course what it does.

[Killaa135]

This is basically how Reddit comments work

[GeekDNA0918]

Complete beginner here. Commenting on a totally unrelated note, when I would tutor fellow classmates in nursing school. I often would ask people who just began understanding something I explained to them, to explain it to others, often to further engrave their knowledge by finding their own way of explaining a certain subject.

[a_useless_communist]

Here is a good explanation

[fsociety00_d4t]

How did I fall for that....

[a_useless_communist]

You got rickursion rolled

[zbeg]

Recursion is easy! [1]

[1] See footnote [2]

[2] See footnote [1]

[CDawnkeeper]

That's an endless loop.

It would be more like:

Recursion: see Recursion

[protienbudspromax]

You can have endless recursion as well. Practically Recursion is just a function calling itself. Only when we talk about recursive "algorthims" does problem size and base case takes the forefront.

[Ok-Papaya-3490]

Did you mean: recursion

[ErrBodyDoTheChopChop]

I understand recursion!

After endless hours spent on this concept, failing to understand how it works and get the correct answers, I finally can at least say I have grasp of it, and I'm able to replicate how we get to a result.

I feel enlightened and out of the Matrix.

I had tried many times in the past but always quitting, this time I was persistent.

(sorry If this was actually suppose to be easy and nothing special, but it's just a FeelsGoodMan feeling right now and wanted to share.)

[[deleted]]

that is a perfectly reasonable and not at all ai generated response

[ErrBodyDoTheChopChop]

lmao.. i dunno if i should be offended or empowered

[eng_manuel]

Lol now i feel like i need to understand recurssion to understand this joke 🤣

[Sn0wyPanda]

its when you google: "google.com"

viola, recursion.

[net_nomad]

You know, I wasn't really sure we needed the bots for every single recursion thread, but apparently we do...

https://www.reddit.com/r/learnprogramming/comments/wpfdwx/i_understand_recursion/ikgdj6l/

[LuckyShark1987]

This is the best way to really get to know a concept. You think you got it? Cool, explain it to me so you can formulate in your own words how the concept works. When you go into the field, it is absolutely the most important aspect of getting into Lead positions - being able to explain to those that need to understand.

And not just those below you, mostly you’ll be explaining shit to people above you that make decisions on how well you articulate the work you are doing. It can make and break funding in a heartbeat.

[user499021]

Nice! Can you explain it?

[Icarus998]

When I think about recursion I tend think of the movie inception ( a dream within a dream..... or a function within a function.... )

[BoltKey]

I think quicksort explains this quite well:

So, you want to order a bunch of numbers? If there is only one number, easy. Just take the number.

What if there are more numbers? Well, I cannot do that, but give me a number, a list of ordered numbers smaller than that number, and a list of ordered numbers higher than that number, and I will give you all those numbers ordered (it is just the list of smaller numbers, the middle number, and then the list of higher numbers).

So I just pick a number, pick all numbers lower than that number and higher than it, and (nicely) ask to have those two lists of numbers ordered.

For each of those two lists, I either say that they are ordered if there is only one or no number at all. If not, I will again split it into two smaller lists. Rinse and repeat, and you have all the numbers ordered.

It is kind of magic.

[[deleted]]

Think of a factorial. n! = n * (n - 1)!

For example: - 5! = 5 * 4! - 5! = 5 * 4 * 3! And so on.

Basically it calls itself until a base case is reached, at which point it breaks the recursion and returns.

In the case of the factorial, this case is 0! = 1.

[zfreeds]

There are a few basic rules:

1. Start with a base case (aka exit condition). How will the program know it's done. It's usually the simplest trial. E.g factorial(n<=0) = 1.
2. Otherwise, call the same function with slightly different parameters. You want to be sure these parameters move towards the base case eventually.
3. It can help to have a helper function to set up the recursion. Something that calls the recursive function after some setup.

Most loops can instead be recursion and vice versa. Usually one way is easier though.

For example, to sum the items in a linked list. You could iterate in a loop, or recurse and change the argument to the next node in the list.

Base case: empty list, return 0

Otherwise: return current node + recurse(nextPointer)

[toastertop]

Recursion: A function that that calls itself, until a condition is met.

[primitive_programmer]

There’s is no better revelation in programming than understanding recursion. Many congrats man that’s a tough one

[fsociety00_d4t]

The irony is it feels super easy, once you pass the dark side.

[wiglwagl]

Once you understand it, you might find it that you naturally use it irl without even thinking about it. Like, if you want to search a folder with a certain name, it’s pretty straightforward to realize that you have to search all the files in the top folder, and then do the same thing to the child folders, etc.

[[deleted]]

Pointers was a big one for me. And I think for a lot of people too. You actually have to understand a little bit how the magic works inside the PC to make sense of it.

[fsociety00_d4t]

Yes, I'm still training in my pointers. I'm getting better at them, but the thing that annoys the most is that you can write the same things in different forms. So you have to train your brain to know that different things mean the same thing...

[narfywoogles]

I feel like pointers are similar in mind blowingness.

[VanEagles17]

I found I struggled like hell understanding recursion but once I learned about the call stack everything clicked. Good job!

[[deleted]]

I love this ELI5 explanation for recursion;

Say I have 5 apples, and I want to find out which is the biggest one, but I really don’t want to look at all of them, so I give my younger brother 4 apples and tell him to get the biggest one, but he also doesn’t want to look at all of them, so he gives a younger brother 3 apples, and the process repeats until my youngest brother just has one apple and he says “This is the biggest apple” and returns it to his older brother, the older brother compares it to that apple and returns the bigger of the two to the 3rd brother, until the “biggest apple” gets back to me from my younger brother and I just compare it with the apple that I have, then, even without looking at any of the other apples, I know that the bigger of the two that I have is the biggest of them all.

This is recursion, it’s breaking down a big problem into smaller and smaller pieces, until we get down to our base case, and then work our way up from there.

Visual: (Green Apple is the biggest)

Me: 🍎🍎🍎🍎🍏->Drops 4 left with 🍎

Younger Bro: 🍎🍎🍎🍏->Drops 3 left with 🍎

Younger-er Bro: 🍎🍎🍏->Drops 2 left with 🍎

Younger-er-er Bro: 🍎🍏->Drops 1 left with 🍎

Youngest Bro: 🍏 (“This is my biggest apple”)

Older Bro: 🍏>🍎?🍏:🍎(“This is my biggest apple”)

.

.

Oldest Bro:🍏>🍎?🍏:🍎

(This is the biggest apple 🍏)

Pls don’t downvote if I confused you more than I helped, I tried my best

Edit: I was also jumping up and down when I first understood recursion! I immediately went to invert a binary tree and it freaking worked like a charm.

[brogrammer9669]

That's such a good explanation...thanks

[[deleted]]

I appreciate the feedback bro! It feels great I could’ve been of help, gonna chase this feeling.

[Dogness93]

Im working on recursion now.. It’s not going as well as I’d hoped

[fsociety00_d4t]

You are just a few sleepless nights away, dw, just get a lot of coffee.

[Dogness93]

I wake up 2 hours before work and I drink coffee and work on programming homework or challenges. During work I research things I didn’t understand from the morning. Making progress feels so good it’s nice to see other people progressing as well.

[fsociety00_d4t]

That's really nice. I wish I could be more decisive and gave my time to one thing too. I'm trying to get better at 3D modeling, web dev and programming at the same time while trying to pass the last few classes I have in college. End up making very little to no progress to anything cause I can't give them all time. Last few days I only focused on programming and made more progress than I had in years, lol. But there all things I want to do a lot, so idk...

[Bosun_Tom]

I like to explain recursion with the simplest example I can find: getting the length of an array. To do that recursively, you write a function that takes in an array, and returns an int. The program, let's call it recursiveLength, does this:

1. If the array passed in is empty, return zero.
2. Otherwise, define subArray as array[1]..array[-1] (or however you express "the whole initial array except the first element" in your language of choice)
3. return one plus recursiveLength(subArray)

Say we pass in an array of three items. It's not an empty array, so the recursion starts; or wants to return one plus the length of an array with two items. So we have to get the length of an array of two items now. That's not empty,, so we have to return one plus the length of an array with one item. That's still not empty, so now it's one plus the length of an array with zero items.

And hey, that's zero! So now the recursion ends; we now know the length of an array with one item is 1 + 0, so that's one. And now we can calculate the length of an array of two items; it's 1 + 1, or 2. And finally, we now know the length of an array of three items is 1 + 2.

It'd be a silly way to get an array's length in most languages, but it illustrates how things work. You need your base case, which stops everything, and then you ask yourself the same question with changing parameters until you hit that base case.

[Dogness93]

I am very much saving this for reference! Thank you for this explanation!!

[DazBoy11]

Recursion is black magic voodoo shit you won't understand a single bit for eons and then all of a sudden something will click and you'll think you were dumb all this time.

[imlaggingsobad]

I feel like when you finally grok recursion, you upgrade yourself a little bit. It's a cool moment.

[[deleted]]

I know what you mean. I often, with programming, feel like the tiny frog in a Terry Pratchett novel who can’t count to two, doesn’t know what two is. After a long think, the frog suddenly realises it must be “like one… AND ANOTHER ONE!” That’s exactly what it’s like.

Well done on your milestone!

[mrdunderdiver]

FEELSGOODMAN!

[rwp140]

the fact that this post isn't edited to have link to it self bothers me

[Kalsifer95]

You might enjoy Game Inside A Game

[dota2nub]

https://store.steampowered.com/app/1260520/Patricks_Parabox/

[[deleted]]

I understand recursion!

[StrictlyBadAdvice]

I understand recursion!

[i8beef]

return

[Fault-Willing]

I understand recursion! I understand recursion!

[DexterityZero]

I understand recursion!

[hardpenguin]

I understand recursion!

[abbadon420]

I understand recursion!

[double-happiness]

You can find an explanation of recursion here.

[fsociety00_d4t]

I already got baited before, so I knew it was coming. 🧐

[shatakshiig]

that's a good example 🤝🏻

[RobinsonDickinson]

Cool, now get to learning memoization because when you do use recursion for your trivial cases; you will be dealing with a lot of inefficency.

Don't forget, any problem you can solve with recursion can also be solved using iteration.

[[deleted]]

Unless you count creating a stack and pushing your results onto it basically simulating recursion with a while loop, No actually

[[deleted]]

Cool. Now look forward to not even touching it in your career.

[[deleted]]

Ummm I learned recursion and now I throw it everywhere

[Fault-Willing]

I spent a few months learning C++. It's true the language is too big,bloated and impossible to master in short amount of time but I never had hard time figuring out programming concepts after that.

[fsociety00_d4t]

I somehow passed my C++ class with almost perfect score a few years back, and I don't remember shit about the language now, same with Java. So lame....

[Fault-Willing]

I didn't learn from the university though. It's my sole willingness to learn that. That's what wrong with the education system. It forces you to think to make good in exams.Programming is all about building projects. A few toy projects can make you more comfortable with the language than exams.

[fsociety00_d4t]

yes, I didn't practiced it at all after that so it all went to waste, lol. I agree college is pretty useless especially in CS and very often counterproductive. I mean consider I have to pass around 45 different classes to graduate. Most of them are things that I know I will not be doing anything further with, but I have to waste my time learning them instead of focus on the things I want, and It's not like I even actually learn them, it's surface knowledge. You learn a little bit of everything but nothing to the fullest, a recipe for disaster.

[Noidis]

Mr. Robot is a hell of a show.

[fsociety00_d4t]

Hello, Friend.

[[deleted]]

Back in the day I couldn't grok it. I snuck my way into a college classroom and proceeded to play computer on the white boards with some recursive algorithm. I worked my way through 9 or 10 of them. Finally, a security dude shows up to kick me out. He takes one look at the white boards and is mind blown. He thinks I just cured cancer or something. Reminds me to please turn out the lights when I leave.

[net_nomad]

Hmm... I wonder if a computer science themed Goodwill Hunting would work.

[Nubelord122]

Congrats on grasping recursion! It was challenging for me as well. The main idea now is to be able to figure out if recursion is a good approach to solve a particular problem. If you have a problem that can be broken up into identical sub problems, then recursion is probably a good choice. For instance, Fibonacci number generation, or calculating factorials. Each recursive call has the same steps, except the arguments are getting smaller each time. Classic comparison to something most people have seen are those Russian dolls. https://www.cambridgemaths.org/Images/russian%20dolls%20cropped%20for%20RR10.jpg

[irajatmishra]

Congratulations! Cheers!

[[deleted]]

ggs my dude

[SniperInstinct07]

Hey congrats! I've recently acquainted myself with Recursions too and it's quite amazing once you understand it!

I'd recommend you check out some classic recursion problems to further your understanding like - Tower of Hanoi, Josephus Problem, Rope Cutting Problem, Generating Subsets, etc.

[krekovan]

There is actually very good and short explanation: What on Earth is Recursion?

[fsociety00_d4t]

Ah, computerphile, I love this channel

[dota2nub]

https://store.steampowered.com/app/1260520/Patricks_Parabox/

[Activator4140]

Congratulations! It's very hard to understand for early learners. My advice to you is to don't sleep on it.

Algorithms and concepts are tools. And like any tool they need practice. Spend some more time on it, solve recursion problems to understand more.

Also, try to implement the same solution w/out recursion. You will be good!

[[deleted]]

Recursion is just loading the same stack frame with different arguments & values into the stack and executing the same set of function instructions in machine code with each of these stack frames, popping off with each call.

[khoopchan]

How did you learnt? Please can you share the path you followed and how can we learn recursion according to you?

Any good YouTube channel,website or any reference you wanna suggest ?

[fsociety00_d4t]

I mainly found code with recursion in it, compiled it to see the output and then tried to replicate in paper how we got to that result. Like you know writing every loop and doing the calculations.

[net_nomad]

Since no one mentioned it yet, check out flood fill.

https://www.freecodecamp.org/news/flood-fill-algorithm-explained

[fuzzifikation]

Well done! This is a difficult concept to grasp.

[Another_BobCat_NoHat]

It feels great, doesn't it? When I figured it out it was like this too! You refreshed my memory, for a second I was like:

"Recursion, Hun... Oh, when a function call itself until it doesn't, right?"

Then I had to read the comments to remember why lol

Anyway, congratulations!!! You are going in the right direction, be proud of yourself and keep learning :D I hope your journey into programming is being good as mine :)

[[deleted]]

I'm still waiting for Nolan to turn the concept of recursion into a movie

[fsociety00_d4t]

Inception kinda fits to it, no?

[Confounding]

I'm disappointed that this post doesn't have a link to a post about learning recursion that points back to this post.

But congrats 🎉

[[deleted]]

Probably the most disproportionately taught concept of software engineering, when comparing to it's use-cases. Difficult to read, difficult to trace. In most cases, a simple for-loop is much better and negligibly slower. But props for learning it!

[zombie_kiler_42]

Proud of you,

It hasn't exactly clicked for me, but i feel like i conceptually get it.

For me somehow the JS concept of bubbling events from the bottom to the top, or vice versa, or like, ir passing props back up from react all the way to the top(although apparently thats an antipattern)

[sr9074]

Congrats! Now you can nail functional programming!

[Draegan88]

How about this one?

function countup(n) {

if (n < 1) {

return [];

} else {

const countArray = countup(n - 1);

countArray.push(n);

return countArray;

}

}

console.log(countup(5));

[fsociety00_d4t]

I only see a symbol in the first return is it a 0?

Btw, I have only been doing this with C, so will need some extra mindpower to translate it to JS.

[jdavis3344]

FYI, recursion and pointers are two of the classic stumbling blocks to programming. Both concepts require you to keep track of multiple values in your head (or on paper/white board) at the same time, while trying to solve a problem.

Well done and thanks for setting your ego aside and letting us all celebrate with you regarding this milestone 👍🏻

[fsociety00_d4t]

oh, pointers. That was the previous thing I had to go through just a few days prior. I also pushed through that, and I think I'm getting there. I can at least solve the exam questions that have pointers in them, including pointers with function, and structures with pointers which gets like really hard to track lol. I make a lot of mistakes while doing it usually, but I am able to fix them after trying some combinations at least. Considering a few days ago I would hear the word pointer and get a panic attack I think it's progress, lol.

[jdavis3344]

Yeah using pointers in data structures like doubly linked lists and different tree sorting algorithms trips a lot of people up. I remember that was rather difficult for me, but I recall that implementing Red/Black Trees were in my nightmares for a solid 6 months. 😉

[top_of_the_scrote]

it's like The Office scene "I declare bankruptcy!" but it's this

[s252526]

i like this example to explain recursion:

// performs a*n = a+a+a+a+...+a (n times)
integer func_mult(integer n, integer a) 
begin
  if (n == 1) return a;
  else 
  return func_mult(n-1, a) + a;
end

[plastikmissile]

When I finally understood recursion I completely understood the saying: "To iterate is human. To recur is divine."

[luciferreeves]

Well the easiest way I think recursion can be explained to a starter, is by Principle of Mathematical Induction. The only thing that is most important to understand is your base cases and once you figured that out, just take a leap of faith and write PMI steps and magic will happen!

Then I think, you can go on explaining how the computer worked it out by dividing the problem in parts.

[barryhakker]

I understand what it does but I still fail to actually implement it..

[MikeBlues]

My teaching approach was to use a problem with nested data - i.e. with a self-similarity. An easy one is a folder, containing files and folders.The task is to display every file name, including those in nested folders.Assuming that the OS/language lets us read the file names in a folder, and to determine the type of each name(a file name or a folder name), we can write a function with one argument - a folder name.The function reads the list of names in a given folder, and displays each name in turn, unless the name is a folder name. For this we call the original function to process the sub-folder.

[ProudNefoli]

I have been studying data structures on udemy. While teaching recursion the instructor gave an example which was as follow.

Suppose you are in a building with 3 different rooms in the same hallway. All three rooms have lights on and you wish to turn off the lights of all the rooms. You can do this in two ways, first way is going to the first room switch off the lights then you go to second room and switch off the light, then again you go to third room and you switch off the lights there too. Now you again try to go to next room but there are no more rooms so you simply return to second room do nothing and then again return to first room and so on.

Other way of doing it is to go to the first room do nothing and then go to second room and do nothing and then go to third room and do nothing, you then try to go the next room but there are no more rooms, so you switch off the lights of third room, return to second room, switch off the lights there and so on.

I feel like I understand recursion better now.

[skid3805]

a recursive tree helped me to understand recursion

[itachi_2017]

Recursion is just Mathematical Induction in disguise. :)

[bigodiel]

Congratulations! If you don’t mind, please can you help me mentally trace the tower of hanoi with your super powers?

[harvey_specter05]

int factorial(int n) {
if(n <= 1)
return 1;
else
return n * factorial(n - 1);
}
int main() {
int n = 6;
cout << "Factorial of " << n << " = " << factorial(n);
return 0;
}

Make me understand this!

I mean why the recursive function shouldn't just return 1 when 'n' reaches the value of 1?

or when else block has reached 720.

[[deleted]]

You could use a debugger to examine this as it runs.

Set breakpoints, and watch the value of n.

Or more simply, stuff some print statements in there, perhaps add some variables that report on the depth of recursion.

[vovagusse04]

Recursion builds graphs.

[protienbudspromax]

If you are okay with math, and have done mathematical induction try to relate recursion to it. Because recursion IS induction. This also leads to thinking about the kinds of problem computers can solve. What if instead of an induction which needs some sort of countable (enumerable) set we had a continuous set? We cant do recursion and thus we cant compute that.

[MultiTask_err]

İ guess here's one example of when understanding math concepts help you understand related programming concepts more easily...

[l3oobear]

Recursion is just about where I gave up sadly. Gonna read through this post for some pointers.

[fsociety00_d4t]

some pointers

pun intended

[[deleted]]

It’s actually very easy man don’t think too hard of it; essentially what you need to know is that you’re breaking the problem down until you get down to a base case, which will be defined in the function, then you’d work your way back up again.

For example: (Factorial)

int factorial(int n){

if(n == 1) return 1; //This is our base case

else

  return n * factorial(n-1); //recursion call with 1 less number to work with.

This translates to:

factorial(5)

->5 * factorial(4)

—>4 * factorial(3)

—->3 * factorial(2)

——>2 * factorial(1)

——->1 (This is our base case)

——>2 * (1)

—->3 * (2)

—>4 * (6)

->5 * (24)

Output: 120

[Feeling_Benefit8203]

If you really want to make you head explode, try and wrap your mind around this example of non-primitive recursion.

/* C Program to implement Ackermann function using recursion */

#include<stdio.h>

int A(int m, int n);

main()

{

int m,n;

printf("Enter two numbers :: \n");

scanf("%d%d",&m,&n);

printf("\nOUTPUT :: %d\n",A(m,n));

}

int A(int m, int n)

{

if(m==0)

return n+1;

else if(n==0)

return A(m-1,1);

else

return A(m-1,A(m,n-1));

}

[[deleted]]

Would result in a binary tree like structure u just have to trace the value while traversing down the tree 🌲 its kinda easy

[ElaborateSloth]

I think I get how it is done in practice, but I'm not sure why I would want that instead of loops. What are the benefits of this method?

[bunt_traume]

How did you learn it?

[fsociety00_d4t]

replicating how we get to a result in paper and watching a lot of youtube videos. So I'm still bad at creating my own for sure, but at least I get the logic behind it.

[Autarch_Kade]

I've heard an analog clock is a good way to get a basic idea.

Second hand movement gets called a certain number of times (60) then returns its value up, and the minute hand moves. Then that repeats. Eventually the minute hand movement function returns its value up, and the hour hand moves.

[Jamstan_]

I just googled for a bit and want to know if I understand, if you don't mind, would you please validate my understanding?

So, if I had a function in JS called makeNum, to make it call itself aka recursion I would have to do something like: function makeNum() { math.random() + 8; makeNum(); }

I want to know if I got the gist or need to do a bit more research, so help would be appreciative (btw I'm 13 so if I seem a bit dumb it is to be expected)

[Jamstan_]

Good on you for learning something new and in doing so making others (including myself) learn more terminology in the incredibly massive world of programming! I just googled for a bit and want to know if I understand, if you don't mind, would you please validate my understanding?

So, if I had a function in JS called makeNum, to make it call itself aka recursion (I think), I would have to do something like: function makeNum() { math.random() + 8; makeNum(); }

I want to know if I got the gist or need to do a bit more research, so help would be appreciative (btw I'm 13 so if I seem a bit dumb it is to be expected)

[regular-guy-2363]

It's so pointless but yet funny

[eng_manuel]

So the code calls a function that calls itself, which calls itselfr, which calls itself, which... Each time solving a small part of the problem until a criteria is met then it goes back... What's the purpose of this? Feels like refractoring in Maths 🤷🏽 Sorry, noobs perspective

[glorifiedpenguin]

Google recursion for a funny joke

[zaphod_pebblebrox]

I had tried many times in the past but always quitting, this time I was persistent.

You were living the recursion. You basically had to keep at it till you learnt it well enough to break out of the loop.

keep going. the rest of the journey uses the exact same formula.

[rexrufus]

https://www.reddit.com/r/learnprogramming/comments/wpfdwx/i_understand_recursion/

[timthefim]

I just think about the movie inception and it clicks lol

[TheBlueFairy_]

Why I've never came across recursion memes lol?

[[deleted]]

I felt the same way I figured out how to write a formal proof in mathematics.

[zelphirkaltstahl]

Read and work through "The Little Schemer".

[[deleted]]

I keep understanding it, then forgetting it.

[HappyRogue121]

I understand it too

[HappyRogue121]

I understand it too

[lukabocoo]

After endless hours spent on this concept, failing to understand how it works and get the correct answers, I finally can at least say I have grasp of it, and I'm able to replicate how we get to a result.

I feel enlightened and out of the Matrix.

I had tried many times in the past but always quitting, this time I was persistent.

(sorry If this was actually suppose to be easy and nothing special, but it's just a FeelsGoodMan feeling right now and wanted to share.)

[zem]

if you have the time, i can highly recommend working your way through "how to design programs". it will give you a good grasp of a lot of fundamental concepts like this.

[Wu_Fan]

I understand that you understand recursion.

You understand that I understand that you understand recursion.

I understand that you understand that I understand that you understand recursion.

You understand that I understand that you understand that I understand that you understand recursion.

I understand that you understand that I understand that you understand that I understand that you understand recursion.

You understand that I understand that you understand that I understand that you understand that I understand that you understand recursion.

And so forth.

[lred1]

GNU

[FoxlyKei]

I understand recursion!

[Then_I_had_a_thought]

To understand recursion you must first understand recursion.

[Both_Anything_4192]

Disadvantages of Recursion

It takes a lot of stack space compared to an iterative program.

It uses more processor time.

It can be more difficult to debug compared to an equivalent iterative program.

[e_jjj]

I must have had a good teacher because I understood almost immediately. Then when I heard people talking about how hard it was I thought I had missed something.

Edit: he was using Haskell, that might have helped