재귀적용법

3.1. 재귀적 용법

이번에 배울 것은 새로운 파이썬 문법은 아니구요, 프로그램을 짜는 테크닉 중의 한 가지인데 조금 머리가 아플 수도 있는 내용이랍니다. 하지만 최대한 쉽게 알려드릴 테니까 너무 걱정 마시고 함께 알아보도록 해요.

알아볼 내용이 무엇인고 하니, 함수가 자기 자신을 호출하는 '재귀'적인 용법입니다.

갑자기 어려운 것을 배우면 머리가 많이 아프실 테니까 먼저 준비운동을 하는 것이 좋겠군요. 다음의 예제를 봐주세요. 먼저 주어진 두 수를 합하는 함수를 만들어보겠습니다.

>>> def hap(a, b):
...   print(a + b)
...

제대로 만들었는지 확인을 해보세요. 이 함수를 어떻게 쓰는지 아시겠죠? 확인해보셨으면 두 수를 곱하는 함수도 만들어보세요.

>>> def gop(a, b):
...   print(a * b)
...

그럼 이번엔 두 수를 합해보고 곱해보고, 두 가지 일을 다하는 함수도 만들어 보겠습니다.

>>> def hap_gop(a, b):
...   hap(a, b)
...   gop(a, b)
...

이 함수는 자기에게 맡겨진 일을 직접 수행하지 않고 다른 함수들에게 시켜버리죠? 다시 말하면, 이 함수는 hap() 함수와 gop() 함수를 호출했다고 할 수 있습니다. 테스트를 한 번 해보세요. 재미 있으신가요?

이젠 본론으로 들어가겠습니다.

def countdown(n):
    if n == 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n-1)

이 함수는 무슨 일을 하는 함수일까요? 함수 이름을 보면 추측을 할 수도 있는데… 잘 모르시겠나요? 그렇다면 몇 줄 안되니까 직접 쳐보시지요.

제대로 만드셨으면 아래와 같이 사용을 해보시구요.

>>> countdown(3)
3
2
1
Blastoff!

이 함수는 매개변수로 받은 수부터 카운트다운을 하다가 0까지 오면 꽝!하는 일을 한답니다. '그런 거라면 for 문이나 while 문과 똑같잖아'하고 생각하는 분도 계시겠지만 코드를 가만히 보시면 차이점을 발견하실 거예요.

이 함수는 if, else 구조로서 n이 0인지 아닌지 따라서 다른 일을 하도록 되어 있습니다. 이 if 문에서 검사하는 n은 첫째줄에서 함수를 정의할 때 매개변수로 정해준 n과 같은 녀석입니다. 그러니까 매개변수에 3을 넣어서 함수를 호출하면, 즉 countdown(3)이라고 쓰면 함수 본체의 n값으로 3이 들어가는 것이지요.

n값으로 3이 들어오면 함수 내부에서는 어떤 일이 벌어질까요?

먼저 if n == 0: 에서 n값이 0과 같은지 비교합니다. n이 3이므로 n의 값과 0은 같지 않습니다. 그러면 else: 이후의 명령을 수행하겠지요.

다음 줄에 있는 print(n)은 n 값을 출력하라는 명령이니까 화면에 3을 출력해줍니다.

그 다음엔 countdown(n-1)이라고 되어있지요. countdown이라는 함수를 호출하면서 n-1 값을 매개변수로 넣어주라는 뜻입니다. 결국 countdown(2)와 같이 함수를 호출하게 되지요.

그런데 여기서 뭔가 이상하다는 것을 눈치채셨을 겁니다.

countdown이라는 함수에서 countdown을 호출한다?

예, 그것이 바로 오늘의 주인공, 재귀적 호출입니다. 함수가 자기 자신을 호출하는 것이죠.

머리가 복잡해지기 시작하신다면 생각을 잠시 덮으시고 countdown(2)라고 호출하면 어떤 일이 일어날지부터 함께 따져보죠.

먼저 if문에서 n 값이 0과 같은지 검사를 합니다. 검사 결과가 거짓이므로 else: 이후의 명령을 수행하겠죠. print(n)에서 n 값인 2을 화면에 출력해주고 그 다음 줄에서 countdown(1)을 호출합니다.

뭔가 감이 잡히시나요? 처음에 countdown 함수를 호출하면서 매개변수 값으로 3을 넣어줬는데 함수가 자기자신을 호출하면서 매개변수가 점점 작아지죠? 그렇다면 countdown(1)은 다시 countdown(0)을 호출하게 되는 것이 틀림없습니다.

그러면 countdown(0)에서는 무슨 일을 할까요? n == 0이면 print("Blastoff!")하라고 되어있으니 화면에 그렇게 출력해줍니다. '뻥이야~!'

그렇게해서 countdown 함수가 끝이 납니다. 지금까지 본 것이 모두 countdown(3)을 호출했을 때 일어나는 일들입니다.

이 일들을 하는 동안 countdown 함수는 네 번이나 호출되었지요. countdown(3), countdown(2), countdown(1), countdown(0). 맞나요?

어떠세요? 이해할 만 한가요? 좀 어렵긴 하지만 알고 나면 꽤 재미가 있지요.

사실 이 예제에서는 for 문을 이용해도 얼마든지 할 수 있는 일을 예로 들었지만 어떤 경우에는 재귀적 호출을 잘 사용하면 복잡한 프로그램을 아주 쉽게 만들 수도 있답니다.