javascript 의 재귀함수 문제
조회수 339회
function flatten(oldArr) {
var newArr = []
for (var i = 0; i < oldArr.length; i++) {
if (Array.isArray(oldArr[i])) {
newArr = newArr.concat(flatten(oldArr[i]))
} else {
newArr.push(oldArr[i])
}
}
return newArr;
}
// flatten([[1],[2],[3]]) // [1,2,3]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1,2,3]
재귀함수를 이용해서 배열의 모든값을 하나만 출력이 되도록 하는 문제입니다. 풀다가 도저히 못풀어서 문제의 해답을 보게되었는데요 코드중 for 문안에서의 작동 로직이 도저히 모르겠습니다. 해당 코드의 동작로직이 어떻게 될까요??
1 답변
-
재귀 함수를 다루는 데 있어서 가져야 되는 것이 있는데, 바로 함수에 대한 믿음입니다. 여기서
flatten
함수는 배열을flat
하게 만들어 주는 함수입니다. 이 때 함수의 내용을 구현할 때에는 함수 안의 코드에서 등장한flatten
함수는 올바르다고 믿어 봅시다.무슨 말인지 헷갈릴 수도 있을 것 같습니다. 예시를 들어 보겠습니다.
const arr = [ [1, [2, 3, 4], [5, [6], 7]], [3, 1, 4, [1]], 5, 9, [2, 6, 5] ]
우리가
arr
에flatten
을 하고 싶다고 가정해 보겠습니다.Array.isArray
는 어떤 변수가 배열인지 아닌지를 알려줍니다.- 위에서 언급해 주신 코드는 그러면 원소가 배열인 경우에는
flatten
함수를 호출해서newArr
에 원소들을 전부 집어넣을 것이고, - 그렇지 않을 경우에는 원소 하나이므로
newArr
에 그냥 집어넣어 줄 것입니다.
- 위에서 언급해 주신 코드는 그러면 원소가 배열인 경우에는
그러면 이
flatten
함수의 구현이 맞다고 믿고,arr
의 각 원소에 대해 위의for
-루프를 돌리면 어떤 일이 일어나는지 생각해 봅시다.[1, [2, 3, 4], [5, [6], 7]], // flatten 후 -> [1, 2, 3, 4, 5, 6, 7] [3, 1, 4, [1]], // flatten 후 -> [3, 1, 4, 1] 5, // -> 배열이 아니므로 그대로 9, // -> 배열이 아니므로 그대로 [2, 6, 5] // flatten 후 -> [2, 6, 5]
결국에는,
newArr = newArr.concat([1, 2, 3, 4, 5, 6, 7]) newArr = newArr.concat([3, 1, 4, 1]) newArr.push(5) newArr.push(9) newArr = newArr.concat([2, 6, 5])
을 하게 되고, 우리가 기대하는
[1, 2, 3, 4, 5, 6, 7, 3, 1, 4, 1, 5, 9, 2, 6, 5]
가 된다는 것을 알 수 있습니다. 함수 안에 적혀 있는flatten
이 잘 실행될 거라고 믿었더니, 결과가 제대로 나오는 것을 알 수 있습니다.재귀 함수는 어떻게 짜나요
재귀 함수를 분석하는 것과 일맥상통합니다.
flatten
이라는 재귀 함수를 처음부터 작성해야 한다고 한다면, 일단 올바른flatten
함수가 이미 있다고 가정하고, 이걸 어떻게 활용하면 좋을지 고민해 보면 조금 더 쉽게 짤 수 있을 것입니다. 이 때 생각의 방향은 "큰 문제를 작은 문제로 쪼개서 생각한다"가 되면 더 좋겠습니다. (그렇지 않으면function flatten(oldArr) { return flatten(oldArr) }
같은 코드를 만들 수도 있으니까요!)앞서 언급한
arr
의 상황을 살펴봅시다.arr
를flatten
하려고 봅시다.- 우선 이 큰 문제를 작은 문제들로 쪼개 본다면
arr
의 원소 각각에 대해flatten
을 하고 생각하면 좋을 것 같아 보입니다. flatten
을 하고 보니[1, 2, 3, 4, 5, 6, 7], [3, 1, 4, 1], 5, 9, [2, 6, 5]
가 나옵니다.- 이제 이걸
[1, 2, 3, 4, 5, 6, 7, 3, 1, 4, 1, 5, 9, 2, 6, 5]
로 바꾸는 방법을 생각해 볼 수 있겠습니다. (2)에서 (3)으로 오는 것은 처음 문제를 바로 푸려고 하는 것보다 쉬울 것입니다.
댓글 입력