04. 재귀함수 (Recursive Call)

정의

재귀용법(=재귀함수) 란?
- 함수 안에서 동일한 함수를 호출하는 형태
- 재귀 호출은 스택의 전형적인 예이다
   - 함수는 내부적으로 스택처럼 관리된다

TIP
고급 정렬 알고리즘에서 재귀용법을 사용하므로 고급 정렬 알고리즘을 익히기 전에 재귀용법을 먼저 익히는 것이 좋다

 

재귀 용법의 이해 (예시 - 팩토리얼)

- factorial(num) 은 서번의 factorial 함수를 호출해서 곱셈을 한다

- 일종의 num - 1 번의 반복문을 호출한 것과 동일하다

- factorial () 함수를 호출할 때 마다 지역변수 num 이 생성된다

- 시간 복잡도 O(num-1) , 공간 복잡도 O(num) 이므로 둘 다 O(n) 이다

 

재귀함수 (Recursive Call)

public class RecursiveCall {
 
    public static void main(String[] args) {
 
        int result = factorial(5);
 
        System.out.println(result);
 
    }
 
    private static int factorial(int num) {
        // 5 * factorial(4) * factorial(3) * factorial(2) * factorial(1)-1
        if (num < 2) {
            return 1;
        } else {
            return num * factorial(num - 1);
        }
    }
}

 

패캠 강의 풀이

public class RecursiveCall2 {
    public static void main(String[] args) {
 
        int result = factorial(5);
 
        System.out.println(result);
 
    }
 
    private static int factorial(int num) {
        if (num > 1) return num * factorial(num - 1);
        else return num;
    }
}