[알고리즘] 재귀 함수

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

 

아래와 같은 함수가 재귀 함수이다.

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

 

그러나 이 코드를 실행시킨다면 "재귀 함수를 호출합니다." 라는 문장을 출력하다가 어느 순간 에러를 내며 멈출 것이다. 

RecursionError: maximum recursion depth exceeded while calling a Python object

이 오류 메세지는 재귀의 최대 깊이를 초과했다는 내용이다. 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 그 한계를 벗어났기에 다음과 같은 메세지를 출력한 것이다. 즉 위의 함수는 언제 끝날지는 없고 계~~속 자기 자신을 추가로 불러온다.

 

컴퓨터의 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 

 

재귀 함수의 가장 대표적인 예로는 팩토리얼(Factorial) 문제가 있다. (6! 갖고 싶음 방학때 운동해야지)

팩토리얼의 기호는 느낌표(!) 이고, 숫자 뒤에 붙혀 사용한다. n!의 의미는 1~n까지 모두 곱한다는 의미이다.

n! = 1 X 2 X 3 X ... (n-1) X n

0!과 1!의 값은 모두 1이다. 이 성질을 이용하여 팩토리얼 메서드는 n이 1 이하가 되었을 때 함수를 종료하는 재귀 함수의 형태로 구현할 수 있다.

 

반복과 재귀

 

물론 둘 다 같은 값을 출력한다. 코드를 비교했을 때 재귀 함수의 코드가 더 간결한 것을 알 수 있다. 이렇게 간결해진 이유는 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다. 수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.