재귀 함수(Recursive Function)

재귀함수란?

재귀함수는 자기 자신을 다시 호출하는 함수를 의미한다.

ex) 단순한 형태의 재귀 함수 예

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

=> 어느 정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력된다. 파이썬은 재귀를 호출하는 과정에서의 깊이 제한이 있기 때문에 별다른 설정없이 재귀 호출하면 오류가 난다. 실제로 컴퓨터 시스템상에서 함수가 재귀적으로 호출되면 스택에 함수가 쌓여서 메모리가 올라가게 된다. 메모리는 한정된 크기 만큼의 자원을 가지고 있기 때문에 무작정 함수가 종료되지 않고 재귀적으로 호출하게 되면 빠르게 메모리가 가득 차서 문제가 생길 수 있다.

 

팩토리얼 구현 예제

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
        result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n<=1: # n이 1 이하인 경우 1을 반환
        return 1
    # n! = n*(n-1)!를 그대로 코드로 작성하기
    return n* factorial_recursive(n-1)

print('반복적으로 구현 : ', factorial_iterative(5))
print('재귀적으로 구현 : ', factorial_recursive(5))

 

[실행 결과]

반복적으로 구현 : 120 재귀적으로 구현 : 120

 

최대 공약수 계산(유클리드 호제법) 예제

- 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다.

- 유클리드 호제법:

 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자.

이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

- 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 잇다.

 

def gcd(a, b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

print(gcd(192,162))

 

[실행결과]

6