[JS] 재귀 함수

재귀(recursion) 함수

: 재귀 함수란 자기 자신을 호출하는 함수입니다. 재귀 함수를 적용한 코드가 일반적인 반복문으로 이루어진 코드보다 더 간결하고 이해하기 쉽습니다.

재귀 함수가 필요할 때

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

재귀적 사고의 단계

1. 재귀 함수의 입력 값과 출력 값 정의하기.
2. 문제를 쪼개고 경우의 수를 나누기.
3. 단순한 문제 해결하기.
4. 복잡한 문제 해결하기.
5. 코드 구현.

일반적인 재귀 함수의 예시

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

재귀 함수의 장단점

장점

• 변수의 개수를 줄일 수 있습니다.

현재 상태를 저장해야 할 경우 tmp 변수를 만들지 않고, 현재 상태를 메소드를 통해 재귀적으로 호출하면서 변경된 상태를 전달함으로 tmp 변수를 정의하지 않아도 됩니다.

• 반복문을 대체 할 수 있어 코드가 간결해집니다.

상황에 따라 반복문이 여러번 중첩되어야 하는 경우, 코드의 가독성을 떨어뜨리고 얼마나 반복되는지 예측하기 힘들게 됩니다. 이 경우에 재귀함수를 사용함으로써 가독성을 높이고 비교적 예측하기 쉽게 만들어줍니다.

단점

• 메모리 사용이 증가합니다.

지속적으로 함수를 호출하게 되면서 함수 내에서 정의된 로컬변수, 파라미터, 리턴값 모두 Call stack에 저장해야합니다. 이런 과정은 선언한 변수의 값만 사용하는 반복문보다 메모리를 더 많이 사용하게 되고 메모리가 스택의 공간을 넘어가게 되면 Stack overflow 문제가 발생하게 됩니다.