재귀 - 자기 자신에게 되돌리는 것

고지: 재귀는 상당히 고급스러운 주제입니다. 대부분의 어플리케이션에서 알 필요조차 없습니다. 그러나 가끔씩 무한히 귀중한 경우가 있으므로 여기에 공부 재료로 제시합니다. 곧바로 이해가 되지 않는다고 해서 절망하지 마세요.

재귀란 무엇인가?

앞서 회돌이가 프로그래밍의 시금석이라는 사실을 말씀 드렸지만 사실 명시적인 회돌이 구조가 없어도 프로그램을 만들 수 있습니다. 스킴(Scheme) 같은 언어는 실제로 For이나 While 등등과 같은 명시적인 회돌이 구조가 없습니다. 대신 재귀(recursion)라는 테크닉을 이용합니다. 이는 특정 유형의 문제를 푸는 아주 강력한 테크닉으로 증명되어 있습니다. 그래서 지금 살펴보고자 합니다.

재귀는 그냥 함수를 그 함수의 정의에 적용하는 것을 뜻합니다. 그리하여 (자유 소프트웨어의 근원인) GNU의 정의는 재귀적이라는 말을 많이 합니다. 왜냐하면 GNU는 'GNU's Not Unix'의 약자이기 때문입니다. 즉 GNU가 GNU의 정의 안에 포함되어 있습니다!

이를 작동시키는 열쇠는 반드시 종료 조건이 있어야 한다는 것입니다. 어느 시점에서는 함수가 비-재귀적 해결책으로 분기해야 하기 때문입니다. (GNU 정의는 이 테스트에 실패하고 그래서 무한 회돌이에 빠집니다).

간단한 예를 살펴 봅시다. 수학에서 팩토리얼 함수는 인자 이하까지의 모든 숫자의 곱으로 정의됩니다. 1의 팩토리얼은 1입니다. 잘 생각해 보시면 또다른 방법으로 이를 표현할 수 있는데 N의 팩토리얼은 (N-1)의 팩토리얼에 N을 곱한 것입니다.

그리하여:
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

그래서 이를 다음과 같이 파이썬으로 표현할 수 있습니다:

def factorial(n):

    if n == 1:

        return 1

    else:

        return n * factorial(n-1)

이제 매번 N을 1씩 줄이고 N이 1과 같은지 검사하기 때문에 함수는 반드시 끝납니다. 그렇지만 이 정의에는 작은 버그가 있습니다. 1 보다 작은 수로 호출하면 무한 회돌이에 빠집니다! 그를 수정하기 위하여 테스트에서 "==" 대신에 "<="로 바꿉니다. 종료 조건에 실수하기가 아주 쉽다는 사실을 보여줍니다. 이는 아마도 재귀 함수에서 가장 흔하게 야기되는 버그 중의 하나일 것입니다. 올바르게 연산하려면 종료 지점 주위의 모든 값들을 확실하게 테스트하세요.

실행하면 어떻게 작동하는지 살펴봅시다. return 서술문에서 n * (다음 팩토리얼 호출의 결과)를 돌려줍니다. 그래서 다음을 얻습니다:

factorial(4) = 4 * factorial(3)

factorial(3) = 3 * factorial(2)

factorial(2) = 2 * factorial(1)

factorial(1) = 1

파이썬은 이제 다시 거슬러 올라가면서 값들을 교체합니다:

factorial(2) = 2 * 1 = 2

factorial(3) = 3 * 2 = 6

factorial(4) = 4 * 6 = 24

재귀 없이 팩토리얼 함수를 작성하는 일은 실제로 그렇게 어렵지 않습니다. 연습삼아 만들어 보세요. 기본적으로 상황에 맞게 N까지 모든 숫자를 회돌이하면 됩니다. 그렇지만 아래에 보시듯이 어떤 함수는 재귀 없이는 작성하기가 굉장이 까다롭습니다.

리스트 재귀

재귀가 아주 유용한 다른 분야는 리스트를 처리하는 곳입니다. 빈 리스트인지 테스트해서 첫 원소를 빼고 리스트를 만들 수 있다면 쉽게 재귀를 사용할 수 있습니다. 파이썬에서는 조각썰기(slicing)라는 테크닉을 이용합니다. 이는 파이썬 메뉴얼에 완전히 설명되어 있지만 우리의 목적을 위해서는 리스트에 [1:]이라는 "지표"를 사용하면 1번 원소부터 리스트의 끝까지 모든 원소를 돌려준다는 사실만 알면 됩니다. 그래서 L이라는 리스트의 첫 원소를 얻으려면:

first = L[0] # 보통의 지표를 사용하면 된다

그리고 나머지 리스트를 모두 얻으려면:

butfirst = L[1:] # 조각썰기로 1,2,3,4... 나머지 원소들을 모두 얻는다

파이썬 프롬프트에서 시험해 봅시다. 제대로 작동하는지 확인해 보기 위해서 말이지요:

>>> L =[1,2,3,4,5]

>>> print L[0]

1

>>> print L[1:]

[2,3,4,5]

좋습니다. 다시 재귀를 사용하여 리스트를 인쇄해 봅시다. printList 함수를 이용하여 문자열로 구성된 리스트의 원소를 인쇄하는 사소한 사례를 생각해 봅시다:

def printList(L):

    if L:

        print L[0]

     printList(L[1:])

만약 L이 참이라면 - 즉 비어 있지 않다면 - 첫 원소를 인쇄하고 나머지 리스트를 다음과 같이 처리합니다:

# 의사 코드

PrintList([1,2,3])

   prints [1,2,3][0] => 1

   runs printList([1,2,3][1:]) => printList([2,3])

   => we're now in printList([2,3])

         prints [2,3][0] => 2

         runs printList([2,3][1:]) => printList([3])

      => we are now in printList([3])

            prints [3][0] => 3

            runs printList([3][1:]) => printList([])

            => we are now in printList([])

                  "if L" is false for an empty list, so we return None

      => we are back in printList([3])

            it reaches the end of the function and returns None

   => we are back in printList([2,3])

      it reaches the end of the function and returns None

=> we are back in printList([1,2,3])

   it reaches the end of the function and returns None

 

[고지: 위의 설명은 2003년 7월 자크 알쓴(Zak Arntson)이 파이썬 교사 메일링 리스트에 제시한 예제에서 인용하였습니다.]

단순한 리스트라면 간단하게 for 회돌이를 사용하여 처리하면 되는 사소한 일입니다. 그러나 리스트가 복잡해서 그 안에 다른 리스트가 더 들어 있으면 무슨 일이 일어날지 생각해 보세요. 내장된 type() 함수를 이용하여 원소가 리스트인지 테스트해서 그것이 리스트이면 printList()를 재귀적으로 호출할 수 있습니다. 리스트가 아니라면 그냥 그것을 인쇄합니다. 시험해 봅시다:

def printList(L):

    # 비어 있으면 아무 일도 하지 않는다.

    if not L: return

    # 리스트이면 printList를 첫 원소에 호출한다.

    if type(L[0]) == type([]):

        printList(L[0])

    else: # 리스트가 없으므로 그냥 인쇄한다.

        print L[0]

    # 이제 L의 나머지 원소를 처리한다.

    printList(L[1:])

이제 관례적인 회돌이 구조로 시도해 보면 아주 어렵다는 것을 알 수 있습니다. 재귀는 아주 복잡한 과업을 비교적 쉽게 만들어 줍니다.

(물론) 함정이 있습니다. 방대한 데이터 구조에 재귀를 사용하면 메모리를 잠식하는 경향이 있습니다. 그래서 메모리가 부족하다면 또는 데이터 구조가 처리하기에 너무 방대하다면 복잡하지만 전통적인 코드가 더 안전할 수 있습니다.

마지막으로, VBScript와 JavaScript 모두 재귀를 지원합니다. 그렇지만 이미 다 말해서 별로 할 말이 없으므로 각 언어로 재귀 버전의 팩토리얼 함수를 만드는 일은 여러분에게 남겨 두겠습니다:

<script type="text/vbscript">

Function factorial(N)

   if N <=1 Then

      Factorial = 1

   Else

      Factorial = N * Factorial(N-1)

   End If

End Function

 

Document.Write "7! = " & CStr(Factorial(7))

</script>

 

<script type="text/javascript">

function factorial(n){

   if (n <= 1)

      return 1;

   else

      return n * factorial(n-1);

};

 

document.write("6! = " + factorial(6));

</script>

좋습니다. 기능적 프로그래밍에서 소개드렸듯이 이제 또다른 미지의 세계로 뛰어 들어가 봅시다.

기억해야 할 것

· 재귀 함수는 자신의 정의 안에서 자신을 호출한다. · 재귀 함수는 반드시 비-재귀적인 종료 조건을 가져야 한다. 그렇지 않으면 무한 회돌이가 발생한다. · 재귀는언제나 그런 것은 아니지만, 종종 메모리를 많이 소비한다.

 

 출처 : http://coreapython.hosting.paran.com/tutor/index.htm