재귀(recursion)

'재귀'란 자기 자신을 다시 호출하여 자기 자신을 재참조하는 방법이다.

왜때문인지 나의 학식시절 교수님들께서는 재귀란 말을 안좋아하고 '되부름', '순환'으로 바꿔부르거나 그냥 'recursion'으로 부르곤 하셨다. ~~나는 청개구리이므로 재귀라 불렀었다.~~

재귀의 간단한 예를들면 아래와 같다.

def sum(n):
    if n==0: return 0   #base case
    return n+sum(n-1)
n=int(input())
print(sum(n))

n이라는 값을 입력받아 sum()이라는 함수를 호출하는 코드이다.

sum()함수를 살펴보면 n이 0일때 0을 반환하고, 그렇지 않다면 n+sum(n-1)을 반환하여 sum()을 다시 호출하게 된다. 이와같은 함수를 재귀함수 라고 한다.

이 때, n이 0일때 return 0 을 해줘서 끝내주지 않으면 프로그램이 끝이 나지 않게 되는데, 이 끝을 내주는 조건문을 기저사례(base case) 라고 한다.

예를들어 n=5일 때 위 함수의 실행과정을 살펴보면,

sum(5) = 5 + sum(4) 여기서 sum(5)는 다시 sum(4)를 호출하게 되고,

sum(4) = 4 + sum(3)

sum(3) = 3 + sum(2)

sum(2) = 2 + sum(1)

sum(1) = 1 + sum(0) 이와같이 호출하게 된다.

이렇게 각 값들은

sum(0) = 0, base case(n이 0이므로 0반환)

sum(1) = 1 + sum(0) = 1 + 0 = 1

sum(2) = 2 + sum(1) = 2 + 1 = 3

sum(3) = 3 + sum(2) = 3 + 3 = 6

sum(4) = 4 + sum(3) = 4 + 6 = 10

sum(5) = 5 + sum(4) = 5 + 10 = 15

이런식으로 반환하게 되고, 마지막에 반환되는 sum(5)의 값은 15이므로 결과적으로 15가 반환되게 된다.

참고로 위와 같이 n에서 0으로, 위에서 아래로 내려오는 방법을 top-down 방식이라 하고,

def sum(pos):
    if pos==n: return n
    return pos+sum(pos+1)
n=int(input())
print(sum(0))

이처럼 아래에서부터 올라가는 방법을 bottom-up 방식이라고 한다.

예제를 풀어보자.

팩토리얼 문제다. n이 작기 때문에 뒤에서 배울 DP의 메모이제이션을 사용하지 않고 풀 수 있다.

끝나는 점인 base case는 f(0) = 1 이고(0! = 1),

팩토리얼의 식은 f(n) = n*(n-1)*...*1 이다. 이 식을 재귀를 사용하고자 살짝 변형해주면 f(n) = n * f(n-1)으로 만들 수 있다.

이 식을 이용해서 코드를 짜주면 다음과 같다.

def f(n):
    if n==0: return 1   #base case
    return n*f(n-1)

이와 같이 식과 base case를 알면 쉽게 재귀를 짤 수 있다.

+python의 기본 재귀 깊이는 1000이므로 1000을 넘어갈거 같으면 아래와 같이 깊이를 설정해 줄 수 있다.

from sys import*
setrecursionlimit(10**6)

조녁이네