C#에서 재귀(Recursion)로 피보나치 수열의 n번째 값 구하는 방법

C# 재귀를 활용한 피보나치 수열 구현 개요

피보나치 수열은 각 항이 바로 앞의 두 항의 합으로 정의되는 수열입니다(0, 1, 1, 2, 3, 5, 8, 13...). 이러한 자기 참조적 특성 덕분에 재귀(recursion), 즉 메서드가 자기 자신을 다시 호출하는 방식으로 매우 자연스럽게 구현할 수 있습니다.

먼저 n번째 피보나치 값을 반환할 메서드를 하나 정의합니다.

public int displayFibonacci(int n)

그다음 이 메서드를 아래와 같이 호출하면, 내부에서 스스로를 반복적으로 호출하며 n번째 값을 계산합니다.

displayFibonacci(val)

재귀 메서드의 동작 원리

재귀 구현의 핵심은 반복을 멈추게 하는 기저 조건(base case)을 명확히 설정하는 것입니다. 이 예제에서는 두 가지 기저 조건을 사용합니다.

• n이 0일 때: 0을 반환합니다.
• n이 1일 때: 1을 반환합니다.
• 그 외의 경우: 바로 앞 두 항의 합인 displayFibonacci(n-1) + displayFibonacci(n-2)를 반환하며 재귀 호출이 이어집니다.

public int displayFibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    } else {
        return displayFibonacci(n - 1) + displayFibonacci(n - 2);
    }
}

전체 예제 코드

지금까지의 내용을 하나의 완전한 C# 프로그램으로 정리하면 다음과 같습니다.

using System;

public class Demo {
    public static void Main(string[] args) {
        Demo d = new Demo();
        int val = 7;
        int res = d.displayFibonacci(val);
        Console.WriteLine("{0}번째 피보나치 수 = {1}", val, res);
    }

    public int displayFibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        } else {
            return displayFibonacci(n - 1) + displayFibonacci(n - 2);
        }
    }
}

실행 결과

7번째 피보나치 수 = 13

위 코드에서는 val = 7로 설정했기 때문에, 피보나치 수열의 7번째 값인 13이 출력됩니다.

성능 관련 참고 사항

단순 재귀 방식은 직관적이지만 같은 값을 중복 계산하게 되어 시간 복잡도가 O(2ⁿ)로 매우 비효율적입니다. 따라서 n이 커질수록 실행 시간이 급격히 늘어납니다. 실무에서는 다음과 같은 대안을 고려하는 것이 좋습니다.

• 메모이제이션(Memoization): 이미 계산한 값을 배열이나 딕셔너리에 저장해 중복 연산을 제거합니다.
• 반복문 방식: for 루프를 사용하면 O(n)의 시간 복잡도로 효율적으로 계산할 수 있습니다.