[Algorithm] DFS 와 재귀 함수( Recursive Function )

💫재귀함수

 

내부적으로 자기 자신을 호출하는 함수를 재귀함수라고 한다.

반드시 종료 조건이 필요하다는 특징을 가지고 있다. 재귀 호출(자신을 호출)을 너무 많이 하게 되면 스택 메모리 영역에 너무 많은 공간을 할당하게 되어 스택 오버플로우가 발생할 수 있다는 점을 주의해야 한다. 그래서 재귀 함수를 구현할 때는 최악의 경우 얼마나 많은 재귀 호출이 발생하는 지 잘 살펴보아야 한다. 또한 재귀 함수에 대한 이해도가 높으면 코드의 가독성이 좋아질 수 있으나, 개념을 모르는 사람이 보면 코드를 이해하기 어렵다는 단점이 있다.

 

 

얼핏보면 같은 두 코드가 있다. 두 코드의 차이점이 무엇일까?

 

Case 1

class Solution {
    public void DFS(int n){
        if(n == 0) return;
        else{
            System.out.print(n + " ");
            DFS(n-1);
        }
    }
    public static void main(String[] args){
        Solution T = new Solution();
        T.DFS(5);
    }
}

Case 2

class Solution {
    public void DFS(int n){
        if(n == 0) return;
        else {
            DFS(n-1);
            System.out.print(n + " ");
        }
    }
    public static void main(String[] args){
        Solution T = new Solution();
        T.DFS(5);
    }
}

두 코드는 엄청 큰 차이점을 갖고 있다.

케이스 1 번의 경우 5 4 3 2 1 이 출력 되지만, 케이스 2번의 경우 1 2 3 4 5 가 출력된다.

이런 차이점을 만드는 이유가 바로 재귀 함수의 특징에 있다.

Runtime Data Area 에서 스택 프레임에는  지역변수, 매개변수, 복귀 주소 가 담아져 컨트롤 된다.

 

1️⃣Case 1

케이스 1을 보자.

매개변수에 5를 넣어서 DFS() 함수를 호출하였다.  매개변수는 0 이 아니므로 4번 행이 실행된다. 5번 행이 실행되어 5가 출력되고, 자기 자신인 DFS() 함수(매개변수 : 4)를 호출하고 기존 DFS(5)는 매개변수와 복귀 주소를 갖고 스택에 PUSH 되어 sleep 상태가 된다. 이 과정이 반복된다.

매개변수가 0이 되어 3번 행이 실행되어 함수가 종료되게 된다. 그러면 스택에 쌓여있던 함수를 POP해서 실행하게 된다. 가장 맨위에 있는 DFS(1) 이 POP된다. DFS(1) 은 7라인부터 실행되며, 8라인이 실행되고 난뒤에는 함수가 종료 되면서 스택에서 잠들어 있던 DFS(2) 를 POP 하여 실행한다. 이 과정이 반복된다.

그림으로 나타내면 다음과 같다.

 

2️⃣Case 2

케이스 2번의 경우를 보자.

매개변수에 5를 넣어서 DFS() 함수를 호출하였다.  매개변수는 0 이 아니므로 4번 행이 실행된다. 그 다음 바로 자기 자신인 DFS() 함수(매개변수 : 4)를 호출하고 기존 DFS(5)는 매개변수와 복귀 주소를 갖고 스택에 PUSH 되어 sleep 상태가 된다. 이 과정이 반복된다.

매개변수가 0이 되어 3번 행이 실행되어 함수가 종료되게 된다. 그러면 스택에 쌓여있던 함수를 POP해서 실행하게 된다. 가장 맨위에 있는 DFS(1) 이 POP된다. DFS(1) 은 6라인부터 실행되며 이때 매개 변수인 n이 1이므로 1를 출력한다. 그리고 7, 8라인이 실행되고 난뒤에는 함수가 종료 되면서 스택에서 잠들어 있던 DFS(2) 를 POP 하여 실행한다. DFS(2) 도 똑같이 6라인에서 2를 출력하게 되고, 8라인 까지 함수가 종료된 뒤 스택의 최상단 함수를 POP 한다. 이 과정이 반복된다.

그림으로 나타내면 다음과 같다.

📋재귀 함수의 대표적인 예

재귀함수의 대표적인 문제로는 피보나치 수열, 팩토리얼 , 순열과 조합, 그리고 DFS 문제들이 있다.

 

 

프로그래머스 - 피보나치 수

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

 

DFS

Flood fill을 이용하여 풀기

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스