정의:
재귀함수는 함수의 연장선으로, 함수 안에서 자기 자신을 호출하는 함수를 말한다. 이 재귀함수는 반복문(특히 while문)과 비슷하지만 각각의 장단점이 분명하다. 자신을 호출하는 함수이기에 함수가 처음 호출되었을 때 그 안에 있는 호출에 도달하면 또다시 호출되고 또 그 안에 있는 호출에 도달하면 또다시 호출되고... 를 반복하는 것이 재귀함수이다.
특징:
이 재귀함수는 자칫하면 무한 루프에 빠지기 쉽기 때문에 종료 시점을 잘 정해 주어야 한다. 재귀함수의 반복문과 비교되는 특징으로는, 반복문은 초기화, 종료 조건, 제어 변수 값 변경 등의 내용을 포함하는 반면, 재귀함수는 기본적으로 종료 조건만 포함한다.
장점:
재귀함수는 변수 사용이 반복문에 비해 비교적 적기 때문에 가독성이 높다. 또한, 구현할 알고리즘이 재귀함수의 표현이 자연스러운 경우가 있다. 재귀함수 예시의 대표격으로 보통 피보나치 수열을 드는데, 피보나치 수열이란 수열의 0번째 값은 0으로, 1번째, 2번째 값은 1로 설정한 후, 3번째부터는 f(n) = f(n-1) + f(n-2)식을 사용한 수열이다. 이는 반복문으로도 충분히 구현 가능하지만 재귀함수로 표현할 시 훨씬 직관적이고 간결하게 만들 수 있다.
#include <stdio.h>
int fibonacci(int n){
if(n == 1 || n == 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main(void){
printf("%d", fibonacci(4));
return 0;
}위 코드는 피보나치 수열 함수 fibonacci()를 구현한 코드이다. 만약 인자로 1이나 2를 전달받으면 1을 반환하고, 그게 아니라면 f(n - 1) + f(n - 2)값을 반환한다. 이 반환 과정에서 fibonacci 함수를 재귀하는데, 계속 값이 줄어들면 언젠가는 1과 2가 되기 때문에 1을 반환받고 이를 더한 것을 또 재귀하고.. 그런 방식이다.
단점:
사실 재귀함수에 대해서는 장점보다는 단점이 이야기할 것이 많은데, 일단 속도가 느리다. 한번에 프로세스를 여러 개를 처리하다 보니 속도가 느려질 수밖에 없다. 그리고 함수가 재귀호출 될 때마다 새로운 변수를 계속 만들어 저장하기에 메모리 사용이 비효율적이다. 또한 함수는 stack 메모리 영역을 사용하는데, 재귀가 많이 일어나다 보면 스택 오버플로우가 일어나 치명적인 문제를 초래할 가능성이 있다.
