[알고리즘] Recursion

1. 재귀함수란?

‘어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 재참조하여 정의할 때’를 재귀적(recursive)라고 한다. 즉, 자기 자신과 똑같이 동작하는 함수를 재귀함수라고 한다.

2. 재귀함수는 왜 쓰는지

• 알고리즘 자체가 재귀함수를 쓰는 것이 자연스러울 때 코드의 가독성이 좋아지기 때문에.
• 변수 사용을 줄여줄 수 있다.(=mutable state를 줄일 수 있다)
  mutable state : 변경 가능한 상태(dict의 value, 리스트)

3. 재귀함수는 언제 쓰는지

• 동일한 로직이 반복될 때
• 재귀 함수로 구현이 가능한 것은 while문이나 for문으로도 구현이 가능하다.
• (물론 그 반대도 가능)

4. 재귀함수의 동작 원리

• 재귀함수의 가장 대표적인 사용 예제

# 팩토리얼
def factorial(n):
	if n==1:
		return 1
	return n*factorial(n-1)

 

함수를 호출할 때마다 콜스택에는 함수의 매개변수, 지역변수, 반환주소값 등을 모두 저장하게 된다.

이때, factorial(5)를 호출하게 되면 반환타입 부분에서 5*factorial(4)가 수행이 되면서 factorial(4)가 호출이 되고 반환을 기다리게 된다.

그다음에는 factorial(4)에 대한 지역변수, 매개변수, 반환주소값 등이 콜스택에 쌓이게 되고 이후 차례대로 factorial(3,2,1) 함수가 콜스택에 쌓인다.

재귀함수의 필수 조건인 종료 조건문이 들어가 있으면 n==1에 걸려 해당 콜스택이 하나씩 수행되며 사라진다.

 

5. 재귀의 단점

재귀가 수 없이 반복되어 스택메모리에 함수가 차곡차곡 쌓이다가 더 이상 스택메모리에 함수의 정보를 저장할 수 없을 때 스택오버플로우가 일어난다.

또한, 스택오버플로우가 일어나지 않더라도 함수의 정보를 저장하는 과정에서 콜스택의 부하로 인한 메모리낭비가 일어나는데 이를 해결하기 위해서는 꼬리 재귀를 사용하면 해결이 가능하다.

꼬리 재귀는 재귀 호출이 끝나는 시점에서 아무 일도 하지 않고 바로 결과를 반환하는 방법인데 함수의 상태 유지 및 추가 연산을 하지 않기에 스택오버플로우를 해결할 수 있다.

# 꼬리 재귀를 사용하지 않은 recursion
def factorial(n):
	if n==1:
		return 1
	return n*factorial(n-1)

# 꼬리 재귀를 사용한 recursion
def factorial(n, total):
	if n==1:
		return total
	return factorial(n-1, n*total)

차이점을 보면 반환 부분의 코드가 달라졌다.

이처럼 꼬리 재귀의 핵심은 반환부에 연산이 없어야 한다.

 

즉, 정리하자면

일반 재귀함수는 코드가 간결하고 읽기 쉽지만 함수가 호출될 때마다 새로운 스택을 생성하기 때문에 스택 오버플로우 문제가 발생할 수 있고 함수를 호출하는 횟수가 많아지면 성능 저하가 일어날 수 있다.

꼬리 재귀함수는 재귀 호출 시 현재까지 구한 값을 함수의 매개변수로 넣어서 전달하기 때문에 새로운 스택을 생성하지 않고 다음 재귀호출에서 다시 사용되어 스택 오버플로우 문제를 해결할 수 있고 메모리 낭비의 문제도 잡을 수 있다.
그러나, 파이썬은 꼬리 재귀 최적화를 지원하지 않으므로 함수가 호출하는 횟수가 많아질 경우에는 꼬리 재귀를 사용했다 하더라도 성능 저하가 일어날 수 있다.