[Python] 재귀함수(Recursive Function)

✏️ 재귀함수(recursive function)

👉🏻 재귀함수란, 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.
즉, 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 한다.

재귀함수 사용시 반드시 탈출 조건이 있어야 stack overflow를 방지할 수 있다.

✨ 다음 예시를 살펴보자.

def function(n):
    if n == 0:
        return
    else:
        print(n)
        function(n-1)
    
function(3)

# 결과
3
2  
1  

function(3)을 호출하면
=> function(2)를 호출하고 (메모리 영역이 구분되고 변수가 만들어진다.)
=> function(1)을 호출하고 (메모리 영역이 구분되고 변수가 만들어진다.)
=> function(0)이 되면 리턴한다. (메모리 영역이 구분되고 변수가 만들어진다.)
=> function(1)로 돌아가서 없어진다.
=> function(2)로 돌아가서 없어진다.

---

📌 재귀함수의 호출 및 리턴 과정

재귀함수는 호출과 리턴 과정을 이해하는 것이 중요하다.
이 과정을 이해하기 위해선 일반함수의 호출 및 리턴 과정에 대한 이해가 필요하다.

👉🏻 http://10bun.tv/beginner/episode-4/
위의 링크는 일반함수와 재귀함수의 호출 및 리턴 과정에 대해 알기 쉽게 설명해 놓았다.
아래 내용은 그 중 일부를 발췌하였다.

C 언어를 이용하여 프로그램을 작성하던 중에 main() 함수에서 "함수 A"를 호출했는데, 다시 "함수 A"에서 "함수 B"를 호출하고, "함수 B"가 다시 "함수 C"를 호출한 경우를 그림으로 표현한 것입니다.

• main() 함수 중간에 "함수 A"를 호출하면서 코드 진행이 "함수 A"의 처음 부분으로 옮겨갑니다.
• "함수 A" 함수 중간에 "함수 B"를 호출하면서 코드 진행이 "함수 B"의 처음 부분으로 옮겨갑니다.
• "함수 B" 함수 중간에 "함수 C"를 호출하면서 코드 진행이 "함수 C"의 처음 부분으로 옮겨갑니다.
• "함수 C"의 모든 실행을 마치면 "함수 B"에서 자신을 호출했던 다음 줄로 리턴(돌아감)합니다.
• "함수 B"의 모든 실행을 마치면 "함수 A"에서 자신을 호출했던 다음 줄로 리턴(돌아감)합니다.
• "함수 A"의 모든 실행을 마치면 main() 함수에서 자신을 호출했던 다음 줄로 리턴(돌아감)합니다.

대부분의 입문자의 경우에도 이렇게 함수가 호출되고 되돌아오는 과정은 무리 없이 직관적으로 받아들이는 것처럼 보입니다.

재귀호출의 경우에 입문자들이 오해하거나 알고는 있어도 머릿속에서 자연스럽게 떠올리는 그림입니다. 재귀함수 내에서 자신을 다시 호출하면 자신의 처음으로 돌아가서 실행된다고 오해하는 경우가 가끔 있습니다.

하지만 재귀함수 내에서 자신을 호출하는 경우에는 위의 그림과 같은 일이 벌어지게 됩니다. 모든 함수는 호출되면 메모리에 새로운 공간을 확보해서 매번 전혀 다른 공간에서 작업이 진행됩니다. 소스 코드에서는 같은 공간처럼 보이지만 실제 실행되는 코드는 전혀 다른 공간에서 이뤄진다고 생각하는 편이 좋습니다.

main() 함수에서 처음 재귀함수를 실행했을 때 "재귀함수 1"이라는 메모리 공간이 생겨서 작업을 진행하다가 다시 재귀함수를 실행한다면 새로 "재귀함수 2"이라는 메모리 공간이 생성되는 방식입니다.

이런 방식을 반복하다보면 같은 코드가 메모리 공간만 옮겨다니면서 무한히 반복되기 때문에 메모리가 부족할 때까지 멈추지 않고 반복하다가 프로그램이 종료되는데요, 이것 때문에 재귀함수를 작성할 때에는 언제 멈춰야 할지 탈출조건이 필요합니다.

위의 그림에서 "재귀함수 3"은 탈출조건을 만나서 실행이 멈추게되고 이후 이전 함수로 복귀하여 나머지 코드를 진행하고 다시 이전 함수로 복귀하는 과정이 계속 진행됩니다.

---

📌 재귀호출의 예

✨ 재귀함수의 호출 및 리턴 과정에 대한 이해를 마쳤으면 위의 예시를 다시 살펴보자. 이번에는 print(n)을 function(n-1) 다음 줄로 적어 리턴 과정을 살펴보자.

def function(n):
    if n == 0:
        return
    else:
        function(n-1)
        print(n)
    
function(3)

# 결과
1
2
3

=> 'function(0)'은 탈출 조건을 만나서 실행이 멈추고 이전함수인 'function(1)'로 복귀한다.
=> 'function(1)'의 나머지 코드인 print(1)가 실행되고 이전함수인 'function(2)'로 복귀한다.
=> 'function(2)'의 나머지 코드인 print(2)가 실행되고 이전함수인 'function(3)'로 복귀한다.
=> 'function(3)'의 나머지 코드인 print(3)가 실행되고 자신을 호출한 곳으로 돌아간다.

재귀함수는 메모리 성능면에서 보다 떨어지지만 간결한 코드를 제공하며 DFS/BFS 알고리즘 구현에 있어 꼭 알아야하는 개념이므로 제대로 이해하자.