Why does recursion reverse itself?

[ugwen]

hopefully the code is clear (with the output). It seems to show recursion:

• evaluating all in one go (asynchronously?)
• executing statements from before the call 1st and in sync
• then executing statements from after the call and in reverse sync, giving a mirror effect.

i may be misunderstanding synchronicity, but i don’t know why it appears (in terms of output) to go into reverse
(sorry, this post explains better when you copy the code to editor to see output)

const recurse = array => {

  if(array.length <= 1) { return array }

  const midIndex = Math.floor(array.length / 2)
  const leftArr = array.slice(0, midIndex)
  const rightArr = array.slice(midIndex)

  n++
  console.log( 'BEFORE', 'left:',leftArr, 'right:',rightArr, 'n:', n, 'p:', p)

  recurse(leftArr)

  p++
  console.log(' AFTER', 'left:',leftArr, 'right:',rightArr, 'n:', n, 'p:', p)

  return leftArr.concat(rightArr)
}

let n = 0, p = 0  // LABELS ONLY n = prevCount ; p = postCount (wrt recursive call)
const array = [1,2,3,4,5,6,7,8,9,10]
console.log('original:', array, '\n','--------')
console.log('--------','\n', 'recursed:', recurse(array))

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/102.0.5005.115 Safari/537.36

Challenge: Implement Merge Sort

Link to the challenge:

freeCodeCamp.org

[bbsmooth]

I’m not exactly sure I understand what you mean by going in reverse? You are making the recursive call between the console log “BEFORE” and the console log “AFTER”, so you will never get to “AFTER” until the array length <= 1. Thus, all of the "BEFORE"s will execute first and then once they are finished all of the "AFTER"s will execute as you work your way back up the recursion stack.

I’m not sure if that answers your question, it’s just my best guess as to what you meant by “going in reverse”.

[ugwen]

thanks. i need to go back and revise the ‘recursive stack’ part.

[ugwen]

it’s just i was seeing that the AFTER part should only be executed once after the recusive call stuff with the result of the Arr’s at the end of that process, but that’s not the case…the AFTER part is put in the stack before then?

yeh, i think seeing this bit of code shows the stack working:

function countUp(n){
    //n(1)-before recursive call, n(2)-after
  if(n < 1){return[]}
    console.log('PUSHED TO STACK HERE:', 'n(1):',n)
  const array = countUp(n-1)
    console.log('STACK EXECUTED HERE:', 'n(2):',n)
  array.push(n)
  return array;
}
console.log(  countUp(10) )

[colinthornton]

function countUp(n) {
  if (n < 1) return [];
  const array = countUp(n-1)
  array.push(n)
  return array;
}

console.log(countUp(3))

Let’s look at how this is evaluated.

Inside the console log we call countUp with n=3 so we need to evaluate that. To evaluate it we’ll need to run all the lines of the function.

// lines to run for countUp(3)
  if (3 < 1) return []; // 3 is not less than 1 so skip this
  const array = countUp(3-1) // pause here!
  array.push(3)
  return array;

But in the middle of evaluating that call, we call another function, countUp(2), so we’ll need to evaluate that before continuing on.

// lines to run for countUp(2)
  if (2 < 1) return []; // 2 is not less than 1 so skip this
  const array = countUp(2-1) // pause here!
  array.push(2)
  return array;

But in the middle of evaluating that call, we call another function, countUp(1), so we’ll need to evaluate that before continuing on.

// lines to run for countUp(1)
  if (1 < 1) return []; // 1 is not less than 1 so skip this
  const array = countUp(1-1) // pause here!
  array.push(1)
  return array;

But in the middle of evaluating that call, we call another function, countUp(0), so we’ll need to evaluate that before continuing on.

// lines to run for countUp(0)
  if (0 < 1) return []; // 0 is less than one so return here
  // skip the lines below because we've already returned
  const array = countUp(0-1)
  array.push(0)
  return array;

The call to countUp(0) returns [], so now we can continue where we left off with countUp(1).

// lines to run for countUp(1)
  if (1 < 1) return [];
  const array = countUp(1-1) // continue evaluation from here
  array.push(1) // array is now [1]
  return array; // return [1]

The call to countUp(1) returns [1], so now we can continue where we left off with countUp(2).

// lines to run for countUp(2)
  if (2 < 1) return [];
  const array = countUp(2-1) // continue evaluation from here
  array.push(2) // array is now [1, 2]
  return array; // return [1, 2]

The call to countUp(2) returns [1, 2], so now we can continue where we left off with countUp(3).

// lines to run for countUp(3)
  if (3 < 1) return [];
  const array = countUp(3-1) // continue evaluation from here
  array.push(3) // array is now [1, 2, 3]
  return array; // return [1, 2, 3]

Now the return value of countUp(3), [1, 2, 3], is logged to the console.

[ugwen]

yes. so simple. thank you.