TIL-2024.03.08 - 재귀함수

 

------- 재귀함수

 

설명:

• 함수가 자기 자신을 호출하는 방식으로 정의되는 함수.
• 재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복.
•  재귀함수로 작성이 되는 코드는 반복문으로도 작성

 

특징: 

1. 자기 자신을 호출: 재귀 함수는 자신을 호출
2. 베이스 케이스(Base Case):
   > 재귀 함수는 무한히 호출되지 않도록 멈추는 조건이 필수.
   > 베이스 케이스를 지정하지 않으면 함수가 무한히 호출되며 스택 오버플로우(Stack Overflow)가 발생.
3. 작업을 작은 문제로 분할: 재귀 함수는 하나의 큰 문제를 해결하는 대신 작은 부분 문제로 분할하고 각 부분 문제는 동일한 함수에 대한 재귀 호출을 통해 해결.
4. 스택 사용: 재귀 함수는 호출 스택(Call Stack)을 사용하여 호출된 순서를 추적. 각 재귀 호출은 스택에 새로운 프레임을 추가하고, 함수가 반환되면 해당 프레임이 스택에서 제거.

 

작동 원리:

// 100까지 더하기

function f(n) {
    if (n <= 1) {
       return 1 // 종료 조건
    }
    return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050

// 재귀함수
// 순번   f(n)   n      return       최종
// 1   f(100)  100  100 + f(99)  100+99+98+97+96+95+94..+2+1   
// 2   f(99)   99   99 + f(98)   99+98+97+96+95+94..+2+1 
// 3   f(98)   98   98 + f(97)   98+97+96+95+94..+2+1 
// 4   f(97)   97   97 + f(96)   97+96+95+94..+2+1 
// ...
// 99  f(2)    2    2 + f(1)    2+1
// 100  f(1)    1    1 // return값이 자기 자신을 호출하지 않는 상황

 

 

 

예제:

 

// 팩토리얼

function factorial(n) {
    // 베이스 케이스: n이 0 또는 1일 때, 1을 반환
    if (n === 0 || n === 1) {
        return 1;
    } else {
        // 재귀 호출: n * (n-1)의 팩토리얼을 재귀적으로 호출하여 구함
        return n * factorial(n - 1);
    }
}