파이썬 - 재귀 함수 (recursive function)

재귀 함수

자기 자신을 호출하는 함수

어떤 함수에서 자신(함수)을 다시 호출하여 작업을 수행하는 방식의 함수이다.

함수내에 같은 이름의 함수가 올 때를 말한다.

함수 호출을 멈추기 위한 base case (종료되는 상황)이 1개 이상 존재하고 수렴할 수 있도록 작성해야 한다.

 

 

 

 

재귀함수로 팩토리얼 계산하기

def factorial(n) :
	if n==0:
		return 1
	return n*factorial(n-1)
    
print(factorial(3)) #6

 

예를 들어 팩토리얼 함수를 만들었다.

factorial 함수는 factorial 함수를 반환하여 다시 호출한다.

factorial(3)은 3*factorial(2)가 되고,

이것은 다시 3*2*factorial(1)이 되고, 다시 3*2*1*factorial(0)이 된다.

인자가 0일 경우에는 factorial(0)은 재귀함수를 호출하지 않고 1을 반환하기 때문에 3*2*1*1이 되어 결과값 6이 반환되는 것이다.

여기서 종료되는 상황인 base case는 인자가 0일 때를 말한다.