[Algorithm] 재귀 용법 (recursive call)

Posted: 2023.03.03     Updated: 2023.03.03

재귀 용법 (recursive call, 재귀 호출)

• 고급 정렬 알고리즘에서는 재귀 용법 사용

1. 재귀 용법

• 함수 안에서 동일한 함수 호출
• 스택의 전형적인 예
• 내부적으로 스택처럼 관리됨
• 파이썬에서는 재귀 함수의 깊이가 1000회 이하여야 함

2. 재귀 용법 예시

팩토리얼 구하기

2! = 1 x 2
3! = 1 x 2 x 3
4! = 1 x 2 x 3 x 4

n! = n x (n - 1)!

public int factorial(int num) {
    if (num <= 1) return 1;
    else return num * factorial(num - 1);
}

• 시간 복잡도 O(n)
  • factorial 함수를 n-1 번 호출해서 곱셈
  • n-1 번 반복문 호출한 것과 동일
• 공간 복잡도 O(n)
  • factorial 호출할 때마다 지역변수 n 생성

3. 재귀 호출의 일반적인 형태

일반적인 형태 1

public int function(입력) {
    if (입력 > 일정값)    // 입력이 일정 값 이상이면
        return function(입력 - 1);    // 입력보다 작은 값
	else
        return 일정값;    // 재귀 호출 종료
}

일반적인 형태 2

public void function(입력) {
    if (입력 <= 일정값)    // 입력이 일정 값보다 작으면
        return 결과값;    // 재귀 호출 종료
    function(입력보다 작은 값);    // 재귀 호출 종료
    return 결과값;
}

public int factorial(int num) {
    if (num <= 1) return num;
    else return num * factorial(num - 1);
}