이번 포스트에서는 재귀가 왜 필요한지와 기본적인 재귀의 흐름에 대해서 살펴보자.
재귀함수
재귀란?
재귀(再歸, recursion )란 러시아의 전통인형 마요르카 처럼 내 안에 또 다른 나 즉 모양이나 동작은 동일하지만 크기만 작은 나를 찾아가는 과정이다.
우리는 수학 시간에도 재귀의 성격을 잘 배운적이 있다. 1부터 n까지의 곱을 구하는 펙토리얼 연산이 그 예이다.
n! = 1 * 2 * 3 * ... * (n-2) * (n-1) * n
여기서 맨 마지막의 *n을 제외하면 나머지는 (n-1)! 이 된다. 즉 크기만 1작아진 펙토리얼이다.
이렇게 하나의 문제 내에 크기는 다르지만 동일한 성격의 다른 문제를 하나 이상 포함하고 있는 것을 재귀적 구조라고 한다.
이런 재귀를 프로그래밍 함수에 적용한 것을 재귀 함수라고 한다. 재귀함수는 자기가 자기를 부르는 형태의 함수로 완전탐색을 위해 순열/조합/부분집합을 구하거나 DFS와 같은 탐색 등 알고리즘 전반에 사용되고 있으므로 알고리즘을 위해서는 반드시 정복해야할 산이다.
간단한 재귀와 문제점
가장 간단한 형태의 재귀 함수를 작성해보자. 다음의 recursionEndless라는 메서드는 내부적으로 다시 recursionEndless를 호출하고 있다. 이 형태를 우리는 재귀 함수라고 한다.
하지만 막상 이 함수를 실행시켜보면 어떤 문제가 발생할까?
아마도 다람쥐 쳇바퀴 돌듯이 스스로를 계속 호출하다가 아래와 같이 StackoverflowError가 발생하면서 종료된다.
Hello Recursion
…
Hello Recursion
Exception in thread "main" java.lang.StackOverflowError
재귀함수는 기본 부분 + 유도 부분으로 구성
위와 같은 이유로 재귀 함수는 반드시 종료될 수 있는 상황을 만들어 두어야 하며 이를 위해 기본 부분(Base Part)과 유도 부분(Inductive Part)으로 구성된다.
- 기본 부분: 재귀 호출을 벗어나는(return) 단계로 재귀함수는 적어도 하나의 기본 부분이 필요하다.
- 유도 부분: 문제의 크기를 변경하며 자신을 다시 호출하는 단계로 결국 기본 부분으로 수렴해야 한다.
이때 문제의 크기를 나타내기 위해서 재귀 함수는 일반적으로 파라미터를 사용한다. 다음의 예를 살펴보자.
이제 recursionLimit를 호출하면서 양수의 파라미터를 전달해준다면 1씩 감소하면서 점점 0에 수렴하고 언젠가 함수는 종료될 수 있을 것이다.
이처럼 재귀함수는 무한 루프에 빠지지 않기 위해서 재귀 호출을 벗어나는 기본 부분과 유도 부분에서 기본 부분으로 수렴하는 코드가 필수이다.
반복문 to 재귀함수
그런데 위와 같은 제한 조건은 사실 반복문에서도 당연히 필요했던 부분이다. 반복문이 무한루핑에 빠지지 않기 위해서는 반복문이 종료되는 경계 조건이 명확해야 하기 때문이다.
아마도10번 beep라는 문자열을 출력하는 프로그램을 반복문으로 작성할 때는 아래와 같이 작성했을 것이다.
작성된 반복문 내부에는 전체 문제의 크기, 초기값에 대한 정보가 모두 있기 때문에 그냥 beepLoop()를 호출하기만 하면 잘 동작할 것이다.
만약 이것을 재귀 형태로 바꾼다면 아래와 같이 작성할 수 있다.
전체적으로 구성 요소가 다르지는 않다. 색으로 잘 구분해보면 반복문에 있는 요소들이 재귀에도 그대로 있다. 다만 문제를 종료하기 위한 조건 즉 i를 초기화 하는 부분이 재귀 내부에 존재할 수 없고 재귀를 처음 호출할 때 넘겨준다는 점이 다르다.