재귀

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

재귀 함수 :  함수 안에서 자기 자신을 호출하는 함수 (반복적으로 같은 코드를 호출하여 사용)

 

[재귀로 해결하는 문제]

 

- 자연수로 이루어진 리스트를 입력받고, 리스트 의 합을  리턴하는 함수 작성하기

[1, 2, 3, 4, 5]  =>  15??

 

1. 문제를 작게 쪼개기

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

 

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

arrSum([5]) === 5 + arrSum([])

 

3. 작은 단위의 문제 해결  > 전체 문제 해결

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);	// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum
                						// 자기 자신을 계속하여 호출함으로 문제를 작게 쪼개기
}

 

 

 

 

재귀 함수 사용 하기?

1. 재귀 함수의 입력값과 출력값 정의하기
- arrSum 의 경우, 입력값 = number 타입의 배열 /  출력값 = number 타입

2. 문제를 쪼개고 경우의 수 나누기
- arrSum([1,2,3,4])와 arrSum([2,3,4]) 는 구하는 방법이 같다. 따라서 이 방법으로 쪼개질 수 없을 때까지 쪼갠다.

   arrSum([]) >> 입력이 빈 배열인 경우 , arrSum([1,2,3, ... , 10])  >> 요소가 있는 경우 를 분할하여 생각하여야 함.

3. 단순한 문제 해결
- 탈출 조건 세우기

  arrSum 의 요소들을 더해주다가 arrSum ([ ]) 이 이렇게 빈 배열이 될 경우 리턴 0을 해준 후 탈출!

4. 복잡한 문제 해결
- 재귀 문제 풀기

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

5. 위를 합하여 코드구현

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

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

 

 

 

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

>> 모든 재귀함수는 반복문으로 표현할 수 있다. 하지만 재귀를 사용할 경우 코드가 더욱 간결하고 이해도가 높아진다.