[JavaScript] 재귀함수

재귀는 언제 사용하는게 좋을까?

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

 

function recursive(인자) {
  // 조건이 충족될 때 까지 자기 자신을 호출
  if(조건 충족) {
    return 결과
  } else {
    return recursive(작업된 인자)
  }
}

• 재귀 : 문제를 해결할 때 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법
  *모든 재귀는 반복문으로 표현 가능
• 재귀 함수 : 스스로를 호출하는 함수
• 재귀 호출 : 재귀 함수는 실행 과정 중에 자기 자신을 호출하게 됨
  *모든 재귀 함수는 함수의 호출 없이 while / for loop로 표현 가능
• 재귀를 사용한 코드 : 더욱 간결하고 이해하기 쉬움

 

 

재귀적 사고

1. 재귀 함수의 입력값과 출력값 정의하기 : 문제를 가장 추상적으로 또는 단순하게 정의
2. 문제를 쪼개고 경우의 수를 나누기 : 입력값이나 문제의 순서와 크기를 고려
3. 단순한 문제 해결 (base case) : 문제를 더이상 쪼갤 수 없을 때까지 쪼개어 가장 해결하기 쉬운 문제부터 해결
   base case (재귀의 기초) : 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건) 구성
4. 복잡한 문제 해결 (recursive) : 남아있는 문제 해결
   recursive Case : 자신을 호출하는 함수를 포함

function factorial(num) {
  if(num === 1) { // 더이상 쪼갤 수 없는 base case
    return 1
  }
  return num * factorial(num - 1) // 재귀 호출(자기 자신을 호출)
}

let myNumber = [1, 4, 5, 3, 2]

function arrSum(arr) {
  if(arr.length === 0) { //base case
    return 0
  }
  return arr[0] + arrSum(arr.slice(1)) //recursive Case
}

sum(0, myNumber)
// 15

 

 

재귀 함수의 성능 문제

• 호출될 때마다 메모리에 스택이 쌓이는데, 한계치 이상으로 호출이 되어 스택이 넘쳐버리면 메모리 부족으로 에러 발생
• jump가 잦아 반복문에 비해 시간이 오래 걸림
• 꼬리 재귀 최적화 기능을 통해 해결 : return 값이 함수 자체 뿐
  꼬리 재귀 최적화 (Tail Call Optimization) : 재귀 함수를 컴퓨터가 재해석하여 선형 알고리즘을 만들어 실행, 아무리 반복이 일어나도 스택이 넘치지 않음

 

 

재귀 심화

1. 꼬리 재귀 (tail recursion in js)

2. 하노이의 탑 재귀 (js tower of hanoi in recursion)

3. 조합 재귀 함수 (js combination in recursion)

 

 

References

재귀 함수