함수가 함수 내부에서 자기 자신을 호출 하는 것. 자기호출이라고도 한다.
int Fibonacci (int N)
{
if (N == 1 || N == 2)
return 1;
else
return Fibonacci(N-1) + Fibonacci(N-2);
}
C#
복사
재귀는 초기항과 수열을 이루는 규칙을 통해 수열을 간결하게 표현할 수 있는 점화식의 개념을 컴퓨터에서 구현한 것과 같다.
위 함수가 구현하는 피보나치 수열의 점화식은 아래와 같다.
•
•
(n은 양의 정수)
◦
위 코드와 정확히 같게 표현하면 (n은 3이상의 양의 정수)가 된다.
재귀는 긴 수열을 아주 간결하게 표현할 수 있다는데서 무척 아름답고, 재귀로 함수를 구성하면 마치 퍼즐을 푼 것 같은 즐거움도 느껴지만, 코드를 한 눈에 이해하기 어렵고, 현실 세계에 존재하는 컴퓨터의 메모리의 물리적 한계상 자칫하면 stackoverflow가 발생할 수 있으며, 중복 계산 때문에 성능이 떨어지는 –물론 이를 위한 별도의 해법이 존재한다– 등의 문제가 있으므로 실제 코드작업에서 많이 사용되지는 않는다. –일반적인 loop문을 이용한 해법이 이해도 쉽고 성능에도 유리하다.
하지만 재귀를 이해하는 것은 자신을 더 작은 문제로 쪼개고 그것의 옳음을 증명해 자신의 옳음을 증명하는 수학적 귀납법을 이해하는 것이기 때문에 논리적인 사고력 훈련에 도움이 되리라 생각한다. –재귀가 이루는 수학적 귀납법은 복잡함의 세계에서 자기유사성의 원리와도 맞닿아 있다.
추가) Tree나 Graph 등의 문제는 for문을 중첩하는 것보다 재귀함수를 이용하는 것이 더 간단하다. 따라서 재귀함수에 대한 사용은 익혀 두는 것이 필요
