재귀함수를 이해하는 과정은 험난하지만 개발자로서 실력을 한 단계 높이기 위해 반드시 거쳐야 할 관문 중 하나다. 필자는 재귀 함수를 이해하는 데 꽤 긴 시간이 걸렸다. 그 과정에서 알게 된 세 가지 규칙을 공유한다. 재귀함수 예제를 활용해 쉽게 이해할 수 있도록 설명해 보겠다. 개념을 이해하더라도 자유자재로 다룰 수 있으려면 많은 연습이 필요하다. 그만큼 원래 어려운 내용이니 혹시 이해가 잘 되지 않더라도 포기하지 않길 바란다.

재귀함수란?

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

재귀함수 예제

public void func(int count) {
  if (count == 5) {  // 재귀 호출 종료 조건
    return;
  }
  System.out.println("1");
  func(count + 1);  // 재귀 호출
  System.out.println("2");
}

재귀 함수는 위에서 정의한 func 함수처럼 생겼다. count==5가 재귀 호출을 종료하는 조건이다. 그리고 함수 내부적으로 자기 자신을 재귀 호출하고 있다. 재귀 호출 이전에 “1”을 출력하고, 재귀 호출된 함수가 종료된 이후에 “2”를 출력하는 것이 이 함수가 하는 일의 전부다. 이 함수 외부의 다른 곳에서 func(0)을 호출하면 결과가 어떻게 될 지 예상해보라.

1
1
1
1
1
2
2
2
2
2

결과는 위처럼 “1”을 5번 출력하고 “2”를 5번 출력하게 된다. 재귀 함수에 종료 조건이 없으면 죽을 때까지 자기 자신을 호출하게 된다. 그래서 반드시 어떤 조건을 만족할 때 재귀 호출을 멈출 것인지 정해주어야 한다. 함수는 return 문을 만나거나 함수를 끝까지 실행한 이후에 종료된다. 위 예시에서는 count == 5 가 종료 조건이다. 위 예시 코드는 재귀 호출 시 매개변수인 count에 1을 더한 값을 인자로 넘겨주고 있으므로 처음에 func(0) 을 호출하면 1을 5번 출력한 직후에 return 문을 만나게 된다.

종료 조건을 만족할 때 일어나는 일

종료 조건에 도달한 이후의 실행 과정을 글로 작성해 보겠다. “func(0)으로 시작하여 재귀 호출을 반복하다가 func(5)가 호출되면 count 값이 5가 되어 종료 조건을 만족한다. return문을 만나서 func(5) 함수가 종료된다. 그러고 나면 func(4)에서 func(5)를 호출했던 위치의 다음 로직으로 2를 출력하고 func(4) 함수를 종료하게 된다. 그러고 나면 func(3)에서 func(4)를 호출했던 위치의 다음 로직으로 2를 출력하고 func(3) 함수를 종료하게 된다. 그러고 나면 func(2)에서 func(3)을 호출했던 위치의 다음 로직으로 2를 출력하고 func(2) 함수를 종료하게 된다. 그러고 나면 func(1)에서 func(2)을 호출했던 위치의 다음 로직으로 2를 출력하고 func(1) 함수를 종료하게 된다. 그러고 나면 func(0)에서 func(1)을 호출했던 위치의 다음 로직으로 2를 출력하고 func(0) 함수를 종료하게 된다. 처음 호출했던 func(0)이 종료되었으므로 재귀 호출은 끝을 맺는다.”

이게 도대체 무슨 말일까? 비슷한 말을 반복적으로 계속 하고 있다. 그게 바로 재귀의 특징이다. 아래의 그림과 설명을 읽어본 뒤에 위 내용을 다시 읽어보면서 천천히 이해해보길 바란다.

함수가 호출될 때 공간이 할당되고 종료하면서 해제되는 메모리 영역을 Call Stack으로 나타낸다. 함수가 호출(call) 되면 스택 프레임(네모 상자)이 push(메모리 할당)되고 함수가 종료되면 스택 프레임이 pop(메모리 할당 해제) 된다. func 라고 적혀있는 상자가 해당 함수와 관련하여 할당된 메모리(스택 프레임)라고 할 수 있다. 옆에 적힌 숫자 1~6 순으로 push 되고, 6~1 순으로 pop 된다. 6번 스택 프레임이 count==5 연산 결과가 true가 되어 재귀 호출을 종료하게 되는 지점이다. 종료 지점을 만나기 전에는 스택 프레임을 계속해서 push하고 종료 조건을 만족 시킬 때 pop한다. 재귀 호출이 종료되고 나면 바로 다음 로직을 실행하는 흐름을 타게 된다. 위 그림은 설명을 위해 추상화 한 그림이니 더 자세히 알고 싶다면 콜 스택, 스택 프레임에 대해서 검색해보길 바란다.

이해를 돕는 규칙 3가지

필자는 재귀 함수를 구현할 때 아래의 세 가지를 생각해보는 것이 도움이 되었다.

• 결과를 향한 방향
  – 정방향 / 역방향
• 반환 값
  – 있음 / 없음
• 종료 조건

정방향/역방향, 있음/없음, 종료 조건은 개발자가 얻고자 하는 결과에 따라 달라진다.

정방향/역방향 에 대한 설명이 필요할 것 같다. 정방향은 종료 조건을 만족하려면 특정 값을 증가시켜야 하는 경우이고, 역방향은 감소시켜야 하는 경우다. 처음에 봤던 예제를 보자. 재귀 함수가 시작될 때 count가 0이고, count == 5를 종료 조건으로 한다면 종료 조건을 만족하기 위해 재귀 호출 시 count를 증가 시킬 수 밖에 없다. 즉, 처음에 봤던 예제는 결과를 향한 방향이 정방향이다. 역방향의 경우는 어떨까? 재귀 함수가 시작될 때 count가 5이고, count==0 을 종료조건으로 한다면 종료 조건을 만족하기 위해 재귀 호출 시 count를 감소시킬 수 밖에 없다. 필자는 이런 경우를 역방향이라고 이름 붙였다.

반환 값이 없는 경우는 출력만 하거나 전역 변수를 사용하는 등의 이유로 함수에서 값을 반환할 필요가 없는 경우다. (알고리즘 문제를 푸는 중이 아니라면 전역 변수는 사용하지 말자.) 처음에 봤던 예제는 출력만 하고 있으므로 반환하는 값이 없다.

종료 조건을 정하는 건 우리가 원하는 결과를 얻기 위해 재귀 호출을 어떤 지점에서 멈춰야 하는 지를 결정하는 것과 같다. 처음에 봤던 예제에서 종료 조건은 count==5 이다. 왜 하필 count==5 인가? 1을 5번 출력하고 싶었기 때문이다. 아, 참고로 종료 조건은 경우에 따라 여러 개도 될 수 있다.

재귀함수 구현해보기

재귀함수는 순열과 조합을 구할 때도 활용할 수 있고 이분 탐색, DFS 등 다양하게 활용된다. 이해하기 쉽지 않겠지만 알고리즘 문제를 풀 때 재귀함수를 어떤 식으로 사용하는 지 엿보고 싶다면 여기(👈 click!!)를 눌러보라. 우리는 이제 막 배우는 단계이다. 무리하지 말고 쉬운 것부터 천천히 다가가자. 재귀 함수를 설명할 때 대표적인 것이 피보나치 수, 팩토리얼을 구하는 함수이다.

N 번 째 피보나치 수

피보나치 수열은 첫 번째, 두 번째 수가 1이고 세 번째 수부터 이전 두 수의 합으로 나타낸다. 피보나치 수열의 N번째 수가 무엇인지 구하려면 어떻게 해야 할까? 재귀 함수를 적용할 방안이 떠오르는가? 필자는 이걸 떠올리기가 쉽지 않았다. n번째 피보나치 수를 f(n) 이라고 나타내면 f(n) = f(n-1) + f(n-2) 이라는 식이 나온다. 우리는 재귀 함수로 문제를 해결하고 싶다. 종료 조건은 무엇이 되어야 하는가?

종료 조건에 대해 생각할 때, 혹시 가장 처음이나 끝에 어떤 고정 값이 있는지 생각해보라. 우리가 구해야 하는 값은 n번째 피보나치 수이다. 세 번째 수를 생각해보면 1+1 = 2. 네 번째 수를 생각해보면 2+1 = 3. 그럼 첫 번째, 두 번째 수는? 이 수들이 1로 고정되어 있다는 것을 알아챘는가? 이 사실을 활용하자. 종료 조건은 n==1, n==2 로 하고 1을 반환하게 한다. 글 초반에 보여줬던 예시는 종료 조건이 하나 뿐이었지만 이번엔 두 개다. 반환 값이 없었지만 이번엔 반환 값이 있다. 종료 조건을 향한 방향이 정방향(count : 0 → 5) 이었지만 이번엔 역방향(n : n→1, n→2)이다. 고정된 값이 가장 작은 값이기 때문에 역방향으로 구현하는 것이 적합하다.

public long fibonacci(long n) {
  if (n <= 2) {
    return 1;
  } 
}

종료 조건을 코드로 구현했다. 왜 n==1 || n==2가 아니라 n<=2로 작성했을까? 매개 변수 n의 값이 1, 2 보다 작은 0, -1 이 될 가능성이 있는지 따져봐야 한다. 그럴 가능성이 있는가? 없다. 무조건 첫 번째, 두 번째 수는 1이 되어야 하는 것이 피보나치 수열의 규칙이기 때문이다. 하지만 누군가 실수로 fibonacci(-1)를 호출하는 코드를 작성했다고 생각해보자. 종료 조건이 n==1 || n==2라면 무한 루프에 빠지게 된다. 그래서 혹시라도 n이 1 미만의 값일 경우에는 1을 반환하고 종료하도록 종료 조건을 n<=2로 구현한 것이다.

나머지 로직을 구현해보자. 우리는 fibonacci(n) 을 호출했을 때 n 번째 피보나치 수를 반환하게 만들고 싶다. n번째 피보나치 수는 n-1번째 수와 n-2번째 수를 더한 값이다.

public long fibonacci(long n) {
  if (n <= 2) {
    return 1;
  } 
  return fibonacci(n-1) + fibonacci(n-2);
}

어떤가? 혹시 종료 조건을 만족 시킬 수 없는 경우가 있는가? 심지어 매개 변수 n의 값이 -100 일지라도 반드시 종료 조건을 만족하게 된다. 재귀 함수를 구현할 때는 종료 조건에 빈틈이 없는지 잘 따져보아야 한다. 그래야 무한 루프에 빠지지 않고 원하는 결과를 얻을 수 있다. 우리가 구현한 함수가 죽을 때 까지 자기 이름만 부르다 죽게 만들지 않도록 주의하자.

fibonacci(5)를 호출하면 5번째 피보나치 수를 반환한다. 신기하다. 코드가 정말 간결하다. 재귀 함수를 사용하면 이렇게 짧지만 강력한 코드를 작성할 수 있게 된다. 하지만 재귀 함수에 대한 이해가 없으면 이 코드를 이해할 수 없고 작성할 수도 없다.

N 팩토리얼

두 번째 문제는 팩토리얼 함수이다. N 번 째 피보나치 수열 구현 방법을 제대로 이해했다면 쉽게 해결할 수 있다. 팩토리얼을 수식으로 나타내면 다음과 같다. N! = N*(N-1)*(N-2)*...*1 그리고 0!, 1!의 값은 항상 1이 되기로 약속되어 있다. 이제 종료 조건이 무엇이 되어야 하는지 보이는가? 결과를 향한 방향은 정방향인가 역방향인가? return 값은 있는가 없는가? 어떻게 구현할 것인가? 이에 대한 답을 내리면서 함수를 직접 구현해보라. 정답은 아래에 있다. 답을 보지 않고 직접 구현해 본 뒤에 비교해 보기를 권한다.

public long factorial(long n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n-1);
}