[JS 알고리즘 - 재귀2] 재귀 함수의 작성 조건

아래 강의를 듣고 내용을 정리한 포스트 입니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass

이번 글에서는 재귀 함수를 작성할 때 반드시 고려해야 하는 두 가지 전략에 대해 알아보겠습니다.

1. 종료 조건의 존재

재귀 함수를 작성할 때 가장 중요한 것 중 하나는 종료 조건(base case)을 설정하는 것입니다. 종료 조건은 재귀가 멈추는 시점으로, 루프에 중단점이 있어야 하는 것처럼 재귀적으로 무한히 호출하지 않도록 해야 합니다. 중단점이 없으면 영원히 계속되면서 컴퓨터에 악영향을 미칠 수 있습니다.

2. 매번 더 작은 입력값

재귀 함수를 작성할 때 또 다른 중요한 전략은 매번 더 작은 입력값을 사용하는 것입니다. 동일한 함수를 계속 호출하면서 하나의 함수가 자기 자신을 재귀적으로 호출하게 하되, 매 호출마다 더 작은 입력값을 사용해야 합니다. 이렇게 하면 재귀 함수는 매번 더 작은 양의 데이터에서 계속 호출되다가, 종료 조건에 도달하면 실행이 중단됩니다.

예시 1 :

  

    
    
    
    
  
// 0 이 되기 전까지 숫자를 하나씩 내려가며 출력하는 함수 countDown 을 재귀함수로 작성
// 0 이 되면 All done! 을 출력하고 함수가 종료 되어야함
countDown(5) // 5 4 3 2 1 All done!

  

    
    
    
    
  
function countDown(num){
    // 종료 조건이 없었다면, 이함수는 계속해서 음수로 내려가서 무한히 숫자를 console 에 출력했을것이다.
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    // 매번 더 적은 입력값으로 자기자신을 호출한다.
    countDown(num);
}
countDown(5) // 5 4 3 2 1 All done!

 

예시 2 : 

  

    
    
    
    
  
// 주어진 정수를 1이 될때까지 모두 합산하는 함수. 4 + 3 + 2 + 1 과 같음.
sumRange(4) // 10

  

    
    
    
    
  
function sumRange(num){
   // base case : 입력이 1이면 1을 반환하고 재귀를 종료
   if(num === 1) return 1; 
   // 매번 더 작은 값을 가지고 호출
   // (4 + sumRange(3)) + (3 + sumRange(2)) + ... 과 같음.
   return num + sumRange(num-1);
}

sumRange(4) // 10
// return 4 + sumRange(3)
//             return 3 + sumRange(2)
//                          return 2 + sumRange(1)
//                                       return 1
// 이와 같이 작동하며, 호출스택의 최상위에 있는 sumRange(1) 부터 실행되어 
// 마지막에는 return 4 + 6 과 같은 결과가 나오게 된다.

예시 3

고전적인 예시인 팩토리얼을 반복문과 재귀호출로 비교해보겠습니다.

팩토리얼은 수식으로 다음과 같이 표현할수 있습니다

  

    
    
    
    
  
4! = 4 * 3 * 2 * 1

 

이제 이 팩토리얼을 반복문을 통해 구현하게되면, 아래와 같습니다.

  

    
    
    
    
  
function factorial(num: number){
    let total = 1;
    for(let i = num; i > 1; i--){
        total *= i
    }
    return total;
}

console.log(factorial(4)) // 24

 

이것을 재귀호출을 통해 구현해보겠습니다.

그전에 종료 조건과 재귀 호출이 사용되는 매 함수 로직을 살펴보게되면,

factorial(3) 은 3 * factorial(2) * factorial(1) 과 같고, factorial(2) 는 2 * factorial(1) 과 같습니다.

결론적으로, num 에 factorial(num-1) 을 곱한 값을 반환 시켜야 할것입니다.

  

    
    
    
    
  
function factorial(num: number){
    return num * factorial(num-1);
}

하지만 이상태로는, 종료조건이 없어 num 이 0 이하의 음수까지 계속 내려가서 무한히 반복 될것입니다. 따라서 아래와 같이 종료 조건을 지정해 주겠습니다.

  

    
    
    
    
  
function factorial(num : number){
    if(num === 1) return 1;
    return num * factorial(num-1);
}

console.log(factorial(4)); // 24