1. 재귀함수 (스택프레임) 중요!

1. 문제

N이 입력되면 재귀함수를 이용해 1부터 N까지 출력하는 프로그램을 작성하시오.

 

 

2 - 1. 나의 풀이

그냥 생각없이 재귀함수 만들어서 풀었다.

강의 코드로 진행

 

3 - 1. 강의 풀이

난 그동안 감각적으로 문제를 풀다가 강의를 보고 논리적인 풀이와 설명이 가능해졌다.

 

스택 프레임과 그림을 그려가면서 풀면 금방 풀렸다.

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;

public class dfs02 {
    private static void dfs(int n) {
        if(n==0) return;
        else{
        dfs(n-1);
        System.out.print(n);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dfs(n);
    }
}

 

4. 얻어갈 점

재귀함수 호출과 일반 코드의 서순에 따라서 전체 출력의 순서가 정해진다. (스택 프레임)

 

dfs1과 dfs2의 차이는 재귀 함수와 일반 코드중 어느 것을 먼저 호출하냐의 차이이다.

dfs1의 경우는 print(n)이 먼저 호출 됨에 따라서 n, n-1, n-2 ... 으로 호출된다.

dfs2의 경우는 재귀함수인 dfs2(n-1)가 먼저 호출되어서 맨 마지막까지 자기자신이 호출된 다음 역으로 그 다음 라인이 실행되면서 0, 1,..., n-2, n-1, n 이 출력된다.  

private static void dfs1(int n) {
    if(n==0) return;
    else{
        System.out.print(n);
   		dfs1(n-1);
   }
}

private static void dfs2(int n) {
    if(n==0) return;
    else{
        dfs2(n-1);
        System.out.print(n);
    }
}