[재귀함수] 재귀함수 기초 - 2

public class Recursive2 {
    // 2진수 출력
    public static void main(String[] args) {
        Recursive2 rc = new Recursive2();
        rc.DFS(11);
    }

    public void DFS(int n){
        if(n == 0){
            return;
        }else{
            DFS(n / 2);
            System.out.print(n % 2 + "");
        }

    }
}

2진수는 2로 나누면서 나머지 값을 왼쪽 부터 출력하기 떄문에

스택에 넣어서 제일 낮은값 부터 찍어주면 된다 그러므로 출력부분이 아래 오게 해주면 된다!

 

public class Recursive3 {
    public static void main(String[] args) {
        Recursive3 rc = new Recursive3();
        System.out.println(rc.DFS(5));
    }
    public int DFS(int n){
        if(n == 0){
            return 1;
        }else {
            n = n * DFS(n - 1);
        }
        return n;
    }
}

팩토리얼 찍는 문제

처음에는 sum 함수를 따로 주려고 했는데 

그럴필요 없이 n이 0으로 가면 팩토리얼은 마지막에 1을 주기 때문에 1을 반환하고 그 1 값을 가지고

누적해서 곱해준다

그러면 처음에 5가 들어왔을때

 

5 = 5 * DFS(4) ※ DFS(4) = 4 * DFS(3)

이런식으로 누적해서 곱해주기때문에

5 * 4 * 3 * 2 * 1 을 만들어 줄 수 있다!

 

        }else {
            return n * DFS(n - 1);
        }

else 부분을 이런식으로 바꿔줄 수 있다

 

public class Recursive4 {
    public static void main(String[] args) {
        Recursive4 rc = new Recursive4();
        int n = 10;
        for(int i=1; i<=n; i++){
            System.out.print(rc.DFS(i) + " ");
        }
    }
    public int DFS(int n){
        if(n == 1 || n == 2){
            return 1;
        }else {
            return DFS(n-1) + DFS(n-2);
        }
    }
}

피보나치 재귀

 

많이 해봤으므로 ... 마찬가지로 반복문으로 재귀함수를 이용해서 출력해 줄 수 있음

근데 알고리즘에서 풀어봤듯이 이렇게 풀면 나중가면 재귀를 너무 많이타서 시간 초과가 나올 수 있으므로 

배열을 이용해서 풀자!!