[알고리즘] 재귀 함수

 

 

 

📌 재귀

 

 

📍재귀의 이해

 

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

 

🔗 재귀의 코드

 

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

 

recursion() 함수?

자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행된다

 

 

👉🏼 이 함수처럼 자기 자신을 호출하는 함수를 재귀 함수라고 한다

 

 

 

🔗  재귀로 문제 해결하기

 

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

 

 

1. 문제를 작게 쪼개기

 

[1, 2, 3, 4, 5] 의 합을 구하는 과정

 

1 + 2 + 3 + 4 + 5 =?

2 + 3 + 4 + 5 =?

3 + 4 + 5 =?

4 + 5 =?

...

 

위 방식으로 문제를 쪼갠것을 코드로 표현

 

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

 

 

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

 

...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([]) // 더 이상 쪼갤 수 없는 상태

 

 

3. 문제 해결하기

 

가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결

 

arrSum([]) === 0; // <-- 가장 작은 문제를 빈 배열의 합 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;

 

작성 코드

 

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}

 

 

 

🔗  재귀 사용 예시

 

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

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

 

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

 

 

 

📍 재귀의 활용

 

🔗  재귀적으로 사고하기

 

 

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

 

추상적, 또는 가장 단순하게 정의

함수의 입출력값을 정의 -> 재귀 함수를 통해 목표 정의

 

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

 

문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분

구분 기준은 "입력값이나 문제의 순서와 크기" 이다

 

 

3. 단순한 문제 해결하기

 

문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결

👉🏼  재귀의 기초

재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성

탈출 조건이 없다면? 끝없이 자기 자신을 호출

 

 

4. 복잡한 문제 해결하기

 

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

 

5. 코드 구현