시작하기 전에

간혹 누군가는 재귀에 대해 배울 때 재귀 함수가 실행되는 모든 시점을 하나하나 분석하려는 경우가 있다.

이렇게 되면 재귀 학습하기 어려워지므로 재귀 문제의 해결을 위해서는 특정 상황을 가정하는 단계가 필요하다.

어떻게 해야 하나

간단한 문제 하나를 정해서 재귀로 해결해보자.

문제: 1 부터 n 까지의 모든 수의 합을 구하라.

우선 문제를 해결할 함수를 정의하고 한 단계씩 발전시켜 보자.

def sum_to(n):

1. 함수로 무엇을 해야하는지 파악하기

재귀 문제를 해결하기 위한 첫 단계는 함수의 작동 목적을 정의하는것이다.

이것은 쉬워 보이지만 매우 중요한 단계이다. 헷갈리면 안되는게 함수가 지금 수행해야 하는게 아닌 무엇을 수행해야 하는지를 생각하는 것이다.

우리가 구현하려는 sum_to() 함수의 작동 목적은 1부터 n까지의 수를 모두 더하는 것이다.

# sum_to() 함수는 숫자 n을 인자로 받아서 1부터 n까지의 숫자를 모두 더한다.
def sum_to(n):

2. 하위 문제를 설정하고 함수가 이미 작동한다고 가정하기

하위 문제…?

하위 문제는 원래의 문제보다 작은 어떤 문제라도 하위 문제가 될 수 있다.

현재의 경우에는 원래 문제는 1부터 n까지의 수를 모두 더하는 것이고 하위 문제는 n보다 작은 수들을 모두 더하는 경우들이다.

# 원래 문제가 sum_to(n)라면 하위 문제는 아래와 같다.
sum_to(n-1)
sum_to(n-2)
sum_to(n-3)
...
sum_to(1)

문제를 쉽게 해결하기 위해서는 적절한 하위 문제의 설정이 필요하다.

적절한 하위 문제를 선정하라.

하위 문제를 선정하는 다양한 방법이 있지만 그 중 추천하는 방법은 원래의 문제와 가장 근접하게 만드는것이다. sum_to() 함수가 이미 작동하고 있다고 가정하였으므로 문제의 대부분을 해결할 수 있는 값을 선정하는게 타당하다.

지금의 경우에는 n을 해결하기 위한 문제이므로 n-1이 최선의 하위 문제이다.

하위 문제를 구현해보면 아래와 같다.

# sum_to() 함수는 숫자 n을 인자로 받아서 1부터 n까지의 숫자를 모두 더한다.
def sum_to(n): // 원래의 문제 n
    # 1부터 n-1 까지 더하기
    sub_solution = sum_to(n-1)

여기서 누군가는 어떻게 구현된게 없는 함수를 사용하는지 의문을 가질것이다.

그렇습니다. 우리는 아직 아무것도 구현한 게 없다. 그러나 이 부분이 바로 이글의 초반에 말한 재귀 문제를 해결하는 과정에서 가정이 필요하다는 부분입니다. ( 이미 하위 문제에 대해 정상적으로 작동하고 있다는 가정 )

가정으로 인해 우리는 이제 1부터 n-1까지의 합계를 얻은 상태가 되었으므로 마지막 단계를 진행하면 된다.

3. 하위 문제의 답을 얻어서 원래의 문제를 해결하는데 사용하기

하위 문제는 해결되었고 다음으로는 하위 문제의 답을 어떻게 원래의 문제 해결에 사용할 것인가? 라는 문제가 남았습니다.

즉 1 부터 n-1의 합은 구했는데, 1 부터 n의 합계는 어떻게 구할 것인가인데 원래의 문제로 돌아가 다시 생각해보자.

1부터 n까지의 합계를 1부터 n-1까지의 합계를 이용해 구할 수 있지 않을까?

# 현재 구해진 하위 문제와 원래의 문제
sum_to(n-1) # 1 + 2 ... n-2 + n-1
sum_to(n)   # 1 + 2 ... n-2 + n-1 + n

# 하위 문제를 원래의 문제를 해결하는데 사용
sum_to(n-1) + n # 1 + 2 ... n-2 + n-1 + n
sum_to(n)       # 1 + 2 ... n-2 + n-1 + n

코드로 구현하면..

def sum_to(n): // 원래의 문제 n
    sub_solution = sum_to(n-1)

    return sub_solution + n

보다시피 하위 문제의 답이 원래의 문제의 답을 구하는데 쓰였다. 이게 바로 재귀식이라 불리는 방법이다.

4. 이미 문제의 99% 해결했다. 나머지 1%는?

지금까지 구현한 함수를 실행한다면 아마 영원히 스스로를 호출하게 될 것이다. (재귀 무한루프) 그래서 우리는 베이스 케이스를 추가해야 한다.

베이스 케이스란 무엇이고 어떻게 설정하는가?

베이스 케이스는 일반적으로 함수의 시작 단계에서 if-else로 특정 조건에 부합하는 경우 더 이상의 함수 호출을 막기 위해 더 이상의 계산이 필요 없는 값을 설정한다.

지금의 문제에서는 n값이 1인 경우이다.
( 1부터 1까지 모두 더하면 1이므로 더 이상의 계산은 필요없이 1을 리턴하면 된다. )

이제 해당 조건을 체크하는 코드를 추가해보자.

def sum_to(n):
    if (n == 1): # 베이스 케이스 추가
        return 1

    sub_solution = sum_to(n-1)

    return sub_solution + n

베이스 케이스를 추가함으로써 sum_to() 함수가 재귀적으로 호출되다가 n 값이 1이되는 순간(베이스 케이스)에서 1을 리턴하면서 더 이상의 재귀 호출이 일어나지 않게 되어 재귀 함수가 무한루프에 빠지지 않는다.

여기까지해서 재귀 문제를 해결해보았는데 요약해보면 아래와 같다.

  • 함수가 현재 수행하는 작업(currently does)이 아니라 수행해야 하는 작업(should do)을 생각하기
  • 적절한 하위 문제를 설정하기
  • 하위 문제의 답을 사용하여 원래의 문제를 해결하기
  • 베이스 케이스 작성하기

추가 예제

문제: 문자열 거꾸로 만들기

def reverse(s):

함수가 무엇을 수행해야 하는지 생각해보면 함수는 거꾸로 만든 문자열을 리턴해야 한다.

# 문자열을 거꾸로 만든다.
def reverse(s):

문자열을 거꾸로 만들어는 문제에 대한 하위 문제를 생각해야하는데 간단하게 “Hello” 를 예시로 생각해보자.

s = "Hello"

다시말하지만 reverse() 함수는 이미 작동한다고 가정한다. 그리고 쉽게 문제를 해결하려면 하위 문제는 대부분의 문제들을 해결하는 문제로 설정하는게 좋다.

이 경우에는 reverse() 함수를 호출하면 첫 글자를 제외한 문자열에 대해 호출하는 것이다.

reverse("Hello")  # "Hello" 는 원래의 문제
reverse("ello")   # "ello" 는 하위 문제

그리고 함수의 호출 결과가 어떻게 되어야 하는지 생각해보자.

reverse("Hello")  # "olleH"
reverse("ello")   # "olle"

이제 하위 문제를 원래의 문제를 해결하는데 사용하려면 원래 문제의 첫글자를 하위 문제의 결과의 뒤에 추가해주면 된다.

# 하위 문제와 원래의 문제
reverse("Hello")  # "olleH"
reverse("ello")   # "olle"

# 하위 문제의 결과를 원래의 문제 해결에 사용하기
reverse("Hello")       # "olleH"
reverse("ello") + "H"  # "olleH"

코드로 구현해보면

def reverse(s):
    sub_problem = s[1:]  # 첫 글자는 제외
    sub_solution = reverse(sub_problem)

    return sub_solution + s[0]

마지막으로 베이스 케이스를 생각해보자.

무엇이 현재 문제를 더 이상의 함수를 수행할 필요가 없는 값일까?

그건 바로 문자열이 비어있는 경우이다. ( 문자열이 비어있으니 더 이상 문자열을 거꾸로 만들 필요가 없으니 말이다.)

def reverse(s):
    if s == '': // 베이스 케이스
        return ''

    sub_problem = s[1:]
    sub_solution = reverse(sub_problem)

    return sub_solution + s[0]

문제: 피보나치 수열

# 피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

def fibTerm(n):

피보나치 수열을 살펴보면 n 번째 항은 이전 두 항의 합이라는 것을 아실 수 있습니다.

예를들어..

5는 이전 항 3과 2의 합이다.
34는 이전 항 21과 13의 합이다.
233은 이전 항 144와 89의 합이다.

다른 문제들과 다르게 원래의 문제는 두 개의 하위 문제를 필요로 한다.

# 피보나치 수열 (n이 7인 경우)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

7번째 항 13은 6(7-1)번째 항 8과 5(7-2)번째 항 5의 합

함수가 작동한다고 가정했을때, 우리는 이전 두 항을 얻을 수 있다.

# 피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

fibTerm(n):
    term1 = fibTerm(n-1)  # 하위 문제 - 1
    term2 = fibTerm(n-2)  # 하위 문제 - 2

원래의 문제를 해결하기 위해 하위 문제 1,2를 더해서 리턴해야 한다.

# 피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

fibTerm(n):
    term1 = fibTerm(n-1)
    term2 = fibTerm(n-2)

    # 원래의 문제를 해결하기 위해 하위 문제의 답을 사용.
    return term1 + term2

베이스 케이스를 찾는 건 조금 까다로울 수 있는데 이 경우에는 n이 0인 경우와 n이 1인 경우다. 왜냐하면 0과 1은 계산해야 할 이전 항 두 개가 없기 때문이다.

# 피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

fibTerm(n):
    if n == 0 or n == 1:
        return n

    term1 = fibTerm(n-1)
    term2 = fibTerm(n-2)

    # 원래의 문제를 해결하기 위해 하위 문제의 답을 사용.
    return term1 + term2

마치며

지금까지 주어진 문제를 재귀를 이용해 해결하는 방법에 대해 알아보았습니다. 재귀는 결국 문제를 하위 문제로 나눠서 답을 구한 후 하위 문제들의 답을 원래의 문제의 해결에 이용하는 방법이라고 할 수 있습니다.

그리고 적절한 하위 문제를 설정하는 것과 베이스케이스로 무한루프에 빠지지 않게 만들어 주는게 중요합니다.

주의할점은 꼭 재귀를 이용해 해결해야 하는 문제가 아니라면 재귀를 사용하지 않는것을 권장드립니다.

재귀는 아무래도 성능이 좋지 않은 편이기 때문에 꼭 필요한 경우에만 적절하게 사용하시길 바랍니다.

감사합니다.