[Python] 재귀함수

재귀함수란?

아마 다들 어디선가 이 글을 한 번쯤은 읽어봤을 것이다. (이거 보고 웃으면 빼빡 개발자...)

개발자들이 썰렁 개그에 진심인지라 개발자 커뮤니티에 재귀에 관해서 물어보면 꼭 이 농담이 나온다.

해외도 뭐...

 

심지어 백준에는 이런 문제도 있다.

17478번: 재귀함수가 뭔가요?

필자도 처음에는 저게 무슨 소리야 했는데 지금 다시 보니 재귀에 대해서 꽤나 잘 설명한 유머다. 이렇게 개발자화가 되는 것인가...

 

그래서 진짜 재귀란?

재귀함수는(이하 재귀) 자기 자신을 호출하는 함수다.

 

맞는 정의이지만, 이렇게만 보면 도대체 무슨 뜻인지 확 와닿지 않는다. 풀어서 설명하자면, 재귀를 실행하는 도중 다시 재귀가 호출되면 그 즉시 재귀 함수의 복사본을 만들어서 그걸 실행한다. 만약 복사본이 종료된다면 이 재귀를 호출한 재귀 함수를 종료하고 호출된 모든 재귀가 종료되면 끝난다. 아직도 잘 이해가 되지 않을 것이다. 그림과 같이 보자.

 

 

차근차근 순서대로 접근해보자.

 

recur 라는 함수가 있다. 그리고 이 함수는 n을 인자로 입력받는다. 함수는 return을 만나면 종료된다는 것은 이미 알 것이다. 함수가 실행되고, 3이라는 수를 인자로 받았다. 종료 조건, 즉 탈출 조건은 들어온 인자가 0이어야 하는데 조건과 부합하지 않음으로 함수는 또 다른 함수에 인자 2를 넣어 실행한다. 

 

또 다른 recur함수가 실행되었다. 개인적으로 복사되었다고 생각하는 게 이해가 잘 되었다. 여전히 recur(3)은 돌아가고 있고, recur(2)는 recur(1)을 호출했다. recur(1) 또한 탈출 조건을 만족하지 못했기 때문에 recur(0)을 호출한다. recur(3), recur(2), recur(1) 모두 탈출 조건을 만족하지 못해 계속 실행되고 있다.

 

n == 0 임으로 드디어 탈출 조건에 부합했다. recur(0)은 return을 만난 그 즉시 종료되어 자신을 호출한 recur(1)로 돌아갔다. recur(n - 1) 밑으로는 더 이상 실행돼야 할 코드가 없기에 recur(1)은 그 즉시 종료된다. recur(2)와 recur(3) 또한 마찬가지이다. 

 

이제 다시 한번 위에서 보았던 재귀의 정의를 다시 보자. 재귀는 자기 자신을 호출하는 함수이다. 자기 자신을 호출하여 실행하며, 복제된 모든 함수가 종료될 때까지 끝나지 않는다. 자기 자신을 복사해서 실행한다, 여기까지 이해하는 것은 문제없을 것이다.

 

그러나 재귀에서 제일 헷갈리는 지점은 바로 return이다. return 한 후에 무슨 일이 벌어지는가? 위의 함수는 아무것도 리턴하지 않지만, 만약 return n이라고 썼다면 과연 이 함수는 몇을 리턴하는가? 3? 0? 그리고 리턴한 직후에 복사본이 종료되면 재귀를 호출한 전 단계 재귀로 돌아가는데 (== recur(0)이 종료되면 recur(1)으로 돌아가는데) 어느 부분으로 돌아간다는 것인가? 

 

return 이후 일어나는 일

우선 리턴 값보단 어느 부분으로 돌아가는지 살펴보자. 재귀함수는 recur(n - 1)을 만난 그 즉시 실행된다. 

 

def recur(n):
    if n == 0:
        return
    recur(n - 1)
    print(n)

 

만약 위와 같이 코드가 짜여 있다면 과연 print(n)은 언제 실행되는 것일까? 정답은 recur(3) -> recur(2) -> recur(1) -> recur(0) 까지 가서 return을 만나 recur(0)이 종료되고 다시 recur(1)로 돌아갔을 때, recur(0)을 호출했던 recur(n - 1) 밑에 print(n)이 있기에 그제야 n을 출력한다. 여기서 n은 1이다. 왜냐면 recur(1)이니까.

 

print(n) 밑에 return이 생략되어 있다. c로 예를 들자면 main문 쓸 때 마지막에 retun (0) 명시적으로 쓰지만 안 써도 문제는 없다. 파이썬도 동일하다. 여하튼 함수의 끝을 만났기에 자기를 호출한 함수로 돌아가서 종료하고, 종료하고, 종료해서 더 이상 실행 중인 재귀가 없을 때 재귀는 종료된다. 

 

재귀는 탈출 조건을 만나야 종료가 되기 때문에, 이 조건을 무조건 명시해야 한다. 안 그러면 재귀는 무한으로 실행된다. 그전에 스택 오버플로우가 터져서 컴퓨터가 강제 종료시키겠지만. 그래서 나 같은 경우는 탈출 조건을 제일 위에 써놓는다. 그러면 탈출 조건을 까먹고 안 쓸 일도 없고, 무엇보다 내가 보기 편해서 저렇게 쓴다. 

 

재귀에 리턴 값이 있다면

지금까지 리턴 값이 없는 경우를 살폈다. 그런데 만약 아래와 같이 코드가 짜였다면 어떻게 될까?

 

def recur(n):
    if n == 0:
        return n
    recur(n - 1)

 

리턴 값은 3이다. 왜냐? print(n)과 마찬가지로 n을 리턴하는 것이니까. 문제를 바꿔보도록 하자. 우리가 만약 recur(0)의 값인 0을 최종적으로 리턴해야 한다면 어떻게 해야 할까?

 

def recur(n):
    if n == 0:
        return n
    return recur(n - 1)

 

답은 간단하다. 호출된 재귀가 리턴한 값을 그래도 리턴하면 되는 것이다. 이것을 설명하기 위해선 피보나치수열 구하기 문제들이 더 적절한 예시인데 궁금하다면 이 글을 읽어보길 추천한다. [Python] 다이나믹 프로그래밍 (DP)

[Python] 다이나믹 프로그래밍 (DP)

 

혹 위의 설명들이 부족하거나 하노이의 탑 문제의 해설이 궁금하다면 예전에 내가 깃허브에 썼던 글인데 11729 문제 해설 이걸 참조하길 바란다.

 

---

 

오늘의 TMI:

심심해서 만들어 본 쓸데없는 gif. 만들 때 열심히 만들었는데 막상 만들고 보니 쓸 곳은 없고 그냥 버리자니 아까워서 올려본다. 저거 어떤 툴을 쓴 게 아니고, ppt로 노가다 해서 만든 거다.