재귀 함수 Recursive Function

재귀함수(Recursive Function)
자기 자신을 다시 호출하는 함수를 의미한다

간단한 코드

def recursive_function():
		print('재귀 함수를 호출합니다')
		recursive_function()

recursive_function()

이 코드를 실행하게 되면 ‘재귀 함수를 호출합니다’ 라는 문자열을 무한히 출력하게 됩니다.그리고 일정 시기가 되면 오류메시지를 출력하고 멈추게 됩니다

재귀함수의 종료 조건

재귀함수가 이렇게 무한히 반복이 되기 때문에, 언제 끝날지 종료조건을 꼭 알려줘야합니다. 그렇지 않으면 계속 무한 루프처럼 반복하게 되는 것입니다.

대표적으로 if문이 종료 조건 역할을 합니다.

출처: How to Think Like a computer Scientist

def countdown(n): #n매개변수로 한 countdown이라는 함수를 생성
    if n == 0: #만약 n이 0과 같다면
        print("Blastoff!") #"Blastoff!"를 출력해줘라
    else:  #그 밖의 경우에는
        print(n) #n을 출력해주고
        countdown(n-1) #countdown n값에서 -1을 뺀 함수를 호출해줘라

n이 만약에 3이 들어온다면

1. if n ==0;에서 n과 0이 같은지 비교해봅니다 같지 않기 때문에 else문으로 가게 됩니다
2. else문에 가게 되면 n값을 출력해주고 countdown(n-1)을 해주게 됩니다

이렇게 되면 결국은 함수가 자기 자신을 호출하게 되는 것이지요!

여기서 알아야 할 점은 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다는 것입니다!!!!

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문입니다.

팩토리얼
기호는 !를 사용하며, n!는 1 x 2 x 3 x ... x (n-1) x n을 의미합니다
수학적으로 0!와 1!의 값은 1로 같다는 성질을 이용하여 n이 1이하가 되었을 때 종료하는 재귀함수의 형태입니다.

코드로 옮겨보겠습니다.

def factorial_recursive(n):
		if n <= 1:
				return 1
		return n * factorial_recursive(n-1)

print(factorial_recursive(5))

이렇게 되면 결과적으로

120의 값이 나옵니다.

팩토리얼을 점화식으로 표현한다면
1. n이 0 혹은 1일때: factorial(n) =1
2.n이 1보다 클때: factorial(n) = n X factorial(n-1)

팩토리얼은 n이 양의 정수일 때만 유효하기 때문에 n이 1이하인 경우를 고려하지 않으면 재귀함수가 무한히 반복되므로 1이하인 경우에는 1을 반환할 수 있도록 해야한다.
if문을 사용하는 것을 추천합니다.

출처: 이것이 코딩테스트다 나동빈 님의 책을 기반으로 공부한 부분을 정리한 것입니다.