[Algorithm] 재귀함수 기본(팩토리얼, 피보나치수열)

재귀함수란

자기자신을 호출하는 함수, 반복문의 형태

 

아래의 DFS(int n)함수는 내부에서 자기자신을 호출하는 재귀함수이다.

    public void DFS(int n){
        if(n==0) return;
        else {
            DFS(n-1); // 자기자신 호출
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(3);
    }

retrun은 값을 반환해주는 역할이지만 void에서는 함수 종료의 의미도 갖고있다.

처음에는 if ~ else 조건으로 종료 조건을 사용하여 연습하는 것이 좋다고 한다. -> 무한루프 방지

 

재귀함수는 스택프레임을 사용한다.

T.DFS(3)을 호출하면 호출하는 순서대로 아래의 그림처럼 스택메모리에 프레임형태로 담긴다.

DFS(1)

DFS(2)

DFS(3)

스택메모리에는 호출된 함수의 매개변수, 지역변수, 함수가 끝나고 돌아갈 반환 주소값 등이 저장된다.

이처럼 재귀 함수는 메모리를 많이 차지하기에 반복문에 비해 성능이 좋지 않다.

 

---

 

코드로 간단하게 알아보자.

 

재귀함수는 함수를 언제 호출 하느냐에 따라 출력되는 값이 달라진다.

아래 두 코드의 차이를 보자.

    public void DFS(int n){
        if(n==0) return;
        else {
            System.out.printf(n+" ");
            DFS(n-1); // 자기자신 호출
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(3);
    }

입력 : 3

출력 : 3 2 1

    public void DFS(int n){
        if(n==0) return;
        else {
            DFS(n-1); // 자기자신 호출
            System.out.printf(n+" ");
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(3);
    }

입력 : 3

출력 : 1 2 3

 

전자는 n값 출력 -> 함수 호출  -> n값 출력 -> 함수 호출 -> n값 출력 -> 함수 호출

후자는 함수호출 -> 함수호출 -> 함수 호출 -> n값 출력 -> n값 출력 -> n값 출력

 

즉 후자는 DFS(n-1)함수가 스택의 최상단까지 도달 하면 LIFO(후입선출) 순서로 스택프레임을 pop(소멸) 시킨다.

이때 소멸된 순서대로 각 함수의 돌아갈 반환 주소값(위의 로직에서는 System.out.printf(n+" ") 라인)에 도착한다.

 

---

 

재귀함수를 응용한 몇가지 방법들을 살펴보자.

 

1. 재귀함수를 이용한 팩토리얼

    public int DFS(int n){
        if(n==1) { // n == 1을 스택의 최상단으로 지정.
            return 1; // 스택에 최상단에 도착 시 1을 반환한다.
        }
        else{
            return n*DFS(n-1); // 5*4*3*2*1
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        int result = T.DFS(5);
        System.out.println(result); // 120
    }

 

---

 

2. 재귀함수를 이용한 피보나치수열

(가끔 코딩인터뷰에서 피보나치를 배열과 재귀함수로 구현해보라 한다고 들었다..)

    public int DFS(int n) {
        if(n==1 || n==2) return 1;
        else return DFS(n-2) + DFS(n-1);
    }

    public static void main(String[] args) {
        Main T = new Main();
        int n = 5;
        for (int i = 1; i <= n; i++) { // n값 최소 1부터 시작.
            System.out.printf(T.DFS(i)+" ");
        }
    }

입력 : 5

출력 : 1 1 2 3 5

 

피보나치수열의 경우 위의 로직처럼 구현할 경우 입력값이 커질 수록 동일한 계산을 반복적으로 계산 하기 때문에 기하급수적으로 시간복잡도가 증가한다.

: 피보나치수열을 재귀함수를 이용하여 이렇게 구현할 수 있구나 정도만 알고 있자.

 

만약! 더 나아가 시간 복잡도를 줄이고 싶다면 메모이제이션을 사용하면 된다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

동적 계획법 의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.

 

3. 재귀함수를 이용한 피보나치수열 (메모이제이션 활용)

    static int[] fibo; // 배열에 구한값을 담아둔다.
    public int DFS(int n) {
        if(fibo[n] > 0) return fibo[n]; // fino[n] 0보다 크다면 이미 구한 값이다.
        if(n==1 || n==2) return fibo[n] = 1;
        else return fibo[n] = DFS(n-2)+DFS(n-1);

    }
    public static void main(String[] args) {
        Main T = new Main();
        int n = 45;
        fibo = new int[n+1]; // 인덱스 번호로 필요하기 때문에 +1 , 0번은 필요 없다.
        T.DFS(n);
        for (int i = 1; i <= n; i++){
            System.out.printf(fibo[i] + " ");
        }
    }

배열 생성 시 크기 n만큼 0으로 초기화 되는 방식을 이용하여 fibo[n] > 0일 경우 이미 구해진값 이라고 판단하고 재귀함수를 계속적으로 호출하여 스택프레임을 최상단까지 쌓을 필요 없이 바로 fino[n]값을 retrun해준다.

 

---

 

정리

:  다양한 재귀함수 알고리즘 예제를 접해볼 필요가 있는 것 같다..