출처: 위키백과

---

👊 재귀(recursion)함수란? 자기 자신을 호출하는 함수

종료 조건이 충족될때까지 반복적으로 스스로를 불러내면서 주어진 작업을 수행한다.

❗️재귀함수는 반복문으로도 대체가 가능하다. 그렇다면 반복문을 사용하면 될텐데 왜 재귀함수를 사용하는것일까?
일반적으로 [1,2,3,4,5,6,7,8,10]이런식으로 배열이 나와있다면 반복문을 돌리면 쉽지만, 만약 [1,2,3,[4,5,[6,7]],8,9,10] 이런식으로 배열 안에 배열 안에 배열 이런식이라면 반복분 안에 반복문,또 그안에 반복문.. 이런형식으로 복잡한 형태가 만들어질것이다. 이럴때 반복문을 사용하는것보다 재귀를 사용하면 매우 적절하다. 아래와 같은 경우

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. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운경우

👊 재귀 특징

1. 모든 재귀 함수는 반복문으로 표현할 수 있다. 그러나 재귀를 적용하는 경우가 더욱 간결하고 이해하기 쉽다.
2. 재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때까지 실행하는 패턴으로 볼 수 있다.(Recursive Case)
3. 재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야한다.

👊 재귀의 장점과 단점

장점 : 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋다.
단점 : 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용한다.

자연수로 이루어진 배열의 합을 구하는 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;

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

// 4! 구하기

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

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

자료출처
코드스테이츠
https://www.youtube.com/watch?v=aPYE0anPZqI