[파이썬] 알기 쉽게 풀어쓴 재귀 함수

안녕하세요.

오늘은 제가 파이썬을 하면서 이해하기 어려웠던 부분인 '재귀함수'에 대해 이야기해보려고 합니다.

재귀함수 란?

쉽게 말하자면 자기가 자기를 호출하는 함수입니다.

일반적인 함수는 다른 함수를 호출해서 실행하거나, 값을 반환하여 결과를 돌려줍니다.

하지만 재귀함수는 함수가 자기 자신을 호출하여 문제를 해결하는 방식으로 동작합니다.

그로 인해 복잡한 문제를 해결할 수도 있지만 무한루프에 빠질 수 있다는 단점이 됩니다.

왜 재귀 함수는 무한루프에 빠지나요?

종료조건이 없으면 무한 루프(프로그램의 명령을 무한히 반복)를 하게 됩니다.

예시 1)

def A(n):
    print(n)
    A(n-1)

A(1)

1. A(1) 호출 : 함수 이름이 A인 함수가 정의된 곳으로 이동(def)
2. print(1) 출력 :  n=1이므로 1 출력
3. A(1-1) 호출 : A(0) 함수 이름이 A인 함수가 정의된 곳으로 이동(def)
4. print(0) 출력 : n=0 이므로 0 출력
5. A(0-1) 호출 : A(0) 함수 이름이 A인 함수가 정의된 곳으로 이동(def)
6. A(-1-1), A(-2-1), A(-3-1) 계속 호출합니다.

예시 1을 보면 종료조건이 없기 때문에 음수가 되어도 계속 호출을 합니다.  이처럼 종료조건이 없으면 함수를 호출하여 코드를 실행하게 되는데 1,0이 호출되어서 끝나는 것이 아니라 음수-1,-2 등 n이 음수가 되어도 계속해서 호출이 됩니다. 

 

---

예시를 보면서 더 알아볼까요?

예시 2)

def A(n):
	print(n)
	if n>0:
		A(n-1)
A(3)

코드에 A(2)를 넣었을 때 

1. A(2)로 인해 함수(def A(n))로 이동
(이때 A(2)는 함수에 있는 함수명(식별자)을 호출해서 함수 안에 있는 코드를 실행함)
2. print(2) 출력
3. 조건문에 들어가 2>0을 만족하기 때문에 A(2-1)가 입력된다.
4. A(1)는 다시 함수(def A(n))로 이동한다.
5. print(1) 출력
6. 다시 조건문에 들어가 1>0을 만족하기 때문에 안에 있는 A(1-1)이 실행되어 A(0)이 입력
7. A(0)이 되면 if 조건(n>0)이 만족하지 않으므로 그대로 종료됩니다.

결과적으로 210이 되고 종료됩니다.

 

다음 코드를 봐볼까요?

예시 3)

def h (N):
    print(N)
    if N >0:
        h(N-1)
    print(N)
h(5)

코드에 h(2)를 넣었을 때

1. h(2)로 인해 함수(def h(n))로 이동
(이때 h(5)는 함수에 있는 함수명(식별자)을 호출해서 함수 안에 있는 코드를 실행함)
2. print(2) 출력
3. 조건문에 들어가 2>0을 만족하기 때문에 h(1)이 입력된다.
4. h(1)는 다시 함수(def h(n))로 이동한다.
(함수 h(N)을 호출했기 때문이다)
5. print(1) 출력
6. 다시 조건문에 들어가 1>0을 만족하기 때문에 안에 있는 h(n-1)이 실행되어 h(0)이 입력된다.
7.print(0)
8. h(0)이 되면 if 조건(n>0)이 만족하지 않으므로 함수가 종료됩니다. 
9. h(0)이 실행을 마치면, 스택에 쌓여있던  이전에 호출된 함수로 돌아와서 출력합니다.
10.h(0)->h(1)->h(2) 역순으로 출력됩니다. 

함수 h를 인자 N에 대해 호출하면, N부터 N-1, N-2, N-3,... 0까지 출력하고, 다시 N-4부터 N까지 역순으로 출력하는 결과를 얻을 수 있습니다. 결과적으로 210012가 되고 종료됩니다.

 

이해가 안 되실 수도 있습니다. 다시 차근차근 설명해 드리겠습니다.

왜 이렇게 다시 역순으로 돌아간 거야?

재귀함수의 특징입니다. 재귀함수는 함수가 스스로를 호출하다가 종료조건이 만족되면 호출 스택의 가장 위에 있는 함수부터 순서대로 실행되어 역순으로 결과를 출력하게 됩니다. 따라서 재귀 함수에서는 함수가 호출될 때마다 스택에 쌓이는데, 이 스택에는 함수가 호출된 순서대로 정보가 저장되기 때문에, 함수의 실행이 종료되는 경우에는 스택에서 가장 최근에 저장된 함수 정보를 꺼내어 이전에 호출된 함수에서 실행을 이어나가게 됩니다.

 

이때 스택이란?

항목을 순차적으로 나열하여 저장하는 방법입니다. 스택은 데이터를 넣고 꺼내는 입구가 같은 것입니다. 쌓는 형식이기 때문에 먼저 들어간 것이 가장 나중에 나옵니다. 실행취소와 역추적이 가능하다는 장점과 밑에 있는 데이터에 접근하고 싶으면 모든 데이터를 꺼내야 한다는 단점이 있습니다.

스택구조

다시 예시 3을 보면 스택에 쌓아놓았다가 종료조건을 만족하면 가장 마지막의 호출된 함수를 꺼내서 함수 실행을 이어나가게 됩니다.

예시3 스택 구조

예시 2는 왜 역순을 안 했어?

예시 2도 역순을 했습니다. 다만 print()를 하지 않음으로 인해 볼 수 없는 것입니다.

예시2와 예시3의 차이