프로그래밍/ 재귀함수

함수가 함수 내부에서 자기 자신을 호출 하는 것. 자기호출이라고도 한다.

int Fibonacci (int N)
{
    if (N == 1 || N == 2)
        return 1;
    else
        return Fibonacci(N-1) + Fibonacci(N-2);
}

재귀는 초기항과 수열을 이루는 규칙을 통해 수열을 간결하게 표현할 수 있는 점화식의 개념을 컴퓨터에서 구현한 것과 같다.

위 함수가 구현하는 피보나치 수열의 점화식은 아래와 같다.

  • a1 = 1, a2 = 1
  • an+2 = an+1 + an (n은 양의 정수)
    • 위 코드와 정확히 같게 표현하면 an = an-1 + an-2 (n은 3이상의 양의 정수)가 된다.

재귀는 긴 수열을 아주 간결하게 표현할 수 있다는데서 무척 아름답고, 재귀로 함수를 구성하면 마치 퍼즐을 푼 것 같은 즐거움도 느껴지만, 코드를 한 눈에 이해하기 어렵고, 현실 세계에 존재하는 컴퓨터의 메모리의 물리적 한계상 자칫하면 stackoverflow가 발생할 수 있으며, 중복 계산 때문에 성능이 떨어지는 –물론 이를 위한 별도의 해법이 존재한다– 등의 문제가 있으므로 실제 코드작업에서 많이 사용되지는 않는다. –일반적인 loop문을 이용한 해법이 이해도 쉽고 성능에도 유리하다.

하지만 재귀를 이해하는 것은 자신을 더 작은 문제로 쪼개고 그것의 옳음을 증명해 자신의 옳음을 증명하는 수학적 귀납법을 이해하는 것이기 때문에 논리적인 사고력 훈련에 도움이 되리라 생각한다. –재귀가 이루는 수학적 귀납법은 복잡함의 세계에서 자기유사성의 원리와도 맞닿아 있다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.