4/11 재귀함수

함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 합니다. 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다(구현은 만들다와 같은 뜻입니다). 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다.

이번에는 재귀호출을 사용하는 방법을 알아보겠습니다. 참고로 재귀호출은 코드가 간단한 편이지만 머릿속으로 생각을 많이 해야 됩니다.

먼저 간단한 재귀호출 함수를 만들어보겠습니다.

def hello():
    print('Hello, world!')
    hello()
 
hello()

실행 결과

Hello, world!
Hello, world!
Hello, world!
...(생략)
Traceback (most recent call last):
  File "C:\project\recursive_function_error.py", line 5, in <module>
    hello()
  File "C:\project\recursive_function_error.py", line 3, in hello
    hello()
  File "C:\project\recursive_function_error.py", line 3, in hello
    hello()
  File "C:\project\recursive_function_error.py", line 3, in hello
    hello()
  [Previous line repeated 974 more times]
  File "C:\project\recursive_function_error.py", line 2, in hello
    print('Hello, world!')
RecursionError: maximum recursion depth exceeded while pickling an object

hello 함수 안에서 다시 hello 함수를 호출하고 있습니다.

소스 코드를 실행해보면 'Hello, world!' 문자열이 계속 출력되다가 에러가 발생합니다. 왜냐하면 파이썬에서는 최대 재귀 깊이(maximum recursion depth)가 1,000으로 정해져 있어서 그렇습니다. 즉, hello 함수가 자기자신을 계속 호출하다가 최대 재귀 깊이를 초과하면 RecursionError가 발생합니다.

재귀호출을 사용하려면 반드시 다음과 같이 종료 조건을 만들어주어야 합니다.

def hello(count):
    if count == 0:    # 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return
    
    print('Hello, world!', count)
    
    count -= 1      # count를 1 감소시킨 뒤
    hello(count)    # 다시 hello에 넣음

실행 결과

Hello, world! 5
Hello, world! 4
Hello, world! 3
Hello, world! 2
Hello, world! 1

먼저 hello 함수의 반복 횟수를 계산하기 위해 매개변수 count를 지정합니다. 그리고 count가 0이면 hello 함수를 호출하지 않고 끝냅니다. 만약 0이 아니면 'Hello, world!'를 출력하고, count의 값을 1씩 감소시킨 뒤 hello 함수를 호출할 때 넣어줍니다.

재귀함수는 어떤 것을 재귀함수로 다시 받아올지, 종료 조건은 어떤 것으로 할지가 중요합니다!

재귀함수를 응용한 문제를 풀어보았습니다.

문제 링크

[Silver I] 하노이 탑 - 1914
문제 링크

성능 요약
메모리: 31256 KB, 시간: 884 ms

분류
임의 정밀도 / 큰 수 연산, 재귀

문제 설명
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.

입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력
첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

import sys
sys.setrecursionlimit(10**8)

def hanoi(n: int, x: int, y: int):

    if n == 1:
        print(x, y)
        return

    if n > 1:
        hanoi(n - 1, x, 6 - x - y)

    print(x, y)

    if n > 1:
        hanoi(n - 1, 6 - x - y, y)



n = int(sys.stdin.readline())

hanois = (2 ** n - 1)
print(hanois)

if n <= 20 :
    hanoi(n, 1, 3)