🌊 [JAVASCRIPT] 재귀함수

🌊 재귀함수

: 재귀 함수는 자기 자신을 호출하는 함수를 말합니다. 재귀 함수를 이용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 

 

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

 

재귀로 문제 해결하기

1. 문제를 좀 더 작게 쪼갠다.
2. 1번과 같은 방식으로, 문제는 더 작아지지 않을 때 까지, 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

//arrSum 함수는 배열[1,2,3,4,5]의 합을 반환하는 함수. 

arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

function arrSum(arr) {
 if(arr.length === 0) return 0
 // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
 return arr.shift() + arrSum(arr)
 }

 

1. 문제를 동일한 방식으로 계속 쪼개기
   → 쪼개는 방식이 recursive case
2. 더 이상 안 쪼개지는 것이 base case
   → 재귀 함수의 탈출 조건
3. base case 해결하기
   → 쪼개졌던 문제가 한 번에 해결

 

 

재귀가 적합한 상황

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
• 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

 

재귀적 사고 순서

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고(recursive case) 경우의 수를 나누기 
3. 단순한 문제 해결하기
   → 재귀의 탈출 조건(base case)을 구성하기
   탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다. 그렇다고 문제를 덜 쪼개지 말고 최대한 작게 쪼갠 후 해결한다.
4. 복잡한 문제 해결하기

 

 

• 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
• 꼬리 재귀 (tail recursion in js)
• 하노이의 탑 재귀 (js tower of hanoi in recursion)
• 조합 재귀 함수 (js combination in recursion)