[자료구조/알고리즘] 재귀

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

Chapter1. 재귀의 이해

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

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

3. 문제가 더 쪼개지지 않으면, 가장 작은 단위의 문제를 해결한다.
   문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에, 가장 작은 단위의 문제를 해결한 방식을 리턴하면 문제 전체를 해결할 수 있게 된다.
   2번에서 가장 작은 문제는 arrSum([])이였다. 빈 배열의 합은 0이니까, 0을 리턴해준다.
   그렇게 되면 arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고 최종적으로는 문제 전체가 해결된다.

function arrSum(arr){
  // base case
 if(arr.length === 0){
 	return 0
 }
  // recursive case
return arr.shift() + arrSum(arr)
}

arrSum([])은 조건문에 의해 더이상 자기자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다. 그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.

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

1) 주어진 문제를 더 작은 문제로 나눌 수 있는 경우
2) 중첩된 반복문이 많거나 , 반복문의 중첩 횟수를 예측하기 어려운 경우
=> 모든 재귀 함수는 반복문으로 표현할 수 있다. 그러내 재귀를 적용한 코드가 간결, 이해하기 쉽다.