재귀: 자기를 부르는 함수

재귀(recursion)는 함수가 자기를 다시 부르는 것입니다. 부를 때마다 새 칸이 쌓이고, 더 부르지 않고 바로 돌려주는 끝 조건(base case)에 닿으면 칸이 하나씩 사라지며 돌려준 값이 바로 위 칸으로 돌아옵니다.

1부터 3까지의 합은 '3 + (1부터 2까지의 합)'입니다. 이렇게 같은 일을 더 작은 수로 다시 하면 되는 계산은, 그 일을 하는 함수가 자기를 작은 수로 부르게 쓸 수 있습니다. 그림의 total(2)는 1과 2를 더합니다.

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

def total(n):    if n == 1:        return 1    rest = total(n - 1)    return n + restx = total(2)

1작게 줄여 자기를 부른다

그림의 total에 하는 일 셋을 주석으로 달고, 이번에는 3을 넘겼습니다. 주석이 늘어 줄 번호는 그림과 다릅니다. 칸이 몇 개 쌓이는지부터 세어 보세요. 무엇이 찍힐까요?

def total(n):
    # 1. 끝 조건
    if n == 1:
        return 1
    # 2. 작게 줄여 부르기
    rest = total(n - 1)
    # 3. 돌아온 값으로 계산해 돌려주기
    return n + rest


print(total(3))

6

2칸마다 n이 따로 있다

재귀에서는 같은 함수의 칸이 여럿 쌓입니다. 부를 때마다 새 칸이 생기고 그 칸의 매개변수 n이 따로 붙어, total(1) 칸의 n이 1에 붙어도 total(2) 칸의 n은 2 그대로입니다. 6번 줄이 부르는 total은 total 칸에 없는 이름이라 전역 칸에서 찾습니다(규칙 5). 함수 안의 이름, 밖의 이름의 이름 찾기 그대로입니다. 돌려준 값은 처음 부른 줄이 아니라 자기를 부른 바로 위 칸으로 갑니다. 그래서 끝 조건이 돌려준 1은 그대로 답이 되지 않고, 위 칸들이 하나씩 더해 가며 돌려줍니다.

3끝 조건이 없으면 칸이 끝없이 쌓인다

1번 하위 목표 '끝 조건'을 빠뜨렸습니다.

def total(n):
    rest = total(n - 1)
    return n + rest


print(total(3))

Traceback (most recent call last):  File "main.py", line 6, in <module>    print(total(3))          ~~~~~^^^  File "main.py", line 2, in total    rest = total(n - 1)  File "main.py", line 2, in total    rest = total(n - 1)  File "main.py", line 2, in total    rest = total(n - 1)  [Previous line repeated 996 more times]RecursionError: maximum recursion depth exceeded

멈출 곳이 없어 total(0), total(-1)로 칸이 끝없이 쌓입니다. 파이썬은 칸이 한도(기본 1000개)만큼 쌓이면 멈추고 RecursionError를 냅니다. 맨 아래 줄은 '재귀가 한도를 넘었다'는 뜻이고, 그 위의 'Previous line repeated 996 more times'는 바로 위 두 줄이 996번 더 되풀이됐다는 뜻입니다. 재귀 함수에는 더 부르지 않고 돌려주는 끝 조건이 있어야 하고, 부를 때마다 끝 조건 쪽으로 작아져야 합니다.

예제

부르기 앞에서 찍기

수를 하나씩 줄여 가며 자기를 부르는 함수입니다. 찍는 줄이 부르기 앞에 있습니다.

def down(n):
    if n > 0:
        print(n)
        down(n - 1)


down(3)

3
2
1

칸마다 먼저 자기 n을 찍고 아래 칸을 부르므로, 찍는 차례가 부르는 차례와 같습니다. down(0)은 조건이 거짓이라 아무것도 하지 않고 돌아옵니다.

부르기 뒤에서 찍기

3번 줄과 4번 줄의 차례만 바꿨습니다. 무엇이 찍힐까요?

def down(n):
    if n > 0:
        down(n - 1)
        print(n)


down(3)

1
2
3

자주 틀리는 곳

틀린 생각: 끝 조건이 돌려준 값이 곧 함수의 답이다.

끝 조건의 return이 마지막으로 실행되는 return처럼 보여, 그 값이 처음 부른 줄로 바로 갈 것 같습니다. 돌려준 값은 바로 위 칸으로 갑니다.

def total(n):
    if n == 1:
        return 1
    rest = total(n - 1)
    return n + rest


print(total(2))

3

total(2) 칸의 rest가 끝 조건의 1에 붙고, total(2)가 2 + 1을 계산해 3을 돌려줍니다.

맞는 규칙: 돌려준 값은 자기를 부른 바로 위 칸의 부른 자리로 갑니다. 끝 조건의 값은 위 칸들이 차례로 계산하는 재료가 됩니다(규칙 5).

틀린 생각: 재귀에서 n은 이름 하나라, 부를 때마다 그 값이 하나씩 줄어든다.

코드에 n이 한 번만 적혀 있어 n이 하나뿐인 것처럼 보입니다. 부를 때마다 새 칸이 생기고 그 칸에 n이 따로 붙습니다.

def show(n):
    if n > 0:
        show(n - 1)
        print(n)


show(2)

1
2

n이 하나라면 마지막에 0이 된 n을 두 번 찍었을 것입니다. 1과 2가 찍힌 것은 돌아온 칸마다 자기 칸의 n을 찍기 때문입니다.

맞는 규칙: 재귀로 부를 때마다 새 칸이 쌓이고 칸마다 n이 따로 붙습니다. 돌아온 칸은 자기 칸의 n으로 남은 줄을 실행합니다(규칙 5).

틀린 생각: 계산한 값은 return을 쓰지 않아도 부른 자리로 돌아간다.

5번 줄에서 n + rest를 계산했으니, 그 값이 부른 자리로 갈 것 같습니다. 값을 부른 자리로 돌려주는 것은 return뿐입니다.

def total(n):
    if n == 1:
        return 1
    rest = total(n - 1)
    n + rest


print(total(3))

Traceback (most recent call last):  File "main.py", line 8, in <module>    print(total(3))          ~~~~~^^^  File "main.py", line 5, in total    n + rest    ~~^~~~~~TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

total(2) 칸은 2 + 1을 계산만 하고 버린 채 끝나 None을 돌려줍니다. 그래서 total(3) 칸의 rest가 None에 붙어, 5번 줄에서 3과 None을 더하려다 멈춥니다. 맨 아래 줄은 'int와 NoneType은 +로 더할 수 없다'는 뜻입니다.

맞는 규칙: 부른 자리로 값을 돌려주는 것은 return뿐이고, return 없이 끝난 칸은 None을 돌려줍니다. 계산한 값은 return n + rest처럼 돌려줍니다(규칙 5).

확인 문제

1. 1절 코드의 마지막 줄을 print(total(4))로 바꿨습니다. 무엇이 찍힐까요?

def total(n):
    # 1. 끝 조건
    if n == 1:
        return 1
    # 2. 작게 줄여 부르기
    rest = total(n - 1)
    # 3. 돌아온 값으로 계산해 돌려주기
    return n + rest


print(total(4))

10

2. 3번 하위 목표의 빈칸을 채우세요. 다 채운 코드는 6을 찍고, 마지막 줄을 print(total(5))로 바꾸면 15를 찍어야 합니다.

def total(n):
    # 1. 끝 조건
    if n == 1:
        return 1
    # 2. 작게 줄여 부르기
    rest = total(n - 1)
    # 3. 돌아온 값으로 계산해 돌려주기
    return ____


print(total(3))

def total(n):
    if n == 1:
        return 1
    rest = total(n - 1)
    return n + rest


print(total(3))
print(total(5))

6
15

3. 계단을 오르며 층을 찍는 함수입니다. 무엇이 찍히는지 마지막 줄까지 글자 그대로 쓰세요.

def climb(n):
    if n < 3:
        climb(n + 1)
    print(f'{n}층')


climb(1)

3층
2층
1층

1
2
3
4
5
6
7
8
9
10
11