Recursion_재귀 함수

🔵 ThingsILearned

✔️ 재귀함수 멈추기

함수 내부에서 함수가 자기 자신을 또 다시 호출
안 멈추는 코드
무한으로 DFS(3) ▶️ DFS(2) ▶️ DFS(1) ▶️ DFS(0) ▶️ DFS(-1) ▶️ DFS(-2) ▶️ DFS(-3)……
따라서 재귀함수는 무조건 if, else, return
재귀를 멈추는 조건이 꼭 필요하다

❌ 무한 코드

    public void DFS(int n){
            DFS(n - 1); //여기까지하면 무한으로 돈다
    }

⭕️ 3, 2, 1까지만 출력되는 함수

if, else, return을 사용한다.
return: 값을 반환할수도 있지만 함수 종료의 의미도 가진다.

    public void DFS(int n){
        if(n==0) return; //⭐️
        else {
            DFS(n - 1);
        }
    }

✔️ 함수의 순서에 따라서 출력 값이 달라진다.

3, 2, 1 출력

    public void DFS(int n){
        if(n==0) return;
        else {
            System.out.print(n+ " ");
            DFS(n - 1); //⭐️
        }
    }

1, 2, 3 출력

    public void DFS(int n){
        if(n==0) return;
        else {
            DFS(n - 1); //⭐️
            System.out.print(n+ " ");
        }
    }

✔️ 재귀함수는 stack frame을 사용한다.

❓ 앞선 함수의 순서에 따라서 출력 값이 달라진다.에서 왜 순서에 따라 출력값이 달라졌을까?
재귀함수는 stack frame을 사용하기 때문이다.

💡 stack은 가장 상단에 있는 것이 작동한다.
💡 stack frame을 사용함으로 인해서 back tracking을 할 수 있다.
💡 stack frame에 저장되는 것은
‐ 매개변수
‐‐‐‐‐ 아래 그림에 있는 코드의 경우 n이 매개변수
‐ 지역변수
‐ 복귀주소
‐‐‐‐‐‐ 예를 들어 DFS(2)는 복귀주소가 DFS(3)일 것이다.

✔️ 1, 2, 3이 출력되는 stack frame 원리 그림으로 설명

✅ 1부터 n까지 출력하는 재귀함수를 만드세요

class Main {
    public void DFS(int n){
        if(n==0) return;
        else {
            DFS(n - 1);
            System.out.print(n+ " ");
        }
    }


    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(3);
    }
}

✅ 십진수를 이진수로 바꿔주는 재귀함수를 만드세요

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


    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(13);
    }
}

✅ 팩토리얼을 구하는 재귀함수를 만드세요

class Main {
    public int DFS(int n){
        if(n==1) return 1;
        else {
            return n* DFS(n-1);

        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        System.out.println(T.DFS(5));
    }
}