재 귀 (되부름)

주의 : 이것은 대단히 진보된 주제이며 대부분의 어플리케이션에서 여러분은 그것에 관하여 알 필요가 전혀 없다. 때때로, 가치를 평가할수 없을 정도로 너무나 유용하다, 그래서 나는 여기에 그것을 여러분의 공부를 위하여 제시한다. 곧 바로 이해가 안갈지라도 곤란해 하지 마라.

그것은 무엇인가?

내가 프로그래밍의 전환점의 하나인 회돌이에 관하여 이전에 언급한 것에도 불구하고 사실 명시적인 회돌이 구조 없이도 프로그램을 작성하는 것이 가능하다. 라스프와 같은, 어떤 언어들은 실제로 FOR, WHILE, 등등과 같은 명시적인 회돌이 구조를 가지고 있지 않다. 대신에 그 언어들은 재귀(되부름) recursion 이라고 부르는 테크닉을 사용한다. 이것은 어떤 종류의 문제에는 대단히 강력한 테크닉이라고 증명되었으며, 그래서 우리는 그것을 지금 살펴보려고 한다.

재귀는 하나의 함수를 정의하는 부분으로 같은 함수를 적용하는 것을 단순히 의미한다. 그런식으로 (많은 자유소프트웨어의 근원이 되는) GNU 가 재귀적이라고 말하여진다. 왜냐하면 GNU는 'GNU's Not Unix'을 대표하기 때문이다. 즉 GNU는 GNU를 정의하는 한부분이다!

이것을 작동하게 하는 요점은 함수가 어떤 한 점에서 비-재귀적인 해법으로 분기하도록 종료조건이 있어야 한다는 것이다. (GNU에 대한 정의는 이런 테스트에 통과하지 못하며 그래서 무한 회돌이에 빠지게 된다.)

간단한 예제 하나를 살펴보자. 수학적인 팩토리얼 함수는 다음과 같이 정의 된다. 인수를 포함한 그 인수까지의 모든 수의 곱이며, 그리고 1의 팩토리얼은 1이다. 이것에 대하여 생각해 보면, 우리는 이것을 표현하는 다른 방법이 있으며 N 의 팩토리얼은 (N-1) 의 팩토리얼을 N 배 한것과 동등하다는 것을 알게된다.

Thus:
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 을 감소시키고 N 이 1 과 같은지 점검하기 때문에 그 함수는 반드시 완결된다.

되부름을 사용하지 않고 팩토리얼 함수를 작성하는 것은 상당히 더 많은 코드를 요구한다. 여러분은 1 에서 N 까지 모든 숫자를 담은 리스트를 만들고 그 리스트를 돌려서 현재의 합계를 다음 항목과 곱할 필요가 있다. 그것을 연습으로 시험해 보라 그리고 그 결과를 위의 함수와 비교하라.

리스트에 대한 되부름

되부름이 매우 유용한 다른 영역은 리스트를 처리하는 곳이다. 우리가 빈 리스트에 대하여 테스트를 할수 있다면, 그리고 첫 번째 요소를 뺀 리스트를 만들수 있다면 우리는 되부름을 쉽게 사용할 수 있다.

printList 함수를 사용하여 문자열 리스트의 각 요소를 출력하는 사소한 예제를 살펴 보자:

def printList(L):
    if L:
        print L[0]
        # for [1:] - see 'slicing' in the Python reference manual
        printList(L[1:])

만약 L 이 참이라면 - 비어있지 않다면 - 우리는 첫 번째 요소를 출력하고 그리고나서 그 리스트의 나머지를 처리한다.

그것은 단순한 리스트를 위하여 간단한 회돌이를 사용한 사소한 것이다. 그러나 리스트가 복잡하고 그 안에 다른 리스트를 포함하고 있다면 어떤 일이 일어날 지 생각해 보라. 만약 우리가 항목하나가 리스트인지 테스할수 있다면 그러면 우리는 printList()를 재귀적으로 호출할 수 있다. 그렇지 않다면 우리는 단순히 그것을 출력한다. 그것을 시험해 보자:

def printList(L):
    # if its empty do nothing
    if not L: return
    # if its a list call printList on 1st element
    if type(L[0]) == type([]):
        printList(L[0])
    else: #no list so just print
        print L[0]
    # now process the rest of L
    printList(L[1:])

이제 여러분이 전통적인 회돌이 구조를 사용하여 그것을 시도해 본다면, 여러분은 그것이 대단히 힘들다는 것을 발견할 것이다. 되부름은 대단히 복잡한 작업을 상대적으로 간단하게 만들 수 있다.

(물론!) 여기에도 난제는 있다. 거대한 데이타 구조에 대한 되부름은 메모리를 다 먹어 치우는 경향이 있어서 여러분이 메모리가 부족하다면, 혹은 대단히 거대한 데이타 구조를 가지고 있다면 더 복잡한 관례적인 코드를 사용하는 편이 더 안전할 수 있다.

좋다, 이제 또 다른 미지의 영역으로 달려가 보자. 우리는 객체 지향 프로그래밍을 소개한다.


Previous  Next  Contents


여러분이 이 페이지에 대하여 질문 혹은 제안사항이 있으면 다음주소로 나에게 전자메일을 보내라: agauld@crosswinds.net