프로그래밍 언어/C#

C# 재귀 호출 마스터하기, 팩토리얼과 피보나치 수열 예제로 배우는 프로그래밍 - C#8

eco7T 2024. 9. 25. 10:03
반응형

이번에는 C# 프로그래밍 언어에서 재귀 호출의 개념과 활용 방법에 대해 정리해 보겠습니다. 특히, 팩토리얼과 피보나치수열의 예시를 통해 재귀 호출을 이해하고, 기본 단계와 재귀 단계를 명확히 설명하여 독자가 재귀 호출을 효과적으로 사용할 수 있도록 설명해 보겠습니다.

C# 재귀 호출
C# 재귀 호출

 

C# 프로그래밍 언어의 재귀 호출

  재귀 호출(Recursion)이란?

재귀 호출은 함수(또는 메서드)가 자기 자신을 호출하는 프로그래밍 기술을 말합니다. 일반적으로 반복적인 작업을 수행할 때 많이 사용되며, 이러한 반복 작업을 처리할 때 반복문(예: `for`나 `while`) 대신 재귀 호출을 사용할 수 있습니다.

 

재귀 호출은 크게 두 가지 부분으로 구성됩니다.

  • 기본 단계(Base Case): 재귀 호출이 멈추는 조건을 의미합니다. 이 조건이 없다면 함수는 무한히 자기 자신을 호출하게 되어 프로그램이 멈추지 않고 계속 실행됩니다.
  • 재귀 단계(Recursive Case): 함수가 자기 자신을 호출하는 단계입니다. 이 단계에서 반복 작업을 수행하게 됩니다.

재귀 호출을 이해하기 위해 아래와 같이 간단한 예시를 하나씩 살펴보겠습니다.

 

  팩토리얼(Factorial) 계산 예시

팩토리얼은 수학에서 사용하는 개념으로, 양의 정수 `n`에 대해 `n!`은 `1`부터 `n`까지의 모든 정수를 곱한 값을 의미합니다. 예를 들어 `5!`은 `5 * 4 * 3 * 2 * 1 = 120`입니다.

 

팩토리얼 계산의 일반적인 표현

  • 수학적 표현
n! = n × (n - 1) × (n - 2) × ... × 1
  • 재귀적으로 표현
n! = n × (n - 1)!

특히 `0! = 1`로 정의되며, 이 값은 재귀 호출의 기본 단계(Base Case)가 됩니다.

 

반응형

 

팩토리얼 재귀 호출 구현 예제

이제 C#에서 재귀 호출을 이용한 팩토리얼 계산을 구현해보겠습니다.

using System; class FactorialExample { // 재귀 호출을 사용하여 팩토리얼을 계산하는 메서드 static int Factorial(int n) { // 기본 단계: n이 0이면 1을 반환 if (n == 0) { return 1; } // 재귀 단계: n × (n - 1)의 팩토리얼 else { return n * Factorial(n - 1); } } static void Main(string[] args) { Console.WriteLine("팩토리얼을 계산할 숫자를 입력하세요: "); int number = Convert.ToInt32(Console.ReadLine()); int result = Factorial(number); Console.WriteLine($"{number}! = {result}"); } }

위 코드를 요약하면 다음과 같습니다.

  1. `Factorial(int n)` 함수는 입력값 `n`이 `0`일 때 1을 반환하는 기본 단계(Base Case)를 가집니다.
  2. 그렇지 않으면 `n * Factorial(n - 1)`을 계산하는 재귀 단계(Recursive Case)를 수행합니다.
  3. `Main` 메서드에서 사용자가 입력한 숫자의 팩토리얼을 계산하고 결과를 출력합니다.

예제 실행 결과

팩토리얼을 계산할 숫자를 입력하세요: 5 5! = 120

 

 

  피보나치수열 예시

피보나치수열은 다음과 같이 정의되는 수열입니다.

  • 첫 번째 항: 0
  • 두 번째 항: 1
  • 세 번째 항부터는 이전 두 항의 합

즉, `0, 1, 1, 2, 3, 5, 8, 13,...` 이런 식으로 이어집니다.

 

피보나치수열의 재귀적 표현

  • 수열의 정의
F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2)

 

피보나치 수열 재귀 호출 구현 예제

다음은 재귀 호출을 사용하여 피보나치수열을 계산하는 C# 프로그램입니다.

using System; class FibonacciExample { // 재귀 호출을 사용하여 피보나치 수를 계산하는 메서드 static int Fibonacci(int n) { // 기본 단계 if (n == 0) { return 0; } else if (n == 1) { return 1; } // 재귀 단계 else { return Fibonacci(n - 1) + Fibonacci(n - 2); } } static void Main(string[] args) { Console.WriteLine("피보나치 수열의 몇 번째 항을 원하시나요?"); int number = Convert.ToInt32(Console.ReadLine()); int result = Fibonacci(number); Console.WriteLine($"피보나치 수열의 {number}번째 항은 {result}입니다."); } }

위 코드는,

  1. `Fibonacci(int n)` 함수는 `n`이 `0` 또는 `1`일 때 그 값을 그대로 반환합니다. 이게 기본 단계(Base Case)입니다.
  2. 그 외의 경우, `Fibonacci(n - 1) + Fibonacci(n - 2)`를 수행하며 이는 재귀 단계(Recursive Case)입니다.
  3. `Main` 메서드에서 사용자가 원하는 피보나치수열의 항을 계산하고 결과를 출력합니다.

예제 실행 결과

피보나치 수열의 몇 번째 항을 원하시나요? 7 피보나치 수열의 7번째 항은 13입니다.

 

 

 

  재귀 호출의 장점과 단점

  • 장점
    • 복잡한 문제를 재귀적으로 표현하면 코드가 간결하고 이해하기 쉬워집니다.
    • 알고리즘이 수학적 수식과 유사하게 표현되므로 특정 문제에 대한 논리적 표현이 명확해집니다.
  • 단점
    • 많은 재귀 호출이 발생하면 함수 호출이 중첩되어 메모리 사용량이 많아집니다. 이로 인해 스택 오버플로우(Stack Overflow)라는 오류가 발생할 수 있습니다.
    • 반복문으로 해결할 수 있는 문제를 재귀 호출로 처리하면 성능이 저하될 수 있습니다.

 

  재귀 호출의 효율적 사용을 위한 팁

기본 단계(Base Case): 반드시 있어야 하며, 재귀 호출이 무한히 반복되지 않도록 설계해야 합니다.

메모이제이션(Memoization): 같은 계산을 반복하지 않도록 이전에 계산한 값을 저장하여 재사용하는 방법입니다. 이는 재귀 호출의 효율성을 높여줍니다.

반복문 사용 고려: 성능에 민감한 경우, 재귀 호출보다는 반복문을 사용하는 것이 좋습니다.

반응형