[알고리즘] 재귀함수 활용해보기

[알고리즘] 재귀함수 활용해보기

 

-재귀함수의 특성

• 함수가 자기 자신을 호출한다
• 함수호출시 스택프레임이 생성되어 스택에 담긴다.(모든 함수의 특성)

 

재귀함수는 그 특성을 이해하면 다양한 방식으로 활용할 수 있다.

하지만 성능이 반복문보다 떨어지기에 제한적으로 사용해야한다.

 

재귀함수는 자신을 호출하는 함수기 때문에 기본적으로 이를 멈추기위한 방법이 있어야함. 안그럼 무한히 호출된다. 

기본적인 틀은 비슷하기때문에 외워두는 것이 좋다.

 

 

 

 

 

1.  오름차순 수열 출력해보기

재귀함수를 활용해서

1 2 3 4 5 6 7 8 9 10.. 이런식으로 오름차순으로 출력해보기

public static void DFS_desc(int n){ // 내림차순 출력하는 재귀함수
    if(n==0) return;
    else{
        System.out.print(n+" ");
        DFS(n-1);
    } 
}

public static void DFS_asc(int n){ // 오름차순 출력하는 재귀함수
    if(n==0) return;
    else{
        DFS(n-1);
        System.out.print(n+" ");
    } 
}

public static void main(String[] args){
    DFS_desc(45) // 45 44 43 42 41 ... 1 출력
    DFS_asc(45); // 1 2 3 4 5 ... 45 출력
}

 

 

 

 

왜 재귀함수 내 명령어 순서에 따라 다른순서로 출력될까?

• 스택 프레임

-> 함수 호출시 함수 실행에 필요한 정보(매개변수, 지역변수, 반환주소)를 저장하는 메모리 공간. 함수가 호출될 때마다 새로운 스택프레임이 생성되어 스택구조에 쌓인다. 스택구조의 특성상 LIFO(Last In First Out) 후입선출 구조로 동작한다.

 

 

오름차순으로 출력할때, print문보다 다음번 재귀함수의 호출이 먼저 일어나게 된다. 그렇다면 스택프레임에 DFS(45)부터 DFS(44) DFS(43)... DFS(1)까지 쌓이게된다. 함수호출 스택프레임은 이름에서 보듯 스택으로 이루어져있어서 가장 늦게들어온 DFS(1)부터 차례대로 실행되게 된다. 즉, 함수 호출자체는 45부터 1까지 내림차순으로 이루어지지만 함수의 실행과 출력은 1부터 45까지 오름차순으로 실행되는 것이다. 그 결과 1 2 3 4....45까지 차례대로 출력되는것이다.

 

반대로 내림차순으로 출력할때는 print문이 다음 재귀함수의 호출보다 먼저 실행되므로 숫자가 먼저 출력된다. 스택프레임에 동일하게 쌓이더라도 함수의 호출 순서에 따라 내림차순으로 45 44 43....1 이렇게 출력된다.

 

 

 

 

2. 이진수 출력하기

2로 나눈 나머지값을 역순으로 반환. 나눈몫이 0이라면 중단.

 

 public static void DFS(int n){
        if(n==0) {
            return;
        }
        else{
            DFS(n/2);
            System.out.print(n%2);
        }
    }
    public static void main(String[] args){
        DFS(11);
    }

 

 

 

3. 팩토리얼

public static int DFS(int n){
    if(n==1) return 1;
    else {
        return n * DFS(n-1);
    }
}
public static void main(String[] args){
    System.out.print(DFS(5));
}

 

 

4-1 피보나치 수열

1번째 - 45번째 피보나치 수열 반환시 8s소요

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

    public static void main(String[] args){
        int n = 45;
        for(int i=1; i<=n; i++){
            System.out.println( DFS(i) + " ");
        }
    }
}

 

 

4-1 피보나치 수열 - 배열사용

1번째 - 45번째 피보나치 수열 반환시 4s소요

public class Main {
    static int[] fibo;
    public static int DFS(int n){
        if(n==1) return fibo[n] = 1;
        if(n==2) return fibo[n] = 2;
        else return fibo[n] = DFS(n-1) + DFS(n-2);
    }

    public static void main(String[] args){
        int n = 45;
        fibo = new int[n+1];
        DFS(n);
        for(int i=1; i<=n; i++){
            System.out.println(fibo[i] + " ");
        }
    }
}

 

 

4-2 피보나치 수열 - memoization

1번째 - 45번째 피보나치 수열 반환시 183ms소요

public class Main {
    static int[] fibo;
    public static int DFS(int n){
        if(fibo[n]>0) return fibo[n];
        if(n==1) return fibo[n] = 1;
        if(n==2) return fibo[n] = 2;
        else return fibo[n] = DFS(n-1) + DFS(n-2);
    }

    public static void main(String[] args){
        int n = 45;
        fibo = new int[n+1];
        DFS(n);
        for(int i=1; i<=n; i++){
            System.out.println(fibo[i] + " ");
        }
    }
}