재귀 (== 분할정복)

하나의 함수에서 자기 자신을 다시 호출하는 것으로 작업을 수행하는 알고리즘을 의미한다.

즉 귀납적인 사고 방식으로 문제를 해결하겠다는 뜻.

귀납적 사고는 위키백과 정의로 살펴보면 다음과 같다.

개개의 구체적인 사실이나 현상에 대한 관찰로 얻어진 패턴을 일반적인 규칙으로 이끌어나가는 절차

우리는 기본적으로 절차지향적 사고방식을 가지고 있다. 그렇다면 귀납적인 사고 방식과 절차 지향적 사고방식의 차이는 무엇일까?

다음과 같은 함수가 있다고 가정하자.

# 기본적인 재귀함수
def func(n: int):
	if n == 0:
    	return
   	func(n-1)

절차지향적 사고방식 : func(2)를 호출함 -> 2를 출력 -> func(1) 을 호출함 -> 1을 출력 -> func(0)을 호출함 -> 종료 과 같이 차례차례 사고과정을 이어가는 것을 의미한다.
귀납적 사고방식 : func(1)은 1을 출력함 -> func(k)는 k, k-1, ... 1 를 출력할 것임

즉 귀납적 사고방식은 하나의 현상을 토대로 규칙을 만든다는 의미.

그렇다면 이 귀납적 사고방식을 알고리즘으로 나타내기 위해서는 어떻게 해야할까?

만약에 하나의 함수 안에 아무런 조건 없이 매번 자기 자신을 호출하도록 만든다면.. 끊임없이 함수를 호출하다가 maximum recursion을 넘어서며 파이썬 기준 RecursionError가 발생하고 말 것이다.

def func(n: int):
   	func(n) # 무한 recursion이 발생한다.

때문에 재귀 함수를 구현하기 위해서는 항상 언제 이 재귀를 종료해야하는지에 대한 조건을 걸어야 한다.

BaaarkingDog 블로그에서의 정의를 보자면

재귀 함수의 조건은

이 두 조건이 성립하지 않게 된다면 재귀함수는 무한히 실행되다가 앞서 언급했던 런타임에러, Recursion Error가 발생한다.

사실 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다. 이때 재귀는 반복문으로 구현했을 때에 비해 코드는 간결해지긴 하나 메모리나 시간면에서 손해를 본다.
but.. 재귀함수가 동일한 입력값의 자기 자신을 여러번 호출하게 되면 오히려 굉장히 비효율적이다. 예를들어 피보나치 수열을 가정해보자면, fibo(5)는 fibo(4), fibo(3)을 호출하며 fibo(4)는 fibo(3), fibo(2)를 호출한다. 즉 이미 계산한 것을 또 계산하기 때문에 오히려 매우 비효율적이다. -> 다이나믹 프로그래밍으로 해결가능하다.
재귀함수가 자기 자신을 호출할 때는 스택 영역에서 누적된다. -> 메모리 제한에 의해서 recursion error가 발생한다.

티스토리툴바