JavaScript - Steps algorithm in recusive way - multi loop issue

Question

I have this algorithm exercise that is very popular with developers that returns:

steps(3)

#
##
###

steps(5)

#
##
###
####
#####

I am studying a version of it developed in a recursive way. The code below is working fine.

function steps(n, row = 0 , stair = '') {
  if(n === row) {
    return;
  }

  if(n === stair.length) {
    console.log(stair)
    return steps(n, row + 1)
  }

  if (stair.length <= row) {
    stair += '#';
  } else {
    stair += ' '
  }
  steps(n, row, stair)

}

steps(3)

My only doubt is related to the importance of the 'return' in this part of the code:

 if(n === stair.length) {
   console.log(stair)
   return steps(n, row + 1) // <--- this 'return' 
 }

If I delete the 'return', like this way:

if(n === stair.length) {
  console.log(stair)
  steps(n, row + 1)  // <-- without the return
}

this generates a looping error on console:

Maximum call stack size exceeded

I want to understand why this happens under the hood. I still don't have much practice with recursive functions.

Scott Hunter · Accepted Answer · 2020-07-02 21:28:05Z

1

if n===stair.length, you don't want to make the call steps(n, row, stair) at the bottom of the function, which you would if you left out the return.

answered Jul 2, 2020 at 21:28

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kevin Wang · Accepted Answer · 2020-07-02 21:36:48Z

There are kind of 2 ways to think about recursive functions. The first is to actually look at what literally happens -- that is, look at an example and "unroll" by noting all of the calls to the function steps. This is safe to think about and is easy.
The second way is more "magical. In this way of thinking, you do NOT consider a "big picture" or think about multiple calls of the recursive function. Instead, you form a coherent idea of what your recursive function SHOULD accept as arguments and what it SHOULD return. Then, you can always write the body of your recursive function by using that function in the way you assume it should work. This can be more confusing to grasp, but once you "get" it, it's very elegant and is the more useful mode of thinking.

Let's use the first mode of thinking here, since it's probably easier. Can you tell me how many times steps gets called and with which arguments, in order? For example, the first call is steps(5, 0, ''). Then, what is the second call of steps that will happen? Follow these steps (heh) and you should see what the issue is.

Charlie Bamford · Accepted Answer · 2020-07-02 21:36:52Z

1

It breaks because your code terminates when row === n. That line is the only place where row is changed. Without it, the code will produce output like this:

#
#
#
#
#
...

Since you're handling this in a recursive function, javascript runs out of stack frames before it gets infinitely deep.

edited Jul 2, 2020 at 21:36

answered Jul 2, 2020 at 21:30

Charlie Bamford

1,3197 silver badges18 bronze badges

Collectives™ on Stack Overflow

JavaScript - Steps algorithm in recusive way - multi loop issue

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related