프로그래머가 아닌 이들을 위한 파이썬 3 자습서/재귀

재귀

파이썬에서, 재귀함수는 자기 스스로를 호출하는 함수이다.

재귀 소개

파이썬에서 오랫동안, 우리는 다른 함수를 호출하는 함수를 보아왔다. 그러나, 함수가 스스로를 호출하는 것도 가능하다. 간단한 예제를 보도록 하자.

# Program by Mitchell Aikens
# No Copyright
# 2010

num = 0

def main():
    counter(num)

def counter(num):
    print(num)
    num += 1
    counter(num)

main()

만약 이 프로그램을 IDLE로 실행시킨다면, 이것은 영원히 실행될 것이다. 이 루프를 멈추는 유일한 방법은 키보드에서 Ctrl + C를 눌러 실행을 중단시키는 것이다. 이것이 무한 재귀의 예이다. (일부 사용자는 Ctrl + C 를 누르더라도 중단되지 않고 루프가 시작되는 현 IDLE 시스템의 결함을 보고하였다. 그 상황이 발생하면, Ctrl + F6을 누르라, 그러면 IDLE 쉘이 재시작할 것이다.)

재귀는 while 루프와 같은 것을 성취하는 다른 방법임을 증명할 수 있다. 다른 사례에서, 이것은 절대적으로 옳다. 그럴지라도, 재귀는 while 루프나 for 루프가 최적의 방법이 아닌 곳에서 유효한 다른 사용법이 있다.

재귀는 루프처럼 제어될 수 있다. 제어된 루프의 예제를 보도록 하자.

# Program by Mitchell Aikens
# No copyright
# 2012
def main():
    loopnum = int(input("How many times would you like to loop?\n"))
    counter = 1
    recurr(loopnum,counter)
# 루프를 돌 회수를 지정한다

def recurr(loopnum,counter):
    if loopnum > 0:
        print("This is loop iteration",counter)
        recurr(loopnum - 1,counter + 1)
    else:
        print("The loop is complete.")
# 루프가 진행중이면 진행중인 횟수를 표시하고, 끝나면 완료메시지를 출력한다.

main()

위의 것은 '인수/매개변수'를 사용하여 재귀횟수를 제어하고 있다. 단순하게 당신이 이미 알고있는 함수를 사용하고 프로그램의 흐름을 따르라. 이것은 쉽게 이해할 수 있다. 만약 당신이 어려움을 겪고 있다면, 앞에서 보았던 프로그래머가 아닌 이들을 위한 파이썬 3 자습서/고급 함수 예제를 참조하라.

재귀의 실질적인 적용(응용)

자주, 재귀는 최신의 컴퓨터 과학 수준에서 연구되고 있다. 재귀는 더 작은, 동일한 문제로 세분화할 수 있는 복잡한 문제를 해결하는데 주로 사용된다. 재귀가 문제를 해결하는데에 필수적인 것은 아니다. 재귀로 해결될 수 있는 문제들은, 대체로 루프로도 해결될 수 있다. 또한, 루프는 재귀함수보다 더 효율적일 수 있다. 재귀함수는 루프보다 더 많은 메모리와 리소스를 필요로 한다, 이것은 많은 사례에서 덜 효율적으로 만든다. 이러한 사용 요구사항을 빈번히 오버헤드(overhead)라고 한다. 당신은 이런 생각을 할 수도 있다, "왜 귀찮게 재귀를 쓰는 걸까. 나는 루프만 사용할텐데. 나는 이미 어떻게 루프를 사용하는지 알고 있고 이것은 많은 일을 하는데 말이야." 이러한 생각은 이해할 수 있으나, 전체적으로 이상적이지는 않다. 복잡한 문제를 해결할 때에는, 재귀 함수가 코드를 만드는데 때때로 더 쉽고, 더 빠르고, 더 간단하다.

아래 두 가지 "규칙"에 대하여 생각해보자:

• 만약 내가 재귀없이 문제를 지금 해결할 수 있다면, 함수는 단순히 값을 반환할 것이다.
• 만약 내가 재귀없이 문제를 지금 해결할 수 없다면, 함수는 문제를 뭔가 작고 비슷하게 줄이고, 스스로를 호출하여 문제를 해결할 것이다.

이 규칙의 사용을 흔한 수학 개념인 계승(!; 팩토리얼; Factorials)에 적용해보자. 만약 당신이 수학에서의 계승에 친숙하지 않다면, 다음의 링크를 참조하라. 계승

숫자 n의 계승은, n!로 표현딘다.

아래는 계승의 몇 가지 기본 규칙이다.

만약 n = 0 이라면 n! = 1 만약 n > 0 이라면 n! = 1 x 2 x 3 x ... x n

예를 들어, 숫자 9의 계승을 보도록 하자.

9! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9

사용자가 입력한 숫자에 대한 계승을 계산하는, 재귀의 방법을 사용하는 프로그램을 보도록 하자.

def main():
    num = int(input("자연수를 입력해 주세요.\n"))
    fact = factorial(num)
    print("자연수",num,"의 계승은",fact)

def factorial(num):
    if num == 0:
        return 1
    else:
        return num * factorial(num - 1)

main()

재귀는 또한 고급 주제인 제네레이터(generators; 생성기)에도 유용하다 . 수열 1,2,1,3,1,2,1,4,1,2... 을 생성하기 위해서 우리는 아래의 코드가 필요하다:

def crazy(min_):
    yield min_
    g=crazy(min_+1)
    while True:
        yield next(g)
        yield min_

i=crazy(1)

수열의 다음 요소를 얻기 위해서는 next(i) 를 호출한다.

← 불완전한 것 다루기

파이썬 3에서의 객체 지향 프로그래밍 소개 →