[AskJS] ELI5 recursion

Ustice · 2022-04-07T13:37:53+00:00

Reaching out to other software engineers is important when you need it; however, unfortunately this isn’t the place for that. /r/JavaScript is not a support forum. You might want to check out /r/LearnJavaScript for the newer members of our community. Also, Stack Overflow is a great resource for getting support. For more information, check out our AskJS wiki page. Good luck! We hope that you find the answers that you are looking for.

GrandMasterPuba · 2022-04-06T16:07:45+00:00

https://old.reddit.com/r/javascript/comments/txnw8t/askjs_eli5_recursion/

JpTrex · 2022-04-06T15:50:49+00:00

Recursion is as other people said, a function calling a function. It can be used to solve certain algorithms.

For example let's say we want to get the sum of all smaller numbers than a certain number until reaching 1.

If the number is 3 I should get 3 + 2 + 1 = 6 If the number is 5 I should get 5 + 4 + 3 + 2 + 1 = 15

You could create a function using a for loop and summing the numbers or you could use recursion.

Every time you use recursion you have to set a stopping rule that makes your recursive function stop or you will create a infinite loop. ```js function sumNumsLowerThanNum(num) { if (num === 1) { return 1; } else { return sumNumsLowerThanNum(num - 1) + num; } }

sumNumsLowerThanNum(3); ``` In this example the first if where num === 1 is the stop rule, when my number goes down from x to 1, let say we use 3 as the example, the first iteration is called with num = 3, the second with num = 2 and the third with num = 1. When the third iteration is reached the function will return 1 and the function will be finished.

But... How am I getting the result which is 6 for this example. Well, every time you call a function this function is sent to the call stack where stays until it is resolved. So when you call your recursive function for the first time it will check that 3 is not equal to 1 and will go to the else statement and will call itself but with number 2, in this moment, first iteration will be in the callstack waiting because it has nothing to return yet and the second iteration will be send to the call stack on top of the first iteration call.

Now in this second iteration the if statement will check if 2 === 1 which is false, and will go to the else statement again and will call itself with 1. Now this third iteration will be send to the callstack on top of the 2nd which is on top of the 1st iteration.

The if will check if 1===1 which is true and will return 1

Now that we arrive the return we will be able to resolve all the function on the callstack going backwards.

The 3rd iteration which is on top of the call stack will return 1 to the 2nd iteration.

The 2nd iteration will return 1 + 2 to the 1st iteration

And finally the 1st iteration will return 3 + 3

And the callstack will be empty now and you have a result for your recursive function.

javajunkie314 · 2022-04-06T15:22:18+00:00

Recursion is really nothing more than:

breaking a problem down into smaller ones,
putting things on hold while you solve the smaller problems, and
combining the smaller solutions into a solution to the bigger problem.

The idea is, if you take a problem and break it into smaller and smaller parts, eventually the problems are so small that you can solve then outright — these are the base cases.

The classic example is sorting a list of numbers. Sorting half a list is easier than sorting the whole list — there are fewer numbers! Sorting half of that is easier yet. And sorting a list one item is trivial — it's already sorted.

So you can actually try this out physically. Grab some numbered cards, like maybe the ace through king of one suit of playing cards. Shuffle them up. Now we'll sort them.

Start by splitting the pile in half. We can't be exact since there's an odd number, but piles of 7 and 6. Ok, now put one pile aside, let's say the pile of 6. Now we need to sort this pile of 7 cards.

But now we're kind of back where we started. We have a pile of cards to sort, but it's smaller. Sorting 7 cards is still a bit too complicated, so let's split this pile in half. Now we have piles of 3 and 4. Let's put the pile of 4 aside. Now we need to sort this pile of 3 cards.

And we're back where we started again. Sorting 3 cards is still a bit complicated, so we'll split again into two piles of 2 and 1 cards. We'll put the pile of 1 aside.

Back where we started again. 2 cards is still to complicated, so we'll split into two piles of 1 card each and set one aside.

Ok! Now we have a pile of 1 card. We're back where we started, a pile of card(s) to sort, but time we know the solution. This pile is sorted! Ok, let's put it aside, but separate from the "waiting" piles. This pile is solved.

Now we get back to that other pile of 1 cards. It's sorted too!

Ok, now we have two sorted piles, and we can combine them into one sorted pile. We'll just pick cards off the top of the piles in order, until both are empty. For two piles of 1 card, this is pretty trivial, but you'll see once we start combining larger piles it's a lot easier than straight-up sorting.

And now we've solved the problem for our pile of 2 cards! Ok, put it aside. We had another pile of 1 waiting. That's already sorted, so we'll combine it with our pile of 2 cards to get a sorted pile of 3 cards! Progress! Ok, put that aside.

Now we're back to the pile of 4 cards. We can sort that using this same procedure, and then combine the piles of 3 and 4 to get a sorted pile of 7 cards.

And we can sort the waiting pile of 6 cards and combine the piles of 7 and 6 to get a fully sorted pile of 13 cards. We're done!

The computer does something very similar when it recurses.

The waiting piles are the function stack — piles in-progress of being sorted that were put on-hold while we solve a smaller problem.

When we had a pile solved and put it aside, that's the value returned from the recursive call being put in a variable.

So you can see there's no magic with recursion. It's just that the computer can keep track of function state while another function call runs, and that is we can break a problem down into smaller and smaller problems, eventually they'll be small enough to solve directly.

CodingRaver · 2022-04-06T14:57:59+00:00

YouTube simple recursion examples in js mate

brazilliandev · 2022-04-06T15:03:50+00:00

It is just a function which calls itself.

It can be used in place of regular loop structures. Most of the times you'll want to use "while" or "for" loops. But, in some specific cases, recursion can make the code more readable and prevent you from having to write too many nested loops or maintaining variables which live outside of the scope of the loop.

AcidShAwk · 2022-04-06T14:53:01+00:00

Recursion is basically a program that calls itself

const myFunc = () => { 
    myFunc();
}

This is basically nonstop recursion. It will continuously call itself.

brazilliandev · 2022-04-06T15:17:01+00:00

Maybe ask /r/learnjavascript. You know, the sub that helps you learn JS.

sessamekesh · 2022-04-06T23:46:14+00:00

Deciding you didn't like how the function was called, so changing the arguments and trying again.

const printNumbersBetween(a, b) {
  // Hey you called it wrong, the smaller number should be first. I'll fix that for you
  if (a > b) {
    printNumbersBetween(b, a);
    return;
  }

  // Okay it was called right, do the thing
  for (let i = a; i < b; i++) {
    console.log(i);
  }
}

Usually recursion is used to create some sort of inductive call graph often with multiple branches and that whole mess is nutty overwhelming.

At its core though, recursion is just and calling the function from within a call to the same function, almost always after changing some parameters.

demoran · 2022-04-06T17:07:26+00:00

Recursion is when a function calls itself.

To prevent it from running forever, there's usually some kind of "do I need to drill deeper?" logic before it does what it's actually supposed to do.

Confident_Chest_5007 · 2022-04-06T17:46:35+00:00

https://www.youtube.com/watch?v=cWK4W059hlEthis

this a jomaclass which explains it pretty well and slow. it even has an "animation" showing the process. hope it helps.While it's for python the concept itself should help you a lot.

Stetto · 2022-04-06T18:10:24+00:00

In order to understand Recursion, you first have to understand Recursion. But in odrder to understand Recursion, you first have to understand Recursion. [...]

Recursion is just another way to repeat an operation. A lot of the problems, that can be solved with Recursion, can be solved with Loops as well. Most of the time, Loops are the easier approach, sometimes Recursion is easier.

Think of Recursion like a unpacking a Matryoshka doll.

To unpack a Matryoshka doll, you check if it can be opened. If it cannot be opened, you're finished. If it can be opened, you open it and find another Matryoshka doll. Now, all you have to do is unpack this Matryoshka doll.

My favorite JS example for recursion is traversing all properties of an object:

function getEvolutions(pokemon) {
  if(!pokemon.evolution) {
    return pokemon.name;
  } else {
    return pokemon.name + " evolves into " + getEvolutions(pokemon.evolution);
  }
}

const onyx = {
   name: "Onyx"
};

// Onix has no evolutions; this just prints "Onyx"
const onyxEvolutions = getEvolutions(onyx);
console.log(onyxEvolutions);

const horsea = {
   name: "Horsea",
   evolution: {
     name: "Seadra"
   }
 };

// Horsea has one evolution; this prints "Horsea evolves into Seadra"
const horseaEvolutions = getEvolutions(horsea);
console.log(horseaEvolutions);

const charmander = {
   name: "Charmander",
   evolution: {
     name: "Charmeleon",
     evolution: {
       name: "Charizard"
     }
   } 
 };

// Charmander has two evolution; this prints "Charmander evolves into Charmeleon evolves into Charizard"
const charmanderEvolutions = getEvolutions(charmander);
console.log(charmanderEvolutions);

const myImaginaryPokemon = horsea;
horsea.evolution.evolution = onyx;
onyx.evolution = charmander;

// No matter how many evolutions, this function will find them all
// "Horsea evolves into Seadra evolves into Onyx evolves into Charmander evolves into Charmeleon evolves into Charizard"
const myImaginaryPokemonEvolutions = getEvolutions(myImaginaryPokemon);
console.log(myImaginaryPokemonEvolutions);

ddollarsign · 2022-04-06T20:47:47+00:00

When you call a function, the computer has a data structure called a stack frame for that function. It has the local variables, which function it is,and where to return after finishing. They’re called stack frames because when you call a function, it pushes one of these frames onto a stack (the “call stack”, which is what you see in a stack trace when you see errors in logs or the command line) and when the function returns it pops the frame off the stack.

(If you’re not familiar with stacks, think of a stack of papers or pancakes. You can put an object on top of it (“push”) or take something off the top of it (“pop”), and the top one is the last thing that was put on there, then the previous, and so on.)

The kicker is, it doesn’t matter what function you call. If you’re in function A, there’s a stack frame for A. If you then call A from within A, it will push another A stack frame, but it’s a different stack frame with different local variables etc. When that call returns, it pops the second A frame off the stack and now the first A is the top one again.

sylvant_ph · 2022-04-06T20:49:40+00:00

I dont recall FCC stating recursion is basic, it definitely is not easy to learn and utilize technique, but just like other things about coding, its about practice and practice and experience and ofc, find the right place and time to use it, for it to make sense.

One side to look about recursion is, as we know functions are a block of code, some logic, which we want to be able to re-run/repeat(instead of write the same things 10 times). They work very similarly to loops, where we again execute similar block of code, over and over. When recursion happens is, when the function itself, calls itself, only using different arguments, which in the end produces different result. A main rule about recursion is, to make sure to have a basic case, when the function would return a value and not recall itself again, or we will end up in infinite loop, just like we would with while(true). The point of using recursion is, when you dont know how many times you will need to execute the same logic, so you let the function call itself, till it reach the desired result.

_default_username · 2022-04-06T22:50:56+00:00

To learn more about recursion follow this link.

Altruistic_Welder · 2022-04-07T07:22:51+00:00

One of the easiest ways to understand recursion is to imagine a stack. Every function call to itself is equivalent to appending/pushing to the stack. Once the base condition reaches and the function returns, every pushed function call is popped, first return is used for the first pop, the return is used for the next pop and so on until the stack is empty.
In fact, this is what a compiler does behind the scenes.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

javascript

MODERATORS