10. 재귀¶

10.1. 재귀와 재귀함수¶

재귀recursion는 “본래 있던 곳으로 다시 돌아온다”는 의미로, 주어진 문제를 해결하기 위해 자기자신을 이용하는 기법을 말하며, 함수 본문에 자기자신을 호출하는 함수를 재귀 함수recursive function라고 부른다.

예를 들어, 자연수 n을 인자로 받아 n, n-1,… , 1을 출력한 다음에 발사!를 출력하는 함수 countdown()을 재귀를 활용하여 정의해보자.

n이 0 이하인 경우 : 발사! 출력
n이 양의 정수인 경우 : n을 출력한 다음 바로 countdown(n - 1) 호출

def countdown(n) :
    if n <= 0 :
        print('발사!')
    else :
        print(n)
        countdown(n - 1)

countdown(3)

3
2
1
발사!

위 코드를 보면, n이 양수인 경우 동일한 함수가 호출되지만 인자가 1씩 적어진다. 그리고 결국에는 인자가 0이 되어 실행이 멈춘다.

10.2. 재귀함수의 콜 스택¶

함수가 실행되는 동안 발생하는 모든 정보는 컴퓨터 메모리 상에서 프레임frame형식으로 관리된다. 이때 프레임은 하나의 함수가 실행되는 동안 발생하는 지역 변수의 생성 및 값 할당, 할당된 값 업데이트 등을 관리한다. 함수의 실행과 함께 생성된 프레임은 함수의 실행이 종료되면 스택에서 사라진다.

재귀 함수의 실행과정 동안에도 많은 프레임의 생성과 소멸이 발생하여, 경우에 따라 콜 스택의 변화가 매우 복잡해지기도 한다. 아래 그림은 countdown(3)을 호출했을 때의 콜 스택의 상태를 스택 다이어그램stack diagram으로, countdown(0)이 호출되어 콜 스택이 가장 높게 쌓였을 때이다.

스택 다이어그램의 변화는 다음과 같다.

프레임 생성 순서

Global frame => countdown 프레임(인자 3) => countdown 프레임(인자 2) => countdown 프레임(인자 1) => countdown 프레임(인자 0)

프레임 사멸 순서

countdown 프레임(인자 0) => countdown 프레임(인자 1) => countdown 프레임(인자 2) => countdown 프레임(인자 3) => Global frame

실제로 위 코드의 전체 실행 과정을 Python Tutor : 프레임의 생성과 사멸에서 확인해보면 함수 호출이 발생할 때마다 프레임이 생성되고 또 함수의 실행이 완료될 때마다 해당 함수의 프레임이 사멸하는 것을 확인할 수 있다.

스택stack, 콜 스택call stack, 스택 다이어그램stack diagram

프레임은 생성된 순서 역순으로 사멸한다. 즉, 가장 나중에 생성된 프레임이 가장 먼저, 가장 먼저 생성된 프레임이 가장 나중에 사멸한다. 이렇게 작동하는 구조가 스택stack이기에 함수의 프레임으로 구성된 스택을 콜 스택call stack이라 부른다. 스택 다이어그램stack diagram은 콜 스택의 변화를 다이어그램으로 표현한다.

10.3. 기저 조건와 무한 재귀¶

재귀 함수의 실행이 멈추려면 재귀 호출 과정에서 언젠가는 더 이상 자신을 호출하지 않아야 한다. countdown() 함수는 0과 함께 호출될 때 더 이상 재귀 호출을 하지 않는다. 이렇게 더 이상 재귀 호출이 발생하지 않도록 하는 경우를 종료 조건 또는 기저 조건base case이라 한다. 즉, countdown() 함수의 기저 조건은 n = 0이다.
반면에 아래 함수는 기저 조건을 갖지 않는다.

def count_infinitely(n):
    print(n)
    count_infinitely(n+1)

count_infinitely() 함수를 호출하면 재귀 호출이 무한정 반복됨을 쉽게 알 수 있다. 이러한 상황을 무한 재귀infinite recursion라 한다. 그런데 파이썬을 포함해서 대부분의 프로그래밍 언어는 재귀 호출의 무한 반복을 허용하지 않고 언젠가 아래와 같은 오류를 발생시키면서 실행을 중지시킨다.

RecursionError: maximum recursion depth exceeded while calling a Python object

최대 재귀 한도

파이썬은 최대 재귀 한도Maximum recursion depth를 정해 허용되는 재귀 호출의 최대 반복 횟수를 지정한다. 한도는 파이썬 버전과 운영체제에 등에 따라 다를 수 있으며 필요에 따라 조정하는 것도 가능하다.

사용하는 파이썬의 최대 재귀 한도는 다음 명령문으로 확인할 수 있다.

>>> import sys
>>> print(sys.getrecursionlimit())

재귀 함수를 실행해서 무한 반복에 빠지거나 최대 재귀 한도를 벗어났다는 오류 메시지가 발생하면 다음 두 가지 사항을 확인해야 한다.

기저 조건이 주어졌는가?
어떠한 경우에 기저 조건에 도달하는가?

하나라도 충족되지 않거나 확인할 수 없다면 해당 재귀 함수의 활용에 매우 주의를 기울여야 한다.

10.4. 재귀 시각화¶

재귀를 이해하기 위해 재귀 알고리즘의 작동과정을 시각화해보자. 시각화를 위해 turtle 모듈을 이용한다. 예를 들어, draw_spiral()함수는 아래 그림과 같은 소용돌이를 그린다.

import turtle

def draw_spiral(my_turtle, line_len):
    if line_len > 0:
        my_turtle.forward(line_len)
        my_turtle.right(90)
        draw_spiral(my_turtle, line_len - 5)


my_turtle = turtle.Turtle()
my_screen = turtle.Screen()
draw_spiral(my_turtle, 100)
my_screen.exitonclick()  #스크린을 클릭할 때, 창이 닫아준다. 

10.5. 재귀 활용 예제¶

10.5.1. 계승함수¶

자연수 n이 주어졌을 때, n의 계승 또는 n 팩토리얼factorial은 1부터 n까지의 곱으로, 기호로는 n!를 사용한다. n! = n × (n - 1)!이므로, n!을 계산하는 함수를 재귀를 이용하여 구현하면 다음과 같다.

종료 조건 : n == 0

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

print(factorial(1))
print(factorial(3))
print(factorial(5))

1
6
120

10.5.2. 피보나치 수열¶

피보나치 수열fibonacci sequence은 첫째와 둘째 항이 1이고, 그 뒤의 항은 바로 앞에 있는 두 항의 합인 수열을 말한다.

$1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, …

또는

fibo($1$) = $1$, fibo($2$) = $1$, fibo($n + 2$) = fibo($n$) + fibo($n + 1$) $\forall n \in \mathbb{N}$

종료 조건 : n == 1 or n == 2

def fibo(n) :
    if n == 1 or n == 2:
        return 1
    else :
        return fibo(n - 1) + fibo(n - 2)

print(fibo(1))
print(fibo(2))
print(fibo(4))
print(fibo(8))

10.6. 재귀 문제점¶

재귀를 사용하면 간결하게 코드를 작성할 수 있으며, 때로는 어려운 문제가 간단하게 해결되기도 한다. 반면, 재귀 알고리즘은 실행에 많은 시간이 걸린다는 문제가 있다. 예를 들어, 재귀를 활용하여 정의한 피보나치 함수는 fibo(7)를 계산하기 위해 fibo()함수를 24번이나 호출하고 있다(아래 그림과 파이썬 튜터 참고).

그렇다면 fibo(8)을 계산하기 위해 fibo() 함수를 몇 번이나 호출할까? 38번 정도를 호출한다. 이렇게 fibo() 함수는 인자가 커질수록 호출 횟수가 기하급수적으로 늘어난다. 사실 너무 커서 실질적으로 사용할 수 없다. 예를 들어, fibo(100)도 제대로 구하지 못한다.

10.6.1. 반복문 사용¶

보통 재귀적으로 해결할 수 있는 문제는 반복문을 사용하여 해결할 수 있다. for 반복문을 사용하여 피보나치 함수를 정의해보자.

def fibo2(n) :
    first = 1
    second = 1
    for _ in range(2, n) :
        first, second = second, first + second
    return second 

print(fibo2(100))

354224848179261915075

10.6.2. 메모이제이션¶

메모이제이션memoization은 한 번 호출되어 실행된 값을 저장해두고, 필요한 경우 다시 계산하지 않고 저장된 값을 사용하는 기법이다. 메모이제이션을 사용하여 피보나치 함수를 정의해보자.

memo_dict : 기저 조건이 저장되어 있고, 이후 계산되는 피보나치 수를 저장한다.

memo_dict = {1:1, 2:1}

def fibo3(n) : 
    if n not in memo_dict :
        memo_dict[n] = fibo3(n - 2) + fibo3(n - 1)
    return memo_dict[n]

print(fibo3(100))

354224848179261915075

10.7. 연습 문제¶

10.7.1. 문제¶

독일 수학자인 콜라츠Collatz, L.는 1937년에 아래 알고리즘을 얼마나 많이 반복하면 최종적으로 숫자 1에 다다를 것인가를 질문했다.

주어진 숫자가 짝수라면 2로 나눈다.
주어진 숫자가 홀수라면 3을 곱한 다음 1을 더한다.
실제로 숫자 7부터 시작해서 위 과정을 16번 반복하면 1에 다다른다.
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

반면에 숫자 128부터 시작하면 7번만 반복하면 된다.
128, 64, 32, 16, 8, 4, 2, 1
콜라츠는 어떤 자연수로 시작하든지 반복작업이 언젠가는 끝난다고 추측했는데, 아직 언제 끝나는가는 수학적으로 알아내지 못했다. 이를 콜라츠 추측이라고 부른다.
자연수 n을 입력받아 위의 알고리즘을 몇 번 반복하면 1에 다다르는지를 아래와 같은 형식으로 반환하는 collatz() 함수를 재귀를 사용하여 정의하여라.
In : collatz(128)
Out : 128->64->32->16->8->4->2->1

10.7.2. 문제¶

카탈란 수또는 카탈랑 수 Catalan number는 아래와 같이 정의된 자연수의 수열로, 개수 세기 문제counting problem들을 해결하는 과정에서 많이 나타난다.

$1$, $1$, $2$, $5$, $14$, $42$, $132$, $429$, $1430$, $4862$, …

음이 아닌 정수 $n$에 대해서, $n$번째 카탈란 수$C_n$는 다음과 같이 정의할 수 있다.
$$ C_n = \frac{(2n)!}{n!(n + 1)!} $$

또, 카탈란 수는 다음과 같이 점화식으로 나타낼 수도 있다. $$ C_0 = 1,\quad C_{n+1} = \frac{2(2n + 1)}{n + 2} C_n $$

n을 인자로 받아, n번째 카탈란 수를 반환하는 catalan_number() 함수를 정의하여라.

카탈란 수

$n$쌍의 괄호로 만들 수 있는 올바른 괄호의 개수는 카탈란 수 $C_n$이다. 예를 들어, 3쌍의 괄호로 만들 수 있는 올바른 괄호 구조는 5개로, 아래와 같다.
((())), ()(()), (())(), (()()), ()()()
$n + 2$각형을 $n$개의 삼각형으로 나누는 방법의 수는 카탈란 수 $C_n$이다. 예를 들어, 6각형을 4개의 삼각형으로 나누는 방법의 수는 14개로, 아래와 같다.

10.7.3. 문제¶

코흐 곡선Koch curve는 프랙탈fractal 중 하나로 다음과 같이 만든다.

선분을 하나 그린다.
각 변을 3등분해서, 한 변의 길이가 그 3등분한 길이와 같은 정삼각형을 만든다. 이때 밑변은 없앤다.
2의 과정을 계속 반복한다.

코흐 눈송이는 시작하는 도형이 정삼각형이고, 각 변에 대해 코흐 곡선과 같은 과정을 반복한다.

turtle 모듈을 이용하여 코흐 곡선과 코흐 눈송이를 그려라.

10.7.4. 문제¶

하노이 탑Tower of Hanoi 문제는 세 개의 탑 중에 하나의 탑에 쌓여 있는 다양한 크기의 원판들을 다른 탑으로 옮기는 게임이다. 단, 원판 이동 중에 아래 제한조건들은 반드시 지켜야 한다.

한 번에 한 개의 원판만 옮긴다.
큰 원판이 그보다 작은 원판 위에 위치할 수 없다.

예를 들어, 탑A에 있는 3개의 원판을 탑C로 옮기는 방법은 아래와 같다.

1. 작은 원판을 탑A에서 탑C로 옮긴다.

2. 중간 원판을 탑A에서 탑B로 옮긴다.

3. 작은 원판을 탑C에서 탑B로 옮긴다.

4. 큰 원판을 탑A에서 탑C로 옮긴다.

5. 작은 원판을 탑B에서 탑A로 옮긴다.

6. 중간 원판을 탑B에서 탑C로 옮긴다.

7. 작은 원판을 탑A에서 탑C로 옮긴다.

위 설명을 n개의 원판을 옮길 때로 일반화하면 다음과 같다.

n-1개의 원판을 중간 지점의 위치에 옮긴다.
가장 큰 원판을 목적지로 옮긴다.
중간 지점에 위치한 n-1개의 원판을 목적지로 옮긴다.

아래의 코드에 위와 같은 일을 하는 move_tower(n, from_tower, with_tower, to_tower) 함수를 정의하여라.

n : 원판 개수
from_tower : 출발 탑
with_tower : 중간 지점 탑
to_tower : 목적지 탑

하노이 탑

하노이 탑 문제에서 탑에 원판을 추가, 삭제하는 것은 스택에서 항목을 추가, 삭제할 때와 같다. 이에 하노이 탑 문제에서의 탑은 스택으로 정의할 수 있다.

# 시각화를 위해 turtle 모듈 임포트
from turtle import *

# 원판 클래스
class Disc(Turtle):                                              
    def __init__(self, n):
        Turtle.__init__(self, shape="square") #사각형 모양의 거북이 생성
        self.penup()           #원판이 움직일 때 자취를 남기지 않음
        self.shapesize(1.2, n*2)  #원판 두께는 모두 같고, 길이는 달라지게 설정.                                                         
# 탑tower 클래스
class Tower(list):
    def __init__(self, name, x):
        self.name = name
        self.x = x

    def message(self):
        penup()             #거북이가 움직일 때 자취를 남기지 않음
        goto(self.x, -220)  #아래 텍스트가 입력될 장소로 이동
        write(self.name, align="center", font=("Courier", 17))        
        
    def push(self, d):   
        d.setx(self.x)               #원판의 x좌표 설정             
        d.sety(-150+30*len(self))    #원판의 y좌표 설정
        self.append(d)               #원판을 타워에 추가

    def pop(self):
        d = list.pop(self)           #원판을 타워에서 제거         
        d.sety(150)                        
        return d                                        

# 원판을 옮기는 일을 하는 함수
def move_tower(n, from_tower, with_tower, to_tower):
    pass                              

# Enter를 눌렀을 때 실행할 함수
def play():
    clear()      #거북이는 그대로 두고 화면을 지움
    A.message()  #탑A 아래 A라고 표시
    B.message()
    C.message()
    move_tower(5, A, B, C)  #5개의 원탑을 이동시킴                                 

# 처음 실행할 함수
def main():
    global A, B, C

    A = Tower('A', -300)  #탑 객체 생성   
    B = Tower('B', 0)
    C = Tower('C', 300)
    
    for i in range(5,0,-1):  #탑A에 5개의 원판 넣기
        A.push(Disc(i))   
        
    penup()         #이동할 때, 자취를 남기지 않게 함
    ht()            #텍스트를 그릴 거북이는 안 보이게 함
    goto(0, -220)   #아래 텍스트가 입력될 장소로 이동. 0, -220로 이동.

    write("Press the Enter key", align="center", font=("Courier", 17))    #텍스트를 화면에 나타냄

    onkey(play, "Return")  #Enter키를 누르면 play() 함수 실행
    listen() #사용자의 입력을 기다림  
    return 


main()      #main() 함수 실행           
mainloop()  #turtle graphic 창을 종료할 때까지 프로그램을 실행

클래스 상속

클래스를 선언할 때, 다른 클래스의 상태state와 메서드method를 상속inheritance 받아 활용할 수 있다. 보통 상속을 받는 클래스를 자식 클래스 또는 하위 클래스, 상속을 해주는 클래스를 부모 클래스 또는 상위 클래스라고 부른다. 예를 들어, list, tuple, str 클래스는 Sequence 클래스를 상속하기 때문에 객체를 다루는 공통된 방식을 갖는다. 상속을 정의하는 방식은 다음과 같다.

class 자식클래스(부모클래스) :
    클래스 본문

클래스 상속을 활용할 때의 주요 장점은 다음과 같다.

기존에 작성된 코드를 필요에 따라 수정, 재활용할 수 있다.
데이터(객체) 사이의 관계를 보다 잘 이해할 수 있다.

모든 클래스에는 초기 설정 메서드인 init() 메서드가 포함되어야 한다. 만약 자식 클래스에 init() 메서드가 정의되어 있지 않다면, 부모 클래스의 init()메서드를 그대로 사용한다.

부모 클래스에서 선언된 메서드는 모두 자식 클래스에서 재정의할 수 있다.

아래 Tower 클래스는 리스트list 클래스를 상속받는다. 따라서 Tower클래스의 인스턴스는 list의 pop(), append() 등의 메서드를 사용할 수 있다.

# 탑tower 클래스
class Tower(list):
    def __init__(self, name, x):
        self.name = name
        self.x = x

아래 Disc 클래스는 Turtle 클래스를 상속받는다. 따라서 Disc클래스의 인스턴스는 Turtle의 __init__(), penup(), shapesize() 등의 메서드를 사용할 수 있다.

# 원판 클래스
class Disc(Turtle):                                              
    def __init__(self, n):
        Turtle.__init__(self, shape="square") 
        self.penup()           #원판이 움직일 때 자취를 남기지 않음
        self.shapesize(1.2, n*2)  #원판 두께는 모두 같고, 길이는 달라지게 설정.

Tower 클래스의 pop() 메서드

하노이 탑에서 탑은 스택으로 정의하고 있으며, 이를 위해 list 자료형을 활용하고 있다. 만약, 탑에 또는 스택에 항목을 추가하는 pop() 메서드를 정의하기 위해 아래와 같이 코드를 작성하면 어떻게 될까?

def pop(self) :
    d = self.pop()
    d.sety(150)
    return d

self.pop()의 내부에서 리스트의 pop() 메서드가 실행되기를 원하겠지만, 실제로는 pop() 메서드 안에서 다시 pop() 메서드를 호출하는 재귀 호출이 된다. 이러한 현상을 방지하기 위해 두 가지 선택을 해볼 수 있다.

스택에 항목을 추가하는 메서드 명을 다른 것으로 사용한다. 예를 들어, pop1()으로 사용할 수 있다.

def pop1(self) :
    d = self.pop()
    d.sety(150)
    return d

그러면, 문제 없이 동작한다. 하지만, 메서드 명이 변경되어 혼동스럽다.

list의 pop()메서드와 구별해주기 위해 아래와 같이 코드를 작성할 수도 있다.

def pop(self):
    d = list.pop(self)                   
    d.sety(150)                        
    return d     

10.7.5. 문제¶

재귀를 사용해 주어진 수열의 첫 원소를 포함하는 연속된 부분수열 중 부분수열 원소들의 최대합을 반환하는 subseq_max() 함수를 정의하라.

예를 들어, subseq_max([5, 3, -2, -1])은 아래와 같으므로 8이다.

5 + 3 - 2 - 1 = 5
5 + 3 - 2 = 6
5 + 3 = 8
5 = 5

또, subseq_max([2, -5, -3, 15, 17, -11])은 아래와 같으므로 26이다.

2 -5 -3 + 15 + 17 - 11 = 15
2 -5 -3 + 15 + 17 = 26
2 -5 -3 + 15 = 9
2 -5 -3 = -6
2 -5 = -3
2 = 2

10.7.6. 문제¶

앞 문제에서 정의한 subseq_max()와 재귀를 사용해 주어진 수열 안에 있는 모든 연속된 부분수열들에 대해 부분수열 원소들의 최대합을 반환하는 all_subseq_max() 함수를 정의하라.

예를 들어, all_subseq_max([5, 3, -2, -1])은 아래와 같으므로 8이다.

5 + 3 - 2 - 1 = 5
5 + 3 - 2 = 6
5 + 3 = 8
5 = 5
3 - 2 - 1 = 0
3 - 2 = 1
3 = 3
-2 - 1 = -3
-2 = -2

10.7.7. 문제¶

임의로 중첩된 리스트를 풀어 중첩이 없는 리스트로 반환하는 flatten() 함수를 재귀를 이용하여 구현하라.

>>> flatten([1, [2, 3, 4], [5, 6, [7, 8]]])
[1, 2, 3, 4, 5, 6, 7, 8]
>>> flatten([[4.8, 1.2], 3.3, [5.6, 7.2, 9.8]])
[4.8, 1.2, 3.3, 5.6, 7.2, 9.8]

10.7.8. 문제¶

편집 거리(edit distance)는 두 문자열의 유사도를 측정하는 방법 중 하나로, 한 문자열을 다른 문자열로 만드는데 필요한 최소한의 삽입(insert), 삭제(delete), 변경(substitute) 횟수를 계산해 측정한다.

예는 다음과 같다.

'cut'과 'cat' : 'u'를 'a'로 변경(편집 거리 : 1)
'hi'와 'hello' : 'i'를 'e'로 변경하고, 뒤에 'llo'를 삽입(편집 거리 : 4)
'dogs'와 'dog' : 's'를 삭제(편집 거리 : 1)

두 문자열을 인자로 받아 편집 거리를 반환하는 함수 edit_distance()를 재귀를 사용해 정의하라. 이때 두 문자열은 모두 소문자로 주어진다고 가정한다.

[주의] 문제에서 변경(substitute)은 하나의 문자를 다른 문자로 대체한다는 의미다. 문자의 순서의 교환을 의미하지 않는다.
예를 들어, 'ab'와 'ba'의 편집 거리는 2고, 'listen'과 'silent'의 편집 거리는 4다.

도움말

두 문자열의 처음 또는 마지막 문자부터 하나씩 처리하면 된다. 예를 들어, 마지막 문자부터 하나씩 처리할 때 마지막 문자가 동일하지 않다면
각 경우(삽입, 삭제, 변경)의 최소 횟수를 재귀적으로 구한 다음 최소값을 취하면 된다.

10.7.9. 문제¶

한 지점에서 다른 지점으로 가는 최소 비용을 구하려고 한다. 각 지점의 비용은 아래 그림 a와 같다. 처음 위치는 (0, 0)이며, 지점을 이동할 때는 오른쪽으로 한 칸, 아랫쪽으로 한 칸, 오른쪽 아래 방향의 대각선 칸(\ 방향)으로만 가능하다(그림 b참고).

위의 상황에서는 처음 위치 (0, 0)에서 (2, 2)로 갈 때의 최소 비용은 7(2 -> 1 -> 1 -> 3)이다.

비용 정보와 도착 위치를 입력 받아 최소 비용을 반환하는 min_cost() 함수를 정의하라.

입력값 첫 줄에는 비용 정보의 행(r)과 열(c) 크기가 들어온다. 그 다음 r개의 줄에 비용 정보가 들어오고, 마지막 줄에 도착 위치가 있다.
입력값1

출력값1

입력값2

출력값2

core_pybook

재귀

Contents