[D+29] 재귀함수

 

 

D+29

-  재귀함수 -

(재귀)

 

---

 

 

재귀 (Recursion)

•어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 먼저 해결함으로써 그 문제를 해결하는 방법

 

•함수 스스로를 호출하는 것

 

 

재귀 이해하기

Q. 자연수로 구성되어 있는 배열을 입력받아 배열의 합을 리턴하는 함수 'arrSum'을 작성해라.

만약 해당문제를 직면하게 될 경우 우리는 어렵지 않게 'for문'을 사용해 문제를 쉽게 해결할 수 있을 것이다.

 

function arrSum(arr) {
  let sum = 0;
  for(let i = 0; i < arr.length; i++) {
    sum = sum + arr[i];
  }
  return sum;
}

예로들면, arr에 [10, 3, 6, 2]가 입력되었을 경우 '10 + 3 + 6 + 2'로 '21'이 리턴될 것이다.

 

이처럼 우리는 반복문을 통해 문제를 해결할 수 있지만

'for문' 말고도 해결할 수 있는 방법이 있는데 그것은 바로 '재귀함수'를 이용해 푸는 방법이다.

 

일단 문제를 본격적으로 풀기 전에 재귀의 방식으로 문제를 쪼개서 생각할 필요가 있다.

 

 

1. 문제를 쪼개서 계산을 시도한다.

// 문제를 한번에 해결하는 것이 아닌 쪼개서 나누어서 생각해 본다.

arr([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);

 

2. 문제가 작아지지 않을 때 까지 더 작은 경우를 생각한다.

// 내가 입력한 배열이 끝이 보일때 까지 과정을 거친다.

arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);

 

3. 문제가 간단명료해져서 풀 수 있게 되었을 경우에 문제를 차근차근 해결해 준다.

 

이때에 주의할 점은 재귀는 종료지점을 만들어 주지 않으면 에러가 나지 않는 이상 계속 실행되기때문에

종료지점을 정해주는 것을 잊지 말아야 한다.

arrSum([]) = 0; // 문제가 더이상 작아지지 않는 순간

// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 2

 

이런 식으로 해당 과정을 거치게 되면 재귀함수를 만들 수 있게 된다.

function arrSum(arr) {
  if(arr.length === 0) { // 재귀함수가 끝날 지점을 제시
    return 0;
  }
  let head = arr[0];
  let tail = arr.slice(1);
  return head + arrSum(tail);
}

 

 

재귀의 장단점

•장점

알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋다.

 

•단점

값이 리턴되기 전까지 호출마다 call stack을 새로 생성하기 때문에

메모미를 많이 사용하게 된다.

 

 

재귀를 사용하는 경우

•주어진 문제가 반복적이고 더 작은 문제로 나뉘어 질 수 있는 경우

 

•중첩된 루프가 많거나 중첩의 정도를 미리 알기 어려운 경우

 

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);
                           }
                        }
                    }
                }
            }
        }
    }
 }

모든 재귀함수는 while이나 for문을 통해 표현이 가능하지만 사용하지 않을 경우 위의 경우처럼

무한한 식을 일일히 입력하는 경우가 발생될수도 있기 때문에 재귀를 사용하는 것이 가독성이 좋을 뿐만 아니라

간단하다.