재귀함수 - 파이썬(Python)

재귀함수란 함수 내에서 그 함수를 다시 사용하는 것을 말한다.

 

약간 인셉션 느낌이 드는 방식의 이 함수는 실제 코드를 보면 더 쉽게 이해될 수 있다.

 

def recursive():
	print("이것은 재귀함수입니다.")
    recursive()
    

recursive() #함수 호출

 

이 함수는 "이것은 재귀함수입니다." 를 무한히 출력하는 재귀함수이다.

 

recursive라는 재귀함수가 호출되면 print문을 수행하고 다시 recursive함수를 호출하는 모습이다.

 

하지만, 재귀적으로 진행되는 함수들은 모두 메모리의 스택에 지속적으로 쌓인 후 하나씩 pop하는 형식으로 실행된다.

 

그러나, 이렇게 쌓이는 데이터가 컴퓨터가 제어해놓은 스택의 제한(recursion depth라고도 부른다)을 초과하게 되면 해당 함수는 자동으로 종료된다. 일종의 무한루프를 끊어주는 용도라고 볼 수 있겠다.

 

 

 

재귀함수는 이론적으로 모든 for문이나 while문을 사용하는 반복문을 대신해서 사용될 수 있다.

 

반복문을 재귀함수로 사용하게 되면 보다 간결한 코드 작성이 가능해진다.

 

재귀함수를 이용해 작성할 수 있는 몇 가지 함수에 대해 알아보자.

 

1) 팩토리얼(Factorial) 함수

 

팩토리얼은 !를 기호로 사용해 특정 n 부터 1까지를 곱한 값을 구할 때 사용된다.

 

즉, 5! = 5 * 4 * 3 * 2 * 1 = 120이 되는 것이다.

 

팩토리얼 함수는 반복문과 재귀함수 모두로 구할 수 있다.

 

# 팩토리얼 반복문

def factorial(n):
	result = 1
	for i in range(1, n + 1):
    	result *= i
        
    return result
    
    
# 팩토리얼 재귀함수

def recursive_factorial(n):
	if n <= 1:
    	return 1
        
	return n * recursive_factorial(n-1)
    
print(factorial(5))
print(recursive_factorial(5))

 

 

두 함수 모두 동일한 값이 출력됨을 알 수 있다.

 

재귀함수를 쓸 때 중요한 것은, 부분계산을 잘 찾아내는 것이다.

 

예를 들어, 5!은 사실 5 * 4! 이다. 그리고 4! 또한 4 * 3! 이다.

 

이것을 활용한 코드가 n * recursive_factorial(n-1) 이 되는 것이다.

 

여기서 n이 0이거나 1일 때, 팩토리얼 0!, 1! 의 값은 모두 1이므로, 해당 부분만 return 값을 1로 처리해주면 되겠다.

 

 

2) 유클리드호제법

 

유클리드 호제법은 두 값 A와 B의 최대공약수를 구하기 위해 사용되는 로직 중 하나이다.

 

이 알고리즘의 전제는 A와 B의 최대공약수는 B와 A%B의 최대공약수와 같다는 것이다. (A > B 라고 가정)

 

이것의 수학적 증명은 '유클리드 호제법 증명'과 같은 키워드로 구글링 해보면 쉽게 알 수 있다.

 

# 유클리드 호제법 반복문
def gcd(a, b):
	while a % b != 0:
    	a, b = b, a % b
    
    return b


# 유클리드 호제법 재귀함수
def recursive_gcd(a, b):
	if a % b == b:
    	return b
    
    return recursive_gcd(b, a % b)

 

둘 다 간단한 방식이다. 하지만, 파이썬에서는 이를 아주 편하게 함수로 만들어놨다.

 

from math import gcd

 

gcd 함수에 파라미터로 a, b 값을 넣어주기만 하면 된다.

 

 

3)  피보나치 수열

 

피보나치 수열은 n번째 값이 (n-2)번째 값과 (n-1)번째 값을 더한 값임을 만족하는 수열이다.

 

즉, 1, 1, 2 (1+1), 3 (1+2), 5 (2+3), 8 (3+5), ..... 와 같은 수열이다.

 

피보나치 수열을 구현하는 함수 역시 재귀함수로 구현 가능하다.

 

def fib(n): # 피보나치 수열의 n번째 항의 값을 출력해주는 반복문 함수
    prev = 0
    crt = 1
    for i in range(n-1):
    	temp = prev
        prev = crt
        crt = prev + temp
        
	return crt

def recursive_fib(n): # 피보나치 수열의 n번째 항의 값을 출력해주는 재귀함수
	if n <= 2: # n = 1, 2 일때의 값은 1이므로
    	return 1

	return f(n-1) + f(n-2)
    
for i in range(1, 11): # 1 ~ 10항까지 피보나치 수열 출력
	print(recursive_fib(i))