재귀함수 Recursion

정의 단계에서 자신을 다시 호출하는 함수

큰 문제를 작은문제로 나눠서 문제를 풀 때 사용

전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수

 

주의 사항

반드시 기저사항(종료조건)을 써야한다

사이클이 있다면 쓰면 안된다. (Rec(a)가 Rec(b)을 호출한 뒤 Rec(b)가 다시 Rec(a)를 호출하는 것

 

e.g. 팩토리얼 그 이전의 항을 모두 곱하는 것, 파보나치 

1. 팩토리얼 (Factorial)

팩토리얼은 양의 정수 n에 대해 1부터 n까지의 모든 수를 곱한 값을 의미합니다. 수학적으로는 n!로 표기하며, n!은 다음과 같이 정의됩니다.

• 정의:
  • n! = n *(n-1) (n-2) * ……. 1
  • \( 0! = 1 \) (0 팩토리얼은 예외적으로 1로 정의됨)
• 예시:
  • 3! = 3 * 2 * 1 = 6
  • 5! = 5 * 4 * 3 * 2 * 1 = 120
• 팩토리얼의 재귀적 정의:
  • n! = n*(n-1)!
  • 팩토리얼은 n이 1에 도달할 때까지 재귀적으로 계산할 수 있습니다

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1; // 기저조건!!!!!! 5,4,3,2,1에 도달하면 바꿔나오도록
    return n * factorial(n - 1); // 재귀 호출
}

int main() {
    int n = 5;
    cout << n << "! = " << factorial(n) << endl; // 출력: 5! = 120
    return 0;
}

 

2. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 각 항이 이전 두 항의 합으로 정의되는 수열입니다. 첫 번째 항과 두 번째 항은 각각 0과 1로 시작하며, 이후 항들은 앞의 두 항을 더한 값이 됩니다.

• 정의:
  • F(0) = 0
  • F(1) = 1
  예시:
  • \( F(0) = 0 \)
  • \( F(1) = 1 \)
  • \( F(2) = F(1) + F(0) = 1 \)
  • \( F(3) = F(2) + F(1) = 2 \)
  • \( F(4) = F(3) + F(2) = 3 \)
  • 따라서 초기 항들은 0, 1, 1, 2, 3, 5, 8, 13, ...
• 피보나치 수열의 재귀적 정의:
  • 피보나치 수열도 재귀적으로 정의할 수 있으며, 특정 항을 구하려면 이전 두 항을 계산해야 합니다.2. 피보나치 수열 (Fibonacci Sequence)
    • 정의:
      • F(0) = 0
      • F(1) = 1
    • 예시:
      • \( F(0) = 0 \)
      • \( F(1) = 1 \)
      • \( F(2) = F(1) + F(0) = 1 \)
      • \( F(3) = F(2) + F(1) = 2 \)
      • \( F(4) = F(3) + F(2) = 3 \)
      • 따라서 초기 항들은 0, 1, 1, 2, 3, 5, 8, 13, ...
    • 피보나치 수열의 재귀적 정의:
      • 피보나치 수열도 재귀적으로 정의할 수 있으며, 특정 항을 구하려면 이전 두 항을 계산해야 합니다.
  • 피보나치 수열은 각 항이 이전 두 항의 합으로 정의되는 수열입니다. 첫 번째 항과 두 번째 항은 각각 0과 1로 시작하며, 이후 항들은 앞의 두 항을 더한 값이 됩니다.

피보나치 구현 예제 (C++)

 

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n; // F(0) = 0, F(1) = 1 종료조건!
    return fibonacci(n - 1) + fibonacci(n - 2); 
}

int main() {
    int n = 5;
    cout << "F(" << n << ") = " << fibonacci(n) << endl; // 출력: F(5) = 5
    return 0;
}