자바스크립트에서 재귀함수 사용하기

재귀(Recursion)란

재귀란 무엇일까요?
사전적 정의로 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법입니다.

자바스크립트에서 재귀 함수란 자기 자신을 재호출하는 함수 정도로 설명할 수 있겠네요.

뭔가 복잡하고 어렵게만 느껴지네요. 비유를 들어보겠습니다.

비유

옛날 옛적 숫자가 홀수인지 짝수인지 모르던 시절의 한 꼬마 마법사 레미가 살았습니다.

꼬마 마법사들이 정식 마법사가 되려면 동굴에 사는 정체불명의 그림자 괴물에게 가서 스크롤에 담긴 숫자 중 홀수를 알아와야 했습니다.
한 꼬마 마법사 레미는 스승님에게서 이 과제를 받고 동굴로 떠났습니다.

스크롤에는 [10, 54, 66, 38, 64, 2]라고 적혀있었습니다.

하지만 막상 레미가 그림자 괴물에게 찾아가 스크롤에 적힌 숫자 중 어떤 게 홀수인지 알려달라 하니, 그림자 괴물은 역정을 내며 절대 알려줄 수 없다고 합니다.

레미는 협상을 시도하죠.
그러면 이 스크롤의 숫자 중, 첫 번째 숫자가 홀수가 아닌지만 알려주세요!

그림자 괴물은 승낙합니다.

이윽고 레미가 첫 번째 질문을 했습니다.

[10, 54, 66, 38, 64, 2] 중 10은 홀수인가요?
답변은 홀수가 아니었습니다. 홀수가 아니다!

레미는 골똘히 생각을 했고, 이내 스크롤의 숫자 중 10을 들고 있던 깃펜으로 지운 후 두 번째 질문을 했습니다.

[54, 66, 38, 64, 2] 중 54는 홀수인가요?
54또한 홀수가 아니었습니다.

이렇게 스크롤의 숫자를 차근차근히 지워나간 레미의 스크롤에는 이제 아무런 숫자가 남지 않았습니다.

레미는 또다시 질문했죠.

[]의 첫번째 숫자가 홀수인가요?

그러자 그림자 괴물은 엄청난 화를 내며 그 스크롤은 비어있지 않냐고 멍청이는 썩 꺼지라 말했습니다.

하지만 이미 레미는 원하는 결과를 얻었죠! 스크롤에는 홀수가 하나도 없었습니다.

예시

앞선 비유가 이해되셨나요?
똑같은 동작(함수)를 목적을 달성할 때까지(배열이 빌 때까지) 반복했죠?

이렇게 특정 조건 하에 함수 자신을 계속해서 참조하는 것이 재귀입니다.

코드를 한번 살펴볼까요?

소스를 복사한 후 snippet 등에서 breakpoint를 걸고 참고해보세요.

function findOdd(nums) {
  let result = []
  if (nums.length === 0) {
    return result
  }
  if (nums[0] % 2 === 1) {
    result.push(nums[0])
  }
  return result.concat(findOdd(nums.slice(1)))
}

findOdd([10, 54, 66, 38, 64, 2])

참고 - snippet 실행 영상

재귀를 사용하는 이유

꼭 재귀를 사용하지 않아도 되고, 어떤 경우에는 재귀를 사용하지 않는 것이 더욱 깔끔할 때가 있습니다. 재귀를 사용하는 이유는 여러가지가 있습니다.

재귀를 흔하게 사용하는 경우

JSON.parse
JSON.stringify
document.getElementById
DOM 순회 알고리즘

같은 걸 사용할 때는 보통 재귀적으로 작성됩니다.

DOM은 중첩된 tree 구조로 되어 있습니다. div속에 div가 들어있는 중첩 레이어가 100개, 1000개가 될 수도 있습니다. 그 속을 살펴볼 때 흔하게 사용하는 방법 중 하나가 재귀적으로 움직이는 코드를 작성하는 것입니다.

재귀의 장점

재귀적 표현이 자연스러울 때 적합
- 팩토리얼이나 피보나치 등
변수사용을 줄임
- 함수의 단순화

재귀를 쓰지 맙시다

종료 조건으로 수렴하지 않을 때

for 구문을 사용할 때 무한 루프에 빠지게 된다면 브라우저가 먹통이 되겠죠?

재귀도 마찬가지입니다.

함수에 입력되는 입력값이 변하지 않고 그대로거나, 종료조건이 없거나, 스택 메모리를 초과하여 호출하는 경우에는 재귀를 사용하지 않는 것이 좋습니다.

위에 작성했던 함수의 일부 코드를 주석처리해보겠습니다.

function findOdd(nums) {
  let result = []
  // if (nums.length === 0) {
  //     return result;
  // }
  if (nums[0] % 2 === 1) {
    result.push(nums[0])
  }
  return result.concat(findOdd(nums.slice(1)))
}

findOdd([10, 54, 66, 38, 64, 2]) // Uncaught RangeError: Maximum call stack size exceeded

바로 Maximum call stack size exceeded에러가 발생했습니다.

호출 스택의 메모리를 초과해버렸다는 것이죠.

if (nums.length === 0) {
    return result;
}

이 부분이 바로 재귀 함수의 종료 조건이었음을 알 수 있습니다.
이미 result 배열은 길이가 0이지만 계속해서 slice 처리를 하고, 또 함수를 호출하게 된 것입니다.

재귀함수 작성 시 Tips

종료조건을 먼저 생각하자
array 가 input값인 경우에는 slice나 spread 연산자, concat 연산자 사용이 유용하다
string 인 경우에는 slice, substr, substring이 string input값을 복사하기 유용하다
object 인 경우는 Object.assign이나 spread 연산자가 유용하다

Yeony