파이썬 독학, 재귀 함수(recursion)을 공부해봤다.

이전 포스팅에서 말했듯이, 나는 현재 파이썬을 독학하고 있다. 현재 '프로그래밍 기초'를 끝내고, 코드를 조금 더 효율적으로 짜기 위해서 '알고리즘의 정석'을 듣고 있다. '프로그래밍 기초'를 공부할 때는 그럭저럭 이해하면서 금방금방 따라 할 수 있었다. 하지만 '알고리즘의 정석'으로 들어온 뒤부터 난이도가 급상승하였다. 급상승하는 난이도만큼 나의 미간도 찌푸려져만 갔다.

 

물론 '프로그래밍 기초'에도 해당되는 이야기지만, 지금부터는 꾸준한 반복과 복습을 하지 않는 이상 도저히 다음 단계로 넘어갈 수 없어보인다. 그래서 내가 배운 내용을 다시 한번 더 되뇌기 위해서 지속적으로 포스팅하려고 한다. 그 첫 번째로 오늘은 '재귀 함수'를 포스팅해보려 한다. '재귀 함수'는 말 그대로 "원래 자리로 되돌아가거나 되돌아옴"이라는 뜻을 가지고 있는 함수다. 어떠한 것을 정의할 때 자기 자신을 참조한다는 것이다. 다들 이런 이야기를 한 번쯤 들어본 적이 있을 것이다. 굉장히 기분 나쁜 악몽을 꾸고 있는데, 그 악몽 안에서 또 악몽을 꾸는 이야기. 영화에서는 비슷하게 '인셉션'이라는 영화가 있다. 고등학생일 때 '인셉션'을 봤었는데, 꿈속에서 꿈속으로, 또 꿈속에서 꿈속으로 반복해서 들어가는 이야기는 지금 생각해도 충격적이고 신선한 소재이다. 그때 당시 마지막 장면에서 팽이 논란은 월드컵만큼 뜨거웠던 것 같았다. 딴 길로 새는 이야기는 여기서 각설하고.

 

나는 이 '재귀 함수'를 이해하는데 생각보다 시간이 걸렸다. 문제를 풀어보고, 풀이 과정을 반복해서 봤다. 다른 사람이 다른 방식으로 짠 코드도 계속 찾아봤다. 그러다가 그나마 쉽게 이해를 할 수 있는 팁을 하나 발견했다. 그건 바로 "return에 반드시 자기 자신을 다시 넣는다는 것"이다. 이게 별거 아닌 것처럼 보이지만, 나는 이걸 깨닫고 나서 재귀 함수 문제를 조금더 빨리 풀 수 있었다. 함수를 더 이상 쪼갤 수 없을 때까지 쪼갠 값을 조건으로 걸고, 마지막은 무조건 자기 자신을 불러내면 되는 것이다.

 

'재귀 함수' 예시로 보통 수학의 '!(factorial)'이 많이 나온다. '팩토리얼'을 잠시 살펴보면

1! = 1

2! = 2 * 1

3! = 3 * 2 * 1

이렇게 이루어져 있다.

 

이걸 조금만 수정을 하면

1! = 1

2! = 2 * 1!

3! = 3 * 2!

이렇게 바꿀 수 있다.

즉, n! 은 n * (n-1)! 인 것이다.

 

 

 

이 '팩토리얼'을 '재귀 함수'를 써서 코딩을 해보자. 먼저 쪼갤 수 없는 작은 단위를 찾아보면 1! 가 나온다. 1! 는 자기 자신이 1! 이기 때문이다. 따라서 factorial(n) 함수의 가장 작은 단위 조건을 써주면

 

def factorial(n):

    if n == 1:

        return 1

 

이렇게 써줄 수 있다. 그리고 다시 if문을 나와서 return을 써줄 때 자기 자신을 넣으면 된다. 우리는 이미 반복되는 공식을 위에서 구했다.

 

def factorial(n):

    if n == 1:

        return 1

 

    return n * factorial(n - 1)

 

이게 끝이다. 여기서 n에다가 4를 넣어주게 되면 n은 1이 아니기 때문에 아래 return 부분으로 가서 4 * factorial(3)을 불러내게 된다. 그러면 factorial(3)을 구하기 위해서 다시 factorial 함수가 시작되고 3은 1이 아니기 때문에 3 * factorial(2)가 불러진다. 이렇게 반복하면 결국 facotorial(1)이 나오게 되고 n이 1이 되어 1이라는 값을 불러내고, 차례대로 함수가 풀이된다.

 

'재귀 함수'에서 제일 기초라고 할 수 있는 '팩토리얼' 함수부터 시작해서 차근차근 이해하면 조금 더 어려운 '재귀 함수' 코드를 짤 수 있다. 개인적으로 제일 어려웠던 것은 '하노이의 탑'이었다. 나중에 짜여진 코드를 보면서 어떻게 코드가 흘러가는지는 이해했지만, 솔직히 아무것도 없이 처음부터 코드를 짜보라고 하면 나는 코드 짜는 것을 포기할 것 같다.

 

아직은 여태까지 풀었던 '재귀 함수' 코드들을 조금 더 복습하고 다음 단계로 넘어갈 예정이다. 다음 단계 코드를 만나게 되면 그때 다시 파이썬 독학 포스팅을 하게 될 것 같다.