6.15 Dev.Feedback ( 재귀함수 )

재귀함수

재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.

// 문제. 자연수로 이루어진 리스트(배열)를 입력받고, 
// 리스트의 합을 리턴하는 함수 `arrSum` 을 작성하세요.

let arr = [1, 3, 5, 7]

//a
let sum = 0;
for(let i =0; i<arr.length; i++){
	sum = sum + arr[i];
    }
    

//b
arr.reduce((acc,cur) => acc+cur)

재귀란, 자기 자신을 참조하여 자기 자신을 정의하는 것인데, 위의 경우처럼 어떤 문제를 맞이했을 때, 그 문제를 가장 작은 단위로 나누어 해결하고, 그 범위를 점차 넓혀가며 전체 문제를 해결하는 방식이다.

 

위를 예시로 들어 재귀를 통해 풀어본다면,

 

1. 기존의 문제에서 출발하여 더 작은 경우를 생각한다.

arrSum([1, 3, 5, 7]) = 1 + arrSum([3, 5, 7]);

 

2. 위와 같은 방식으로, 문제가 더는 작아지지 않을 때까지 쪼개본다.

arrSum([3, 5, 7]) = 3 + arrSum([5, 7]);
arrSum([5, 7]) = 5 + arrSum([7]);
arrSum([7]) = 7 + arrSum([]);

 

3. 문제가 간단해져서 바로 풀 수 있게 되는 순간부터 앞서 생성한 문제를 차근차근 해결한다.

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

위의 경우를 말로 정리하면, 아래와 같이 표현할 수 있다.

/*
 * 1. arr이 빈 배열인 경우 = 0
 * 2. 그 외의 경우 = arr[0] + arrSum(arr2)
 *   (arr2는 arr의 첫 요소를 제외한 나머지 배열)
 */
arrSum(arr);

위에서 볼 수 있듯 함수 arrSum 은 (인자가 빈 배열이 아닌 경우) 실행과정 중에 자기 자신을 호출하는데, 이러한 호출 방식을 재귀 호출이라고 한다.

 

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

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다. 

또한 재귀는 알고리즘 문제의 많은 부분을 차지한다. 앞으로 만나게 될 다양한 기업의 입사 시험(코딩 테스트, 알고리즘 테스트 등)이나 직무면접에서 활용할 수 있기 때문에, 기초를 확실하게 다져두는 게 필요하다.

 

(오늘만 해도 알고리즘을 푸는데, 내 머리가 전혀 익숙하지 않아 그냥 멍하니 앉아있던 내 자신을 발견했다. ㅠㅠ 일단 머리가 익숙해지기 위해 어떻게든 알고리즘을 풀기 위한 머리 근육을 키워내는 것이 중요하다!!!!!!!!!)

 

재귀적으로 생각하기 위한 연습이 필요할 때, 도입할 수 있는 필터를 적어본다.

Guide : 재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

 

내가 재귀 함수를 통해 풀고자하는 문제에 임했을 때, 입력값과 출력값이 무엇인지 정확하게 정의해놔야 한다.

그 이유는 어떤 복잡한 문제를 맞이하게 되더라도, 최대한 단순한 파트까지 조각조각내서 그 부분을 해결해낸다면, 결국 그 단순한 파트부터 시작하여 복잡한 문제가 해결이 되는 수순이기 때문이다.

예시를 들자면, 함수 arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받는다 그리고 number 타입을 리턴한다는 것을 간단하게 표현 해보는 것이다.

• arrSum: [number] => number

2. 문제를 쪼개고 경우의 수를 나누기

 

A. 주어진 문제를 어떻게 쪼갤 것인지 고민한다.

B. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.

C. 일반적인 경우, 입력값으로 이 기준을 정하는데, 이때 중요한 관점은 입력값이나 문제의 순서와 크기! 

D. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다.

E. 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면, 문제를 제대로 구분한 것이다.

 

예를 들어보면,

• 함수 arrSum 의 경우 입력값인 리스트(배열)의 크기(배열의 길이)에 따라, 더 작은 문제로 나눌 수 있다. 그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.

이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나누어 진다.

• 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다.
• arrSum: [number] => number
  arrSum([ ])
  arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기

 

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)이라고 부른다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

• 함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0
• arrSum: [number] => number (입력값과 출력값 정의)
• arrSum([ ]) = 0 (경우의 수로 나눈다) ==> 빈배열인 경우
• arrSum([e1, e2, ... , en])  (경우의 수로 나눈다) ==> 빈배열이 아닌 경우

4. 복잡한 문제 해결하기

 

남아있는 복잡한 경우를 해결하는 방식

 

길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고 (두 번째 Dot)

배열의 맨 앞의 요소와, 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과에 다시 나머지 요소를 새로운 입력값으로 구분해준다. (세 번째 Dot)

• arrSum: [number] => number
  arrSum([ ]) = 0
• arrSum([e1]) = e1 + arrSum([ ])
• arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])

두 번째 Dot, 세 번째 Dot의 부분을 구분해낼 수 있다면, arrSum 함수를 포함한 재귀함수의 조건에 들어맞는 여러 함수들을 재귀적으로 구현해낼 수 있다.

 

5. 코드 구현하기

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}

위의 코드는 단계적으로 나눈 코드들을 확인할 수 있다. 아래 코드는 재귀함수를 적용할 때 좋은 틀이다. 이것을 토대로 재귀함수를 구현해보자.

function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

아래 factorial 함수를 실제로 코드상으로 구현해보자. 만일 4!을 구현하고 싶다하면, 어떤식으로 될까?

4 * 3 * 2 * 1 -> 4 * 3! -> 3 * 2 * 1 -> 3* 2! -> 2 * 1

이런식으로 서서히 단위를 작게 나눌 수 있다. 2!까지는 존재하지만 1!은 결국 1이기에 문제를 더 이상 쪼갤 수 없다.

따라서 위의 틀에 입력해보면,

function facto(n){
	if(n === 1){
    	return 1}
}        

이렇게 초기 값을 작성해줄 수 있다. 그럼 그 다음은? 각 부분들을 확인하며 어떤 규칙이 있는지 확인하고, 그것에 대한 코드를 만들어준다.

function facto(n){
	if(n === 1){
    	return 1}
	return n*facto(n-1)   
    // 4에 3!을 곱한다. 4*facto(3)
    // 3에 2!을 곱한다. facto 함수에 3이 들어갔다. 따라서 4*3*facto(2)로 또 나눠진다.
    // 2에 1!을 곱한다. facto 함수에 2가 들어갔다. 따라서 4*3*2*facto(1)로 구분된다.
    // 근데 facto 함수에서는 n이 1이면 1을 리턴하게 된다. 따라서 4*3*2*1로 결과가 나오게 되는 것이다.
}        

위처럼 자기 자신을 계속 참조하여 문제를 해결하는 것이 재귀함수이고, 가장 중요한 포인트는 가장 작은 단위를 찾아내면서 규칙을 찾아내는 것!