[JavaScript]재귀

❓재귀 함수(Recursion Function)란?

자기 자신을 다시 호출해 작업을 수행하는 방식이다.

아래의 코드를 보면 리턴 문을 사용해 rezero함수가 끝나기 전에 다시 함수를 호출해 주고 있다.

function rezero(){
console.log('무한반복중')
return rezero()
}

특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

 

이러한 제귀 함수의 가장 큰 사용 예제는 바로 팩토리얼이다.
(수학 시간에 배웠던 5!라는 문자를 생각해 봅시다....)

function factorial(num) { 
    if (num === 1) { 
        return 1; 
    } 
    //num이 1이 되었을때 함수 끝내기
    
    return num * factorial(num-1);
    //num값에 1씩 빼주면서 factorial함수를 다시 리턴해주고 그 값을 num에 곱해주는 방식이다
}

솔직히 나 스스로도 이해가 잘 되지 않는 식이다......(num이 두 개?...)
이를 좀 더 이해하기 쉽게 그림으로 해당 코드가 수행될 때의 콜 스택을 살펴보자.

👇만약 함수의 인자를 5로 넣을 경우......(5*4*3*2*1이 나오는 과정이다)

리턴하면서 하나씩 원래 값에서 분산시킨다고 생각하면 편할 겁니다.

5! === 5*4!
5! === 5*4*3!
5! === 5*4*3*2!
5! === 5*4*3*2*1

즉 계산하기 쉽게 축약된 식을 펼치는 것입니다.

 

❓Why we use Recursion Function

👌재귀 함수로 모든 반복문을 표현 가능하고 그 반대도 가능합니다.

❓그렇다면 재귀 함수는 왜 사용할까요? 이유는 바로 다음과 같습니다.

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

수많은 for문으로 인해 가독성이 떨어지고 for문 hell이 만들어진 것을 볼 수 있습니다.😫

👉재귀는 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우 사용합니다.
앞으로 만나게 될 다양한 과제와 기업의 입사 시험(코딩 테스트, 알고리즘 테스트 등)이나 직무면접에서 활용할 수 있기 때문에, 기초를 확실하게 다져두는 게 바람직합니다.

 

 

 

❓How to use?

재귀 함수의 사용법은 문제를 어떻게 더 작게 쪼개는 가에 있습니다.
문제를 쪼개고 쪼갠 문제를 반복해서 쪼개게 되면 더 이상 쪼갤 수 없는 상태에 도달하게 됩니다.
그러면 비로소 가장 작은 단위의 문제를 해결합니다.

arrSum([]) === 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;

arrSum 함수의 리턴 값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결되는 것을 볼 수 있습니다.

 

📌분해하고 결합시키기

 

 

📌Case

재귀적으로 문제를 정리할 때는 base case와 Recursive case를 생각해야 한다.

• base case(문제를 더 이상 쪼갤 수 없을 경우)

  //빈 배열의 경우
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  
  //더이상 쪼갤수 없는 경우
   if (num<0)
    return 문제의 해답
  }

• recursiv case(그렇지 않은 경우 문재가 더 쪼개질 경우)

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  }
  
  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);

 

 

❗주의할 점❗

재귀 함수는 무한 반복문으로 사용이 가능하기 때문에 무한 반복 시 에러가 발생할 수 있다.

 

Stack Overflow Error: 콜스택이 너무 많이 쌓여 한계점에 도달했을 때 에러가 발생한다.

Call Stack: 컴퓨터 프로그램에서 현재 실행 중인 서브루틴에 관한 정보를 저장하는 스택 자료구조
즉, 함수가 끝나면 다시 돌아올 위치를 기록해 두는 곳
함수를 재귀적으로 너무 많이 호출하게 되면 콜 스택이 계속해서 쌓이면서 더 이상 기록할 공간이 없어지게 됨 
=>  프로그램 중단