재귀 알고리즘(recursive algorithm)
자기 자신을 내부에서 호출할 수 있는 함수를 재귀 함수라고 함. 재귀 알고리즘(recursive algorithm)이란 재귀 함수를 이용하여 문제를 해결하는 알고리즘을 말함. 재귀 알고리즘은 팩토리얼, 피보나치 수열 등에 쓰임.
재귀 함수와 반복문의 차이
재귀 함수와 반복문은 속도나 작동 박식에서 차이가 남. 반복문은 프로그래머가 지정해준 초기값, 조건값, 증감값을 통해 반복을 제어하고 재귀 함수는 함수가 수렴하거나 조건문을 통해 재귀 호출을 종료하는 방식으로 반복을 제어할 수 있음. 반복문은 반복되는 횟수를 계산하기 편하고 재귀 함수보다 속도가 빠름. 그러나 재귀 함수는 반복되는 횟수를 알기 어렵고, 재귀 함수 특성상 스택의 오버플로우를 발생시킬 수 있다는 문제와 반복문에 비해 속도가 느리다는 단점이 있음.
재귀 함수는 문제 자체가 재귀적인 경우에 사용한다. 재귀적인 문제란 팩토리얼, 피보나치같이 한 부분이 전체와 같은 형태를 띄는 문제들을 말함. 팩토리얼을 예로 들면 n! = n*(n-1)!, (n-1)! = (n-1)(n-2)!과 같은 형태를 반복하게 됨. 이런 문제를 해결할 때 재귀 함수를 이용하면 가독성이 높아짐.
hi