재귀함수

Recursive Function, 재귀함수 : 하나의 함수에서 자기 자신을 다시 호출하는 함수

 

 

---

 

 

귀납적 사고

어떤 문제를 재귀로 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것이다.

• 1번 도미노가 쓰러진다.
• k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.

위 조건 두 가지만 생각한 후 바로 "모든 도미노가 쓰러진다"라는 사고로 이어져야 한다.

 

귀납법
개별적인 특수한 사실이나 현상에서 그러한 사례들이 포함되는 일반적인 결론을 이끌어내는 또는 역으로 보편성에서 구체성을 유도하는 추론 형식 · 추리 방법

 

---

 

절차지향적 사고 vs 귀납적 사고

def recursive(n):
	if n == 0: # base condition
		return
	print(n)
	recursive(n-1)

절차지향적 사고

recursive(3) 호출 ⇒ 3 출력 ⇒ recursive(2) 호출 ⇒ 2 출력 ⇒ recursive(1) 호출 ⇒ 1 출력 ⇒ recursive(0) 호출

 

귀납적 사고

• recursive(1) 이 1을 출력한다
• recursive(k)가 k, k-1,... , 1을 출력하면 recursive(k+1)은 k+1, k,... , 1을 출력한다.
• recursive(k+1) 호출 => k+1 출력 => recursive(k) 호출 => k => ,, => 1출력

위 두 조건이 참이므로 귀납적으로 recursive함수는 n부터 1까지 차례로 출력하는 함수이다.

 

---

 

재귀함수의 조건

1. 재귀함수는 base condition을 가져야 하며, 이는 특정 입력에 대해서 자기 자신을 호출하지 않고 종료되는 조건이다.

2. 모든 입력은 base condition으로 수렴해야 한다.

 

이 두 조건 중 어느 하나라도 지켜지지 않는다면 재귀함수는 결과를 내지 못하고 무한히 돌다가 런타임 에러가 발생된다.

 

---

 

재귀함수 주의사항

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확히 정해야 한다.
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수로 만들 수 있다.
• 반복문보다 재귀로 구현했을 때 코드는 간결해지지만 함수호출 자체가 비용이 큰 연산이라 메모리, 시간에서 손해를 본다.
• 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다. EX. 피보나치 문제
• 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적된다. 이는 메모리 제한이 작게 걸린 문제에서 제약이 될 수 있다.