재귀 알고리즘

재귀 알고리즘(Recursive Algorithm)

어떤 함수가 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘

자기 자신을 호출하고 자기 자신으로부터 호출이 되는 함수를 재귀 함(Recursive Function), 이러한 호출을  재귀 호출(Recursive Call)이라 한다.

 

재귀적으로 문제를 해결한다는 것은 문제를 점점 더 작은 단위로 쪼개어 해결하는 것을 의미한다.

 

재귀 알고리즘의 특징

• 재귀 호출이 수행될 때마다 문제는 점점 작아져야한다.
• 재귀 호출이 종료되는 종료 조건(Terminate Condition)이 존재해야한다.

 

피보나치 수열

하노이의 탑

재귀 함수를 비재귀 함수로

• 재귀 함수는 비재귀 함수에 비해 속도가 느리다.
• 시스템 다운의 위험이 있다.

위 두가지 문제로 최적화 단계에서 재귀 함수를 비재귀 함수로 변환하게 된다.

비재귀 함수로 변환한 피보나치 수열 함수