[Python] 재귀함수의 개념과 종료조건

재귀함수란?

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

즉, 함수 안에 자신의 함수를 가지고 있는 것이다.

예시

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

위 함수를 보면 A라는 함수 안에 A 함수를 다시 가지고 있는 것을 볼 수 있다.

이는 반복문의 효과를 가지게 된다!

 

예를 들자면, 위 함수에서 A(5)는

print(5) ➡️  A(4) ➡️ print(4) ➡️ A(3) ➡️ print(3)  이 과정을 무한 반복하게 한다!

>>>A(5)
5
4
3
2
1
0
-1
-2
#무한출력주의!!!

재귀함수 종료조건

따라서 무한출력을 방지하기 위해서는 종료 조건을 넣어줘야한다. (참고로 종료 조건을 넣는 방법은 아래 2가지.)

#if문
def A(x):
	if x>0:
    print(x)
    A(x-1)

#if, return 사용
def A(x):
	if x<=0:
		return
	print(x)
	A(x-1)

실제로 파이썬을 돌려보면 무한반복되지 않고 값이 출력되는 것을 볼 수 있다.

 

재귀함수 - 예제로 이해하기

def A(x):
	if x==0:
    		return 1
	return A(x-1)*2

위는, x가 0일 때 1을 리턴하고,

그렇지 않을 때, A(x-1)*2를 리턴하는 함수이다.

이 함수는 파이썬에서 실행했을 때의 결과로 알 수 있듯 A 라는 함수는 입력한 값을 2의 지수로 받아서 반환해준다.

왜 이런 결과가 나온 것일까??

 

x에 3이 들어가면 A(2)*2를 반환하고, A(2)가 시행된다.

A(2)는 A(1)*2을 반환하고, A(1)이 시행된다.

이 과정을 A(0)에 도달할 때까지 반복한다.

A(3)              →	A(2)*2
A(2)              →	A(1)*2
A(1)               →	A(0)*2
A(0)              →	1
A(3)              -->	2*2*2*1

 

위 표를 거꾸로 거슬러 올라가보자.

A(0)에 1을 대입하면, A(1)은 1*2가 된다.

A(1)에 2를 대입하면 A(2)는 2*2가 된다.

A(2)에 2*2를 대입하면 A(3)은 2*2*2가 된다.

 

이러한 과정으로 재귀함수의 값이 반환되는 것을 알 수 있다.