[자료구조/알고리즘] javascript로 재귀 풀기

재귀란 ?
원래의 자리로 되돌아가거나 되돌아옴
아래의 코드 처럼 선언한 함수내의 같은 함수를 호출함으로서 재귀를 구현할 수 있음
아래의 코드처럼 recusion 함수는 재귀함수라고 함 
재귀 함수를 잘 활용하면 반복적인 작업을 하는 문제를 좀 더 간결한 코드로 풀어낼 수 있음 

언제 사용하는게 좋을까 ?
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운경우

function recursion() {
	console.log("hi")
    console.log("manchoon")
    recursion()
 }

재귀로 문제 해결하기

재귀로 문제를 풀기에 앞서 이론적으로 재귀로 문제를 해결하는 단계는 아래와 같음 
1. 문제를 좀 더 작게 쪼갬
2. 1번과 같은 방식으로, 문제가 더 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갬 
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결함 

문제 : 자연수로 이루어진 리스트(배열)을 입력받고, 리스트의 합을 리턴하는 함수 'arrSum' 을 작성해라 

 

배열이 [1, 2, 3, 4, 5] 로 주어졌을 때 가장 먼저 생각해야 할 것은 '작게 쪼개는 것이다' 

[1, 2, 3, 4, 5] 보단 [2, 3, 4, 5] 가 더 작고 [3, 4, 5] 의 합을 더하는 것이 더 작은 문제이므로 

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([])

마지막에는 arrSum 이 빈 배열을 받게 되면 문제를 가장 작은 단위까지 쪼갰다고 할 수 있다. 

문제를 가장 작은 문제까지 쪼갰으므로 이제 문제를 해결해야 한다. 

쪼개졌던 문제는 거꾸로 거슬러 올라가면서 합쳐지게 된다. 

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;

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

따라서 위의 단계들을 기반으로 코드를 작성해보겠다.

function arrSum(arr){
	// 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드 
	if(arr.length === 0){
    	return 0;
    }
    
    return arr.shift() + arrSum(arr)
}

 

재귀 함수 템플릿

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

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

문제 : 배열을 입력받아 모든 요소의 합을 리턴하는 재귀함수 만들기 

배열은 head와 tail을 통해 재귀적으로 정의될 수 있습니다.

head는 배열의 첫 요소를 말합니다.

tail은 배열이 head가 제거되고 남은 배열을 말합니다.

(예시) [1, 2, 3]

1) [ ] => 0

2) [3] => 3 + [ ]

3) [2, 3] => 2 + [3]

4) [1, 2, 3] => 1 + [2, 3]

3번의 [3]는 2번에 의해서 3 + [ ]로 정의되고, 따라서 [2, 3]는 최종적으로 2 + 3 + [ ] 로 정의될 수 있습니다.

길이가 1 이상인 배열 arr이 주어졌을 때 head와 tail은 각각 다음과 같이 구할 수 있습니다.

const head = arr[0];
const tail = arr.slice(1);

arrSum(arr)은 arr의 head에 arrSum(tail)을 더하는 방식으로 구할 수 있습니다.