Q. 개념

---

자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.
▣ 출력설명
첫째 줄에 출력한다.
▣ 입력예제 1
3
▣ 출력예제 1
1 2 3

전략

• 모든 메서드는 호출시 스택 자료구조에 스택프레임 정보가 쌓인다.
• 스택프레임에는 매개변수, 지역변수, 복귀주소 정보가 저장된다.
• 스택 제일 상단에 쌓여있는 스택프레임이 작동중인 스택프레임이며, 그 아래 스택프레임들은 실행 대기중이다. 추후 최상단 스택프레임이 스택에서 pop 되면 그 아래 스택프레임의 복귀주소부터 코드가 진행된다.
  
• 구조

  [트리구조]
  D(3)
  ↓↑
  D(2)
  ↓↑
  D(1)
  ↓↑백트레킹
  D(0)
  
  [스택프레임]
  

• 출력순서 중요시 스택구조(+백트래킹)를, 그게 아니면 트리구조(+백트래킹)를 위주로 그려보기

정답

출력순서 차이가 포인트!

import java.util.*;

class Main {
    // DFS = 깊이우선탐색 = 재귀함수
    // 재귀함수는 반복문으로도 구현 가능
    public void DFS(int n){
        // 종료조건 필수
        if(n==0) return;
        else {
            System.out.print(n+" "); // 3 2 1
            DFS(n-1);
            System.out.print(n+" "); // 1 2 3
        }
    }

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

• 출력 : 3 2 1 1 2 3