C++의 재귀 피보나치
이 작은 튜토리얼은 C++의 재귀 함수를 사용하여 피보나치 수열을 구현하는 방법을 설명합니다. 이를 위해 먼저 재귀 함수에 대한 간략한 소개를 하겠습니다.
C++의 재귀 함수
재귀 함수는 자체 본문 내에서 자신을 호출하며 이 개념을 사용하여 재귀라고 합니다. 이 개념은 여러 면에서 유용하며 일부 함수는 재귀만 사용하여 구현할 수 있습니다.
위의 그림은 재귀의 개념을 보여줍니다. main 함수에서 recurse 함수가 호출되고 해당 함수에서 recurse가 다시 호출됩니다.
이렇게 하면 재귀 호출이 생성되고 프로그램은 일부 조건이 충족될 때까지 이 함수에서 반복을 계속합니다. 일반적으로 if...else 구조는 재귀 함수에서 사용되며 한 경로는 재귀 호출을 만들고 다른 경로는 함수에서 종료합니다. 그렇지 않으면 무한 재귀가 발생합니다.
재귀는 함수 내에서 함수를 여러 번 반복 호출합니다. 재귀 조건은 기본 사례가 충족될 때까지 함수를 다시 호출합니다.
기본 케이스는 함수 내부에 포함되며 기본 케이스의 조건이 충족될 때마다 실행을 종료합니다.
암호:
void recursiveFun(int x) {
if (x == 0) return;
x = x - 1;
recursiveFun(x);
}
위의 함수는 일단 x 인수로 호출되면 가 나올 때까지 감소된 x 값(즉, [x-1, x-2,..., x-(x-1)])으로 자신을 재귀적으로 호출합니다. x는 0이 됩니다. 값이 0인 x가 발생하면 프로그램은 새 재귀 호출 생성을 중지하고 값(있는 경우)을 아래에서 위로 반환하기 시작합니다.
재귀는 거의 모든 문제를 해결하는 데 사용될 수 있지만 정말 유익한 선택적인 경우가 있습니다. 일반적으로 어려운 문제와 계층적 패턴을 따르는 문제를 처리하는 데 사용됩니다. 더 작은 하위 문제를 해결하여 주요 문제를 해결합니다.
재귀의 유형
직접 재귀와 간접 재귀는 재귀의 두 가지 유형입니다.
직접 재귀
재귀 함수는 직접 재귀를 통해 자체 본문에서 직접 호출합니다.
void recursion() { ....recursion(); }
코드에서 함수가 자체 본문 또는 괄호에서 자신을 호출하는 것을 볼 수 있습니다.
간접 재귀
간접 재귀에서 함수는 다른 함수 본문에서 간접적으로 호출됩니다.
void func1() { ... func2(); }
void func2() { ... func1(); }
피보나치 수열
피보나치 수열은 각각의 연속된 숫자가 이전 두 숫자의 합인 정수 집합입니다. 처음 두 숫자 0과 1, 세 번째 숫자는 처음 두 숫자를 더하여 계산됩니다.
피보나치 수열을 계산하는 공식은 다음과 같습니다.
<사업부>
$$
x_n = x_{n-1} + x_{n-2}
$$
예를 들어 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
세 번째 요소 1이 0+1의 합임을 알 수 있습니다. 마찬가지로 네 번째 숫자 2는 이전 숫자의 합입니다(1+1=2).
따라서 우리는 시리즈의 다음 요소가 21+34 = 55가 될 것이라고 예측할 수 있습니다.
C++의 피보나치 수열
피보나치 수열을 구현하기 위해 숫자를 입력하고 해당 수량의 피보나치 수열을 인쇄할 수 있는 재귀 함수를 구현할 수 있습니다. 예를 들어 사용자가 8을 입력하면 시리즈의 8개 숫자가 인쇄됩니다.
암호:
#include <iostream>
using namespace std;
int fibonacci(int num) {
if (num <= 1) return num;
return fibonacci(num - 1) + fibonacci(num - 2);
}
int main() {
int num;
cout << "Enter a number: ";
cin >> num;
for (int a = 0; a < num; a++) {
cout << fibonacci(a) << " ";
}
return 0;
}
기본 기능에서 사용자에게 숫자를 입력하라는 메시지가 표시됩니다. 그런 다음 0에서 해당 입력 숫자 num까지 루프를 반복하고 반복자 변수 a를 Fibonacci 함수에 전달했습니다.
이 루프는 사용자가 입력한 숫자의 num번을 반복합니다. Fibonacci 함수에는 숫자가 1보다 작은지 확인하고 해당 숫자를 반환하는 if 조건이 있습니다.
그렇지 않으면 num-1 및 num-2에 대해 fibonacci 함수를 호출합니다. 시리즈의 모든 다음 숫자는 이전 두 숫자, 즉 n-1 및 의 합계를 만들어 계산되기 때문입니다. n-2.
출력:
사용자가 숫자 9를 입력했기 때문에 피보나치 수열에 9개의 값이 포함되어 인쇄되었습니다.
