Recursion
Published: 2020-12-09 04:10:58

With one small step, you can climb a mountain. 

I'm giving you a seed. This seed will grow you a tree of branches. This tree might have five branches coming up from the ground from where the seed was planted. This tree might grow eighteen branches from the initial seed location. It might be a normal tree and have one branch come up. Is this really even a tree? No time to ask questions just follow along, please. 

For every branch, another infinite number of possible branches could branch from these initial branches. And for these branches more infinite possible amount of branches could be arise from one branch. Here let me draw out maybe how ridiculous this tree might look like. The tree seed is "x".

                         9
                        /
            1 -  x  - 5 - 8
               / | \    \
              2  3  4    7
              |
        10 -  6  - 15 
            / | \ 
          11 12 13

Looks great right? Yeah no this is one ugly tree. I hate these trees. And please note every number here can have more branches, and those branches could have more branches, and so on. The bottom line is this is ridiculous, and trying to navigate this already is giving me a headache. I mean sure if I wanted to get to 9, I just need to go from x to 5 to 9 and boom I am done.

But like I keep stressing, this tree could grow infinitely more and more branching out at each new branch in infinitely new ways.

So let me ask you a question. What if I wanted you to make a whole new tree like this, but take all of these numbers in this tree and double them. Do whatever honestly. Change them in some way. How do you do that? What if you have a ridiculously bigger tree than this? What if you had several different variations of these kinds of trees and you just wanted a single way to get through these trees to make these changes?

Recursion. 

        Tree1              Tree2               Tree3
          x                  x                   x
        / | \              / | \               / | \
       1  2  3            1  2  3             1  2  3  
                          |  |  |            /  / \  \  
                          4  5  6           4   5 6   7

See these trees? Still annoying, but they are a little easier to look at. Premise will still be the same. First step to solving a problem that requires recursion is to simplify the problem however you can and make visuals like this, this will save you brain headaches. I have learned without visual representation my actual solution attempt will have major road blocks and hurdles because your brain can only think of so much at one time and the more complex something is, the harder it is to get your head to think and do the same thing.

Solution time: 

Take notes.
- Tree1 has a seed point and has 3 different branches. But those branches have nothing branching out of them. So it would seem to me that I should take note of that.
- Tree2 has branches with an additional branch for each initial branch. And again, at the end of the newest branches no new branches are there. 
- Tree3 has one of those new branches getting a sibling branch, and has no child branch.

Let's see if we can make this come together now where we can get some new trees with some changed values or something but same structure as the trees were are copying from.

Tree1
If I have a tree with only one set of initial branches, cool just do whatever changes you want on those initial branches and you have yourself a new tree that looks the same but with whatever you wanted changed is now changed.

Tree2
Hey I got child branches on these initial branches? But they don't have children though. So start with the first initial branch apply changes to it, then go through its children and make changes there, come back to the initial branches and do this same process for the 2nd and 3rd branch and their child branches. Kinda like going down and up and down and up and down and up. 

Tree3
Now I have a similar case to where I started where I had 3 children and every branch only had one branch but NOW a branch way down has two branches! Well you solved this problem with Tree1. Iteration. In fact you have solved this iterating so many times so far now.

So we have a thing in programming called a call stack that will remember where you are coming from as you go up and down. It'll remember the place you called a function from, and if you don't have anywhere else to go in that function, you just go back up to that function where you came from.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/0uf01rd9mjkjd43uob0u.png)

So you see myRecurFunc says hey go lets make call stack stuff happen, if where I am has children, I gotta go to each child right away, and same thing for their children, and so on and so on. Where I am though I also gotta change stuff so I have myFunc to do that along the ride! So once I take care of all cases where children are and I reach a point where no children are, I refer back to my call stack to where I came from and check again if children exist! Easy!

Remember this monstrosity? This myRecurFunc can navigate this too! Its amazing! 

                         9
                        /
            1 -  x  - 5 - 8
               / | \    \
              2  3  4    7
              |
        10 -  6  - 15 
            / | \ 
          11 12 13

There you go, an attempt at me trying to explain recursion.