자바스크립트 13 재귀함수

• 재귀: 원래의 자리로 되돌아가거나 되돌아옴

=> 재귀 함수 = 자기 자신을 호출하는 함수

 

• 재귀로 문제 해결하기

1. 문제를 좀 더 작게 쪼개기

2. 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼개기

3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결하기

 

 

-> 자연수로 이루어진 배열에서, 해당 값들의 합을 리턴하는 함수 arrSum을 재귀로 구현해보면 다음과 같은 사고 과정을 통해 이루어진다. 

 

1. 문제를 좀 더 작게 쪼개기

 

[1, 2, 3, 4, 5] 의 합을 구한다고 생각해보자.

 

= 1 + [2, 3, 4, 5]

= 1 + 2 + [3, 4, 5]

= 1 + 2 + 3 + [4, 5]

= 1 + 2 + 3 + 4 + [5]

 

이렇게 쪼개볼 수 있다. 

 

2. 문제를 가장 작은 단위로 쪼개기

 

저기서 한 단계 더 나아가면,

 1+ 2 + 3 + 4 + 5 + [] 까지 도달했을 때 더 이상 쪼갤 수 없는 상태가 된다. 

 

3. 가장 작은 단위 문제 해결 -> 전체 문제 해결

 

arrSum([]) === 0 // 문제가 더 이상 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용

arrSum([5]) === 5 + arrSum([])
arrSum([4, 5]) === 4 + arrSum([5])
...
arrSum([1, 2, 3, 4, 5] === 1 + arrSum([2, 3, 4, 5])

 arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전채가 해결된다. 

 

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

base case인 arrSum([])은 조건문에 의해 더 이상 자기자신을 호출하지 않고, 숫자 0을 리턴하며 종료된다. 

그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결되는 과정을 거친다.

 

• 재귀를 사용해야 하는 상황
  • 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  • 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우 
• 재귀적으로 사고하기
  • 재귀 함수의 입력값과 출력값 정의하기
  • 문제를 쪼개고 경우의 수를 나누기
    • 입력값이나 문제의 순서와 크기
    • 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 동일하다면, 문제를 제대로 구분한 것!
  • 단순한 문제 해결하기
    • base case -> 탈출 조건 구성
  • 복잡한 문제 해결하기
    • recursive case

 

재귀함수로 작성이 되는 코드는 반복문으로도 작성할 수 있다. 그런데, 재귀함수는 메모리를 많이 차지하고 성능이 반복문에 비해 느리다고 한다. 함수를 반복적으로 호출하므로, 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있다. 상황에 맞게 적절하게 사용해야 한다. 

 

 

스택과 관련된 내용이 궁금해서 찾아본 글! 

https://ko.javascript.info/recursion

재귀와 스택

실행 컨텍스트가 어떻게 동작하고, 스택에 어떻게 쌓는지에 대한 내용을 찾아보았음.