재귀 함수의 개념 및 문제 접근방식

0. 개요

- 최근 Tree 문제를 풀기 시작하면서 재귀 함수를 사용한 풀이를 많이 접했다.

- 재귀 함수(= Recursion)를 사용하면 연산 속도도 빠르고 작성하는 코드 또한 간결해진다.

- 그래서 Recursion을 제대로 알고 사용하고 싶지만, 감이 잡힐 것 같으면서도 잡히지 않는다.

- 이와 같은 이유로 Recursion을 정복하고 싶다는 생각에 이번 포스팅을 작성한다.

- 나와 같이 Recursion에 어려움을 겪는 분들에게 도움이 되기를 바란다. 

 

 

1. Recursion 이란? 

- Recursion은 함수 내부에서 자기 자신을 다시 호출하는 형태를 가진 함수를 말한다.

 

 

2. 재귀 함수 작성 규칙

- 재귀 함수를 작성할 때 지켜야 하는 2가지 규칙이 있다.

 

a) Base case(반복을 멈추는 조건)

- Base case는 재귀를 멈추는 시점에 대한 조건문이다.

 

 

b) Recursion(반복할 행위)

- Base case를 작성한 다음에 자기 자신을 호출하면 된다.

 

 

c) 잠깐, 생각해보자!

- 이렇게 보면 재귀 함수는 정말 쉽다.

- 그렇다면 나를 포함한 많은 사람들이 왜 재귀 함수에 어려움을 느끼는 것일까?

- 이는 사람의 사고방식과 컴퓨터의 사고방식의 차이에서 온다.

 

 

3. Computational Thinking

- 아래의 그림은 입구에서 출구로 가는 최단거리를 구하는 문제다.

- 문제에서 입구와 출구의 위치가 주어지고, 출구를 가는 최단거리를 찾아야 한다.

- 흰색으로 채워진 공간은 벽이므로 접근할 수 없는 영역이며, 지도를 벗어날 수도 없다. 

 

 

a) 인간적인 사고방식

- 사람은 위의 그림을 보는 즉시 직관적으로 해결책을 도출한다.

- 아마도 아래의 그림과 같이 생각할 것이다.

- 이와 같은 사고방식은 사람이기 때문에 가능한 것이다.

- 사람이기 때문에 거시적인 관점에서 문제를 이해하고 해결할 수 있다. 

- 그러나 컴퓨터의 관점에서는 다르게 생각해야 한다.

 

 

b) 컴퓨팅적 사고방식

- 컴퓨터는 현재 시점을 기준으로 생각한다.

- 그러므로 문제의 전체를 보는 것이 아니라, 지금의 상황 하나만을 고려한다. 

   * FYI, 이 사고방식이 DP와 분할 정복에도 동일하게 적용된다.

 

- 아래의 그림을 살펴보자.

- 초록색이 현재 위치라고 한다면, 컴퓨터는 4가지 옵션(상하좌우)을 가진다.

- 즉, 현재 위치와는 상관없이 컴퓨터는 매번 4가지 옵션 중 하나를 반복적으로 선택하는 것이다.

 

- 한번 움직임을 가질 때마다 컴퓨터는 새로운 상황이라고 인지한다. 즉, 상황이 초기화되는 것이다.

- 그리고 매번 4가지 방향 중 하나를 선택한다.

 

- 무언가 재귀 함수와 비슷한 과정을 거친다는 생각이 들지 않는가?

 

 

4. 재귀 함수를 이용한 문제 접근 방식

- 그렇다면 위의 문제를 재귀적으로 풀어보자.

 

a) Base case 설정 

- 컴퓨터는 매번 4가지 방향(상하좌우) 중 하나를 선택한다.

- 그렇다면 컴퓨터가 갖는 제한 또는 제약이 무엇일까? 이는 재귀를 멈추는 조건이 된다. 

 

   1. 벽에 부딪히면 해당 방향으로 이동할 수 없다.

   2. 이미 방문했던 위치라면 중복해서 방문할 필요가 없다.

   3. 지도를 벗어난 위치로 이동할 수 없다.

   4. 현재 위치가 출구의 위치라면 탐색을 종료한다.

 

 

b) Recursion 설정

- 매번 반복할 때마다 위에 명시한 4가지 조건을 우선적으로 검사한다.

- 만약 4가지 조건 중 하나라도 부합한다면 반복을 멈춘다.

- 만약 4가지 조건 모두 부합하지 않는다면 다음을 반복한다.

 

1. 컴퓨터가 이동할 수 있는 4가지 방향을 검증한다.

2. 4가지 방향 중 위의 조건에 해당하지 않는 경우를 찾아 이동한다.

3. 다시 이 과정을 반복(Recurse)한다.

 

 

c) 잠깐, 생각해보자! 

- 위의 글을 읽으면서 다음과 같은 생각이 들 수 있다. 

 

- 만약 4가지 방향 모두가 종료 조건 4번을 제외한 나머지 조건에 부합한다면 어떻게 해야 할까?

- 해결책은 간단하다. 이전 위치로 돌아가면 된다. 이는 재귀이기 때문에 가능한 것이다.

- 재귀이기 때문에 가능하다는 것이 무슨 의미일까? 아래 코드를 살펴보자. 

 

 

5. 코드 구현

- 위의 조건과 재귀를 간단하게 코드로 구현하면 다음과 같다.

public class findExit {
    public boolean searchMaze(String[][] map, boolean[][] seen, int row, int col) {

        // 1. Base case 설정하기

        // a. 지도를 벗어난 경우
        if (row < 0 || row >= map.length || col < 0 || col >= map[0].length) {
            return false;
        }

        // b. 벽에 부딪히는 경우
        if (map[row][col] == "*") {
            return false;
        }

        // c. 이미 방문했던 위치인 경우
        if (seen[row][col]) {
            return false;
        }

        // d. 출구를 발견한 경우
        if (map[row][col] == "EXIT") {
            return true;
        }

        // 우선 현재 위치를 방문했음을 기록
        seen[row][col] = true;


        // 2. Recurse => 상하좌우 움직임을 구현
        return searchMaze(map, seen, row - 1, col) || // 위로 이동 
               searchMaze(map, seen, row + 1 ,col) || // 아래로 이동
               searchMaze(map, seen, row, col - 1)|| // 좌측으로 이동
               searchMaze(map,seen, row, col + 1); // 우측으로 이동 
                
                
    }
}

 

- 위의 코드에서 주목해야 되는 부분은 마지막 부분에 있는 return 문이다.

- 마지막 return문은 or 연산자(||)를 사용하여 4가지 움직임을 표현했다.

- 4가지 함수(= 움직임) 중 하나에서 false가 바로 다음 함수를 실행하는 방식이다.

 

- 상하좌우 모든 움직임에서 false가 나오는 경우 이전 단계로 돌아간다는 의미다.

- 이는 재귀라는 구조가 갖는 특성 때문이다.  

 

 

6. 탐색 과정

- 위의 코드를 통해, 컴퓨터가 어떻게 지도를 탐색하는지 알아보자.

 

a) 첫 번째 탐색

- 아래의 그림처럼, 첫 번째 탐색에서 주황색 원이 위치한 곳까지 가게 된다.

- 그러나 주황색 원 위치에서는 더 이상 이동할 수 없다. 

- 그러므로 재귀에 의해 이전 위치로 돌아가게 된다.

- 왜냐면 주황색 위치에 다음 탐색을 시도할 때, Base case 부분에서 false를 반환하기 때문이다. 

- 재귀를 작성한 코드 부분에 의하여, 컴퓨터는 무조건 상하좌우 순서로 탐색을 수행한다.

- 현재 주황색 원의 위치에 도달하기 위해, 이전 단계에서 상, 하 움직임을 검증했다.

- 그러나 아래쪽으로 이동한 결과, Base case에서 false를 반환하였다.

- 그러므로 이전 단계로 돌아가서 왼쪽으로 이동하는 선택지를 검증한다.(= 상하좌우로 순서로 이동하기 때문)

 

 

b) 두 번째 탐색

- 위의 그림처럼, 두 번째 탐색으로 주황색 원이 위치한 곳까지 이동하게 되었다.

- 첫 번째 탐색의 결과와 마찬가지로 더 이상 움직일 수 없는 위치로 이동하게 되었다.

- Base case에서 false를 반환하므로 이전 단계로 돌아가게 된다.

 

 

c) 세 번째 탐색

- 최종적으로 세 번째 탐색에서 컴퓨터는 출구를 찾을 수 있게 된다.

 

 

7. 결론

- 여기까지 재귀 함수에 대한 근본적인 이해를 설명해보았다.

- 재귀 함수가 어렵게 느껴지는 이유는 사람과 컴퓨터의 사고방식 차이 때문이다.

 

- 어떤 문제를 해결할 때 하나의 상황을 일련의 과정이 아닌, 완전히 독립된 상황이라 인지하는 것이 중요하다.

- 이를 전제로, 언제 함수가 종료되어야 하는지 조건(Base case)을 설정하고 

- 매번 독립된 상황에서 반복적으로 수행하는 동작을 파악하여 이를 재귀(Recurse)하는 것이 핵심이다.

 

- 재귀 함수는 DP, 분할 정복, BFS, DFS를 익히고 사용하는데 가장 근본적인 지식이 된다.

- 그러므로 꼭 재귀 함수의 동작원리를 본인의 것으로 만들어 코딩 테스트에서 승승장구하기를 바란다.