재귀함수 (Recursive Function)

재귀함수

재귀함수는 함수 안에 자신의 함수를 다시 호출하는 함수를 말한다.

재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다.

 

재귀함수는 스택 프레임을 사용해 작동한다. 스택 프레임에 저장되는 정보는 다음과 같다.

• 매개변수 정보
• 지역변수 정보
• 복귀 주소

그렇다면 재귀함수가 어떻게 작동하는지 코드를 통해 알아보자.

다음은 일반적으로 재귀함수를 표현하는 패턴이다.

class DFS {
    public static void dfs(int n) {
        if (//재귀 탈출 조건) {
            return;
        } else {
            dfs(//탈출을 위한 반복 조건);
        }
    }
}

 

예시 코드이다.

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

1 2 3

이해를 돕기 위해 스택을 직접 그려보면서 알아보자.

설명 이전에 스택은 항상 상단에 있는게 작동한다는 것을 기억하자.

진행 순서 (왼->오)

앞서 말했듯이 스택은 제일 상단에 있는 것이 실행되기 때문에 D(0)이 실행중인 상태이다.

D(0)은 if문 조건에 부합하기 때문에 바로 return되고, 바로 9라인으로 가서 종료된다.

D(0)은 할일을 끝냈기 때문에 스택에서 pop 된다.

 

이후 스택은 가장 상단에 있는 D(1)로 복귀하게 된다.

D(1)은 6라인까지 실행했기 때문에 7라인부터 시작해 print문을 통해 1이 출력된다.

그러면 D(1)도 종료되면서 스택에서 pop 된다.

 

이런식으로 계속하여 가장 상단에 있는 D(2)로 복귀하고 7라인부터 시작해 2를 출력하고 종료 및 pop,

D(3)으로 복귀하고 7라인부터 시작해 3을 출력하고 종료 및 pop 되기 때문에

1 → 2 → 3 순서로 결과가 출력되는 것이다.

 

 

활용 문제

팩토리얼

class Factorial {
    public int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

 

피보나치 수열

class Fibonacci {
    public static int fibo(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return fibo(n - 2) + fibo(n - 1);
        }
    }
}

• 피보나치 수열의 기저는 n이 1 또는 2일 때 이며, 이 경우 재귀가 종료(return 1)된다.
• 1과 2가 아닌 n은 재귀함수를 통해 점점 1과 2를 향해 내려간다.

위 코드를 실제로 실행하면 한가지 문제가 발생하게 된다.

예를 들어 fibo(5)를 호출한다고 했을 때

• fibo(5) → fibo(3) + fibo(4) 호출
  • fibo(3) → fibo(1) + fibo(2) 호출
    • fibo(1) → 1 반환
    • fibo(2) → 1 반환
  • fibo(4) → fibo(2) + fibo(3) 호출
    • fibo(2) → 1 반환 
    • fibo(3) → fibo(1) +  fibo(2) 호출
      • fibo(1) → 1 반환
      • fibo(2) → 1 반환

즉, fibo(3)은 2번, fibo(2)는 3번, fibo(1)는 2번 호출된다. 이전에 구한 값임에도 계속 뻗어나가며 또 값을 구하는 것이다.

이런 경우 fibo(100) 같은 경우 시간이 굉장히 오래 걸리게 된다.

 

구한 값을 어딘가에 저장해놓고, 이전에 구해놓은 값이면 더이상 재귀를 뻗지 않고 값을 가져다 사용한다면 시간 복잡도를 줄일 수 있을 것이다.

이렇게 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해 실행 속도를 빠르게 하는 기술을 "메모이제이션"이라 한다.

 

💻 메모이제이션 활용

class Fibonacci {
    static int[] memo;

    public static int fibo(int n) {
        memo = new int[n + 1];

        if (memo[n] > 0) {
            return memo[n]; //이미 구한 값이 있을 경우
        }
        if (n == 1 || n == 2) {
            return memo[n] = 1;
        } else {
            return memo[n] = fibo(n - 2) + fibo(n - 1);
        }
    }
}