[ALGORITHM] 재귀 호출

재귀 호출 

• 함수 안에서 동일한 함수를 호출하는 방법
• 여러 알고리즘 작성시 사용됨
• 재귀 호출은 스택의 전형적인 예 (호출함수가 내부적으로 스택처럼 관리됨)
• 재귀 호출은 중단하기 위한 종료조건문이 필수 

---

재귀 호출 특징

• 코드가 간결함
• 무한 재귀호출의 위험성 (종료조건 실수할 경우), 성능상의 문제

---

재귀 호출 대표적인 예시 (팩토리얼)

public int factorial(int n) {
    if (n == 1) {
      return 1;
    }
    return n * factorial(n-1);
}

• 규칙 : n! = n x (n - 1)!, f(1) = 1
• factorial(n)은 n - 1 번의 factorial() 함수를 호출하여, 곱셉을 함 (n - 1번 반복문을 호출한 것과 동일한 형태)
• factorial() 함수를 호출할 때마다 지역변수 n이 생성
• 시간복잡도 공간복잡도 O(n - 1)이므로 둘다 O(n)

---

재귀 호출 (팩토리얼) 원리

팩토리얼 호출 원리 

• 함수 호출이 발생하면 이전변수가 스택에 저장
• 기본 케이스에서 호출 함수로 값을 반환

---

재귀 호출은 주요 알고리즘의 기본이 되기 때문에 이해 필수임