(재귀)

작성: 2021-01-29 23:24
수정: 2021-02-07 22:48
난이도: Bronze Ⅰ

※ 이 포스트는 까먹을 만한/더 알면 좋은 것만 정리합니다

재귀 함수

재귀 함수의 재귀는 ‘再歸’로, 그 뜻은 ‘본디의 곳으로 다시 돌아오는 것’이다. 코드의 입장에서 생각해보면, 어떤 함수에서 함수를 호출했는데 코드를 실행하다보니 다시 그 함수를 호출한 곳으로 돌아왔다고 생각할 수 있다. 이렇게 하려면 함수가 자기 자신을 호출하거나, 2개 이상의 함수 호출 과정이 사이클을 이루는 방법이 있다. 보통은 자기 자신을 호출하는 방법을 사용한다.

재귀 함수의 구조

재귀 함수는 일반적으로 아래와 같은 구조 또는 같은 결과를 내는 구조¹를 사용한다.

def recursive():
    ... # condition을 판별하는 코드
    if not condition:
        ... # 종료 전 필요한 연산을 실행하는 코드
        return
    ... # recursive()를 호출하는 코드를 포함한 코드

재귀 함수의 변수와 종료 조건

재귀 함수를 완전히 똑같은 행동을 반복하도록 사용하는 경우는 흔치 않다. 보통 재귀를 통해 문제의 범위를 줄이거나 늘려서 특정 범위를 넘어가면 기존 재귀와 다른 코드를 실행 후 함수를 종료하는 방식으로 사용한다. 이를 위해 재귀 함수의 매개 변수로 현재의 재귀로 처리하려는 문제의 범위를 의미하는 변수를 하나 또는 그 이상을 사용한다. 그 예시로 주어진 수열의 현재 탐색 위치를 나타내기 위해 변수 하나를 사용하거나 탐색할 수열의 범위를 나타내기 위해 두 개의 변수를 사용할 수 있다.

만약 재귀를 종료하는 조건이 없으면 어떻게 될까? 종료하지 않고 함수가 무한히 실행되므로 무한 루프가 발생한다. 재귀를 멈추지 않으면 프로그램도 멈추지 않기 때문에 종료 조건을 항상 가져야 한다.

유명한 예시

팩토리얼 구하기

팩토리얼은 $n!=n\times (n-1)\times …\times 1$의 식을 통해 정의되는 값이다. 반복문을 통해서도 구할 수 있지만 문제의 크기를 줄이고 종료 조건을 시각화하기 아주 좋은 예시이다.

팩토리얼은 아래의 과정을 통해 점화식²을 구할 수 있다.

\[\begin{aligned} n!&=n\times (n-1)\times ...\times 1\\ &=n\times ((n-1)\times (n-2)\times ...\times 1)\\ &=n\times (n-1)! \end{aligned}\]

또한, 정의상 $1!=1$이므로 정확한 점화식은 $n!=n\times (n-1)!, 1!=1$이 된다. 이를 표현한 재귀 함수는 아래와 같다.

def fact(n): # n이 양수라는 조건 필요
    if n == 1:
        return 1
    else
        return n * fact(n - 1)

먼저 1!을 구하는 경우는 답이 1임을 알고 있으므로 1을 반환한다. 그게 아닌 경우는 점화식에 따라 n * (n - 1)! 값을 반환한다. 그런데 (n - 1)!의 값은 아직 모르므로 재귀 함수를 통해 다시 구하는 과정을 반복한다.

위 코드는 사실 문제가 있다. 음수가 들어왔을 때에 처리하지 못하기 때문이다. 이를 보완하기 위해 음수일 때에는 0³, 0일 때에는 1⁴을 반환하도록 조건문을 추가하면 아래와 같이 된다.

def fact(n):
    if n < 0:
        return 0
    elif n == 0 or n == 1:
        return 1
    else
        return n * fact(n - 1)

피보나치 수열 구하기

피보나치 수열은 $a_n=a_{n-1}+a_{n-2},a_0=0,a_1=1$의 점화식으로 정의되는 아주 유명한 수열이다. 위의 팩토리얼과 같은 방식을 이용하여 피보나치 수열을 구할 수 있다.

def fibo(n):
    if n < 0:
        return 0
    elif n <= 1: # 0 -> 0, 1 -> 1
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

팩토리얼과 다른 점이라면 자기 자신을 호출할 때에 2번씩 호출한다는 것이다. 재귀를 한 번만 호출할 필요는 없고, 위와 같이 여러 번 호출해도 된다. 피보나치 수열의 일반형인 n-bonacci 수열은 한 번에 재귀 함수를 n번씩 호출하게 된다!

정리

재귀 함수
- 자기 자신을 호출하거나 자기 자신을 호출하는 함수를 호출하는 함수
- 종료 조건을 사용하여 필요한 만큼만 호출
  - 일반적으로 매개 변수의 값으로 종료 조건을 판별
  - 무한 루프 방지
예시
- 팩토리얼(2747번 - 피보나치 수)
- 피보나치(10872번 - 팩토리얼)
- 위 두 문제 모두 재귀 함수를 몰라도 반복문으로 풀이 가능한 문제라서 ③입니다.

코드를 보면 특정 조건일 때에 return, 즉 함수를 종료시켜 재귀를 종료하는 부분을 명시적으로 추가했지만 이와 논리적으로 유사한 구조로 다음과 같은 경우가 있을 수 있다. ① 특정 조건을 만족할 때에만 재귀 함수를 실행, ② 특정 조건을 만족하지 않을 때 함수의 끝에 자연스럽게 도달하여 재귀를 종료하는 등의 구조가 있다. ↩
n번째 값이 그 이전 값들(n-1, n-2, …)을 통해서 구해지는 관계를 표현한 식이다. 가장 유명한 점화식은 피보나치 수열의 관계를 나타내는 식으로 $a_n=a_{n-1}+a_{n-2}$의 점화식을 가진다. ↩
음이 아닌 정수 범위에서 팩토리얼과 값이 같고 실수에서 대부분(?) 연속인 감마 함수($\Gamma(s)$)의 그래프를 그려보면 실제로는 음의 정수에서 값이 존재하지 않는다. ↩
$0!=1$인 이유는 아무것도 곱하지 않았기 때문에 곱셈의 항등원인 1이 남는다고 설명하지만 사실 감마 함수의 정의에 의해 $1!=\Gamma(2)=1\times \Gamma(1)=1\times 0!$을 만족해야 하고, 이는 곧 $0!=1$임을 암시한다. ↩

노트