Snake nail (issue with recursion)

Question

I try to create the function, that takes n×n matrix (array of arrays) returns one array arter traverse in a clockwise snailshell pattern.

For more information: https://www.codewars.com/kata/521c2db8ddc89b9b7a0000c1

But my code is ok only for 3x3 matrix. If it is bigger there is the error "Maximum call stack size exceeded"

Could you pls help me to understand my mistake

My code:

function snail (array) {
  let result = []
  
  function resultFilling(arrayForResult) {
    if (arrayForResult[0].length === 1) {
      result.push(arrayForResult[0][0])
      return
    }
    
    for (let i = 0; i < arrayForResult.length - 1; i++) {
      result.push(arrayForResult[0][i])
    }
    for (let i = 0; i < arrayForResult.length - 1; i++) {
      result.push(arrayForResult[i][arrayForResult.length - 1])
    }
    for (let i = arrayForResult.length - 1; i > 0; i--) {
      result.push(arrayForResult[arrayForResult.length - 1][i])
    }
    for (let i = arrayForResult.length - 1; i > 0; i--) {
      result.push(arrayForResult[i][0])
    }
    
    let newArr = array.reduce((accum, item, index) => {
      if (index > 0 && index < array.length - 1) {
        accum.push(item.splice(1, item.length - 2))
      }
      return accum
    }, [])
    
    if (newArr.length > 0) resultFilling(newArr)
  }
  
  resultFilling(array)

  return result
}

Yes, i know, that it can be resolved by using "while", but I tried to optimize my code and decided to use recursion. And now I can't really understand why it's not working — skusov, Aug 23 '22 at 13:53
See also https://stackoverflow.com/q/57946428, with at least one answer doing this recursively. — Scott Sauyet, Aug 23 '22 at 15:09

Scott Sauyet · Accepted Answer · 2022-08-24T11:21:50.313

The simplest way to see what's wrong is to add

    console .log (arrayForResult)

at the beginning of resultFilling. When you then try with this input:

const arr4x4 = [
  [1,   2,  3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10,  9,  8, 7]
]

you will get this in the console:

[[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
[[13,14],[16,15]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
[[],[]]
//...
Error: Maximum call stack size exceeded

Which should point us to the problem. A quick fix would be to replace

    if (newArr.length > 0) resultFilling(newArr)

with

    if (newArr.length > 0 && newArr[0].length > 0) resultFilling(newArr)

Now you will get this in the console:

[[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
[[13,14],[16,15]]

and get this return value:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

But if you're interested in an entirely different approach, you can see my answer to a related question by expanding this snippet:

const reverse = a => 
  [...a] .reverse ();

const transpose = m => 
  m [0] .map ((c, i) => m .map (r => r [i]))

const rotate = m => 
  reverse (transpose (m))

const spiral = m => m .length < 2
  ? [... m [0]]
  : [... m [0], ... spiral (rotate (m .slice (1))) ] 


console .log (spiral ([
  [1,   2,  3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10,  9,  8, 7]
]))

.as-console-wrapper {max-height: 100% !important; top: 0}

Snake nail (issue with recursion)

1 Answers1