[Algorithm] 4-(2) 재귀함수

[Algorithm] 4-(2) 재귀함수

 

 

 

1. 개념과 특징

 

자기 자신을 다시 호출하는 함수다. DFS를 실질적으로 구현하고자 할 때 사용하기도 한다.

 

def recursive_function():
	print(‘재귀 함수를 호출한다.’)
	recursive_function()

recursive_function()

 

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 즉, 다시 자기자신을 부르는 return값 이외에 일정 조건(종료조건)이 되면 return 해주는 식이 있어야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. 파이썬은 최대 재귀 깊이 제한이 있다. 조건을 두지 않고 재귀적으로 함수를 호출하면 무한으로 생성되지 않고 오류가 나면서 종료된다.

 

 

반복문 말고 점화식을 그대로 쓸 수 있는 장점이 있다. (팩토리얼 함수를 구현해주는 역할)

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

이렇게 점화식을 직접 집어넣어서 연산을 진행할 수 있다.

 

 

등차수열의 n번째 까지의 합을 구할 수도 있다.

 

def suyal_sum(n):
	if n <= 1:
		return 2
	
    return 2 + 4*(n-1) + suyal_sum(n-2)

print(suyal_sum(10))

 

 

 

 

 

최대공약수 계산(유클리드 호제법)을 할 수도 있다.

 

두 자연수 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))

 

 

2. 재귀 함수 사용의 유의사항

 

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다. 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용해야 한다. 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다. 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있기 때문에 정당성, 타당성 분석 필요하다.

 

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다. 재귀 함수를 사용할 때, 메모리 사용도 주의를 하여야 한다.