최근 수정:
위의 링크를 계속 누르는게 재귀함수이다.
Recursive (function). 재귀함수.
재귀함수는 함수 내에서 그 자신의 함수를 호출하는 것이다. 재귀적으로 함수를 호출한다 해서 재귀함수라 한다.
함수에서 또다른 함수를 호출하게 되면 스택 메모리에 호출한 함수가 쌓이고 실행이 넘어가게 된다. 이때 자기 자신을 한 번 더 호출하는데 만약 함수에서 빠져나가는 조건(기저 라고 한다)가 없다면 무한 루프를 돌게 되며 흔히 스택오버플로우로 컴퓨터가 뻗어 버린다!
따라서 재귀함수를 구현할 때는 기저에 많은 신경을 써야 한다.
재귀함수는 알고리즘 문제 풀이나 DFS 탐색, 트리 순회 등에 거의 필수이므로 반드시 숙지하자! 처음에는 조금 어려울 수 있으나 익숙해지면 재귀함수가 굉장히 쉽고 편해질 것이다. 또한, 함수형 언어들은 대체로 재귀함수를 많이 쓰는 경향이 있어 재귀함수는 꽤나 중요하다.
보통 학교에서 배울 때는 팩토리얼을 예시로 사용하는데 여기서는 피보나치 함수를 예시로 설명하도록 한다. 필자의 경험 상 피보나치가 이해하기 더 쉽다.
먼저 피보나치의 점화식을 살펴보자.
f(n) = f(n -1) + f(n - 2),
f(1) = 1, f(0) = 0
이므로 f를 함수라 생각하고 작성해보자.
C언어를 기준으로 작성해보면
int f(int n)
{
// 기저 처리 (f(1) = 1, f(0) = 0)
if(n <= 1)
{
return n;
}
return f(n - 1) + f(n - 2);
}
뭔가 코드가 굉장히 심플하고 직관적이지 않은가?! 필자는 재귀함수를 좋아하는 사람이라 흥분을 느낀다...
반복문을 이용한 피보나치 보다는 코드를 이해하기 쉽고 직관적이다.[1]
하지만 문제가 하나 있는데 이렇게 피보나치를 구현하면 시간복잡도가 O(2^n)으로 되어 너무 비효율적이다. 시험삼아 n에 30정도를 넣고 돌려보자. 많이 느릴 것이다. 이를 해결하려면 다이나믹 프로그래밍 참고 바람[2]. 그리고 얘기가 나와서 하는 말인데 다이나믹 프로그래밍 문제를 재귀로 풀게 되면 이해하기 쉽고 직관적으로 짤 수 있다.이정도면 재귀 찬양 수준인데...
[1] 개인 차가 있을 수 있음
[2] 메모이제이션을 사용하면 된다.