재귀함수

설명

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

 

입력

첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.

 

출력

첫째 줄에 출력한다..

 

예시 입력 1 

3

 

예시 출력 1

1 2 3

 

문제 해결

 

재귀함수
: 자기가 자기 자신을 호출하는 함수
오늘 문제의 핵심 : 스택 프레임의 사용은 재귀가 작동하는 기본 메커니즘

 

else {
    System.out.print(n + " ");
    DFS(n-1);
}

 

호출의 순서로 출력 결과가 달라진다. 위와 같이 호출하면 결과는 3 2 1

 

else {
    DFS(n-1);
    System.out.print(n + " ");
}

 

이렇게 코드 순서를 바꾸면 결과는 1 2 3으로 나온다.

어떤 원리일까?

 

Stack Frame

 

 

재귀 함수에서 스택 프레임은 함수의 호출과 반환에 관련된 정보를 저장하는 메모리 구조이다.

각 재귀 호출마다 함수의 매개변수, 지역 변수, 복귀 주소와 같은 정보가 새로운 스택 프레임에 저장되어

함수가 자신을 호출할 때마다 이 정보를 사용할 수 있다.

 

위 코드를 보면, DFS(n-1)에서 DFS 함수가 자기 자신을 계속 호출하고 있다.

이 호출이 종료 조건에 도달할 때까지 각 호출은 스택에 쌓인다.

하지만 스택에 쌓인 각각의 함수가 반환될 때, 스택의 상위 프레임(가장 최근의 호출)부터 순차적으로 제거되면서

해당 함수 호출의 결과가 처리된다.

 

코드에서 System.out.print(n + " ");가 DFS(n-1); 호출 후에 있으므로,

각 재귀 호출이 호출의 동작이 스택에서 "풀리는" 순서에 따라 실행된다.

그래서 출력은 가장 먼저 호출된 함수부터 시작하여 스택에서 반환되는 순서대로 진행되어 1 2 3이 출력되는 것이다.

결론적으로, 재귀 함수의 스택 프레임은 함수 호출의 "역순"을 관리한다.

 

 

위 개념을 정리해 호출 위치에 따른 코드의 동작 과정을 정리해보았다.

 

System.out.print(n + " ");가 DFS(n-1); 호출 후에 위치

• DFS(3) 호출 → 스택에 저장됨
  • DFS(2) 호출 → 스택에 저장됨
    • DFS(1) 호출 → 스택에 저장됨
      • DFS(0) 호출 → 스택에 저장됨 → n == 0이므로 반환
    • DFS(1)로 돌아와 System.out.print(1 + " "); 실행
  • DFS(2)로 돌아와 System.out.print(2 + " "); 실행
• DFS(3)로 돌아와 System.out.print(3 + " "); 실행

 

System.out.print(n + " ");가 DFS(n-1); 호출 전에 위치

• DFS(3) 호출
  • System.out.print(3 + " "); 실행 → 출력: "3 "
  • DFS(2) 호출
    • System.out.print(2 + " "); 실행 → 출력: "2 "
    • DFS(1) 호출
      • System.out.print(1 + " "); 실행 → 출력: "1 "
      • DFS(0) 호출 → n == 0이므로 반환

 

최종 코드

 

import java.util.Scanner;

public class P01_재귀함수_스택프레임 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        DFS(N);
    }

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

        }
    }
}