[자료구조/알고리즘] 재귀

출처 : 위키백과

 

---

 

👊 재귀(Recursion)

정의:   자신을 정의할 때 자기 자신을 재참조하는 방법

(어떤 함수가 스스로를 호출하는것)

 

자연수로 이루어진 배열의 합을 구하는 arrSum (재귀적으로 생각해서 구하기)

arrSum([1, 2, 3, 4]) = 1 + arrSum([2, 3, 4]);
arrSum([2, 3, 4]) = 2 + arrSum([3, 4]);
arrSum([3, 4]) = 3 + arrSum([4]);
arrSum([4]) = 4 + arrSum([]);
arrSum([]) = 0;

쪼개서 생각하고 또 쪼개서 생각하는걸 볼 수 있음

 

🎟 모든 재귀 함수는 반복문으로 표현할 수 있다. 그러나 재귀를 적용하는 경우가 더욱 간결하고 이해하기 쉽다.

🎟 재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때까지 실행하는 패턴으로 볼 수 있다. (Recursive Case)

🎟 재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야한다. 

 

// 4! 구하기

function fac(n) {
// Base Case
// n이 0이면 재귀를 더 이상 진행하지 않는다.

	if(n === 1) {
    	return 1
    }
// Recursive Case    
    return n * fac(n-1);
}

 

출처: 코드스테이츠  fac(4) = 24

 

---

👊 재귀를 사용하기에 적합한 경우

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

---

👊 재귀의 장점과 단점

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

단점 : 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용한다.