recursion c
클래식 예제를 통해 C ++의 재귀에 대한 모든 것을 살펴보십시오.
이전 튜토리얼에서 C ++의 함수에 대해 더 많이 배웠습니다.
코드를 하위 단위로 나누고 코드를 더 간단하고 읽기 쉽게 만드는 함수를 사용하는 것 외에도 함수는 실시간 문제 해결, 수학적 및 통계 계산을 포함한 다양한 다른 응용 프로그램에서 유용합니다.
C ++로 더 복잡한 응용 프로그램을 개발함에 따라 많은 요구 사항이 발생하므로 C ++의 몇 가지 특수 개념을 사용해야합니다. 재귀는 그러한 개념 중 하나입니다.
=> 전체 C ++ 자습서 목록을 보려면 여기를 방문하십시오.
최고의 mp3 음악 다운로더는 무엇입니까
이 튜토리얼에서는 재귀를 구현하는 몇 가지 고전적인 C ++ 예제와 함께 재귀가 사용되는 위치와 이유에 대해 자세히 알아 봅니다.
학습 내용 :
- 재귀 란 무엇입니까?
- 재귀 기준 조건
- 재귀 호출을위한 메모리 할당
- 재귀의 스택 오버플로
- 직접 대 간접 재귀
- 꼬리와 꼬리가없는 재귀
- 반복 프로그래밍에 대한 재귀의 장단점
- 재귀의 예
- 결론
- 추천 도서
재귀 란 무엇입니까?
재귀는 함수가 자신을 호출하는 프로세스입니다. 재귀를 구현하거나 자신을 호출하는 함수를 재귀 함수라고합니다. 재귀에서 재귀 함수는 계속해서 자신을 호출하고 종료 조건이 충족 될 때까지 계속 진행합니다.
아래 이미지는 재귀의 작동 방식을 보여줍니다.
위의 다이어그램에서 볼 수 있듯이 main 함수는 funct () 함수를 호출합니다. 함수 funct ()는 정의 내에서 자신을 호출합니다. 이것이 재귀가 작동하는 방식입니다. 자신을 호출하는이 함수 프로세스는 종료 조건을 제공 할 때까지 계속됩니다.
일반적으로 재귀를 구현하는 동안 코드 분기를 제공하여 재귀를 트리거하는 조건과 정상적인 실행을 수행하는 조건을 제공합니다.
재귀 기준 조건
재귀를 수행하면 기본 케이스 또는 종료 케이스에 대한 솔루션이 제공되고 작은 문제에 대한 솔루션을 기반으로 더 큰 문제에 대한 솔루션이 구축됩니다.
팩토리얼 표기법 인 재귀의 전형적인 예를 살펴 보겠습니다..
수학적으로 n의 계승은 다음과 같습니다.
엔! = nxn-1x… .x0!
그게 0! = 1;
따라서 n = 3에 대한 계승은 3이됩니다! = 3 × 2!
삼! = 3x2x1!
삼! = 3x2x2x0!
삼! = 3x2x1x1 = 6
따라서 프로그래밍 방식으로이 계산을 다음과 같이 표현할 수 있습니다.
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }따라서 위에 표시된 것처럼 위의 계승 계산을 재귀 함수 호출로 표현했습니다. 숫자 n이 1보다 작거나 같으면 재귀 호출 대신 1을 반환합니다. 이것은 재귀를 중지 할 수있는 팩토리얼의 기본 조건 / 케이스라고합니다.
따라서 기본 조건은 기본적으로 재귀 함수가 자신을 호출해야하는 횟수를 결정합니다. 즉, 기본 클래스에 도달 할 때까지 더 작은 숫자로 표현함으로써 더 큰 숫자의 계승을 매우 잘 계산할 수 있습니다.
다음은 숫자의 계승을 계산하는 완벽한 예입니다.
#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout< 산출:
계승을 계산할 숫자 입력 :
10! = 3628800
위의 예에서는 재귀를 구현합니다. 표준 입력에서 계승을 찾을 수있는 숫자를 계승 함수에 전달합니다.
계승 함수에서 기본 조건을 (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.
재귀 호출을위한 메모리 할당
함수 호출이 이루어지면 호출 함수의 상태가 스택에 저장되고 함수 호출이 완료되면 해당 상태가 복원되어 프로그램이 계속 실행될 수 있음을 알고 있습니다.
재귀 함수 호출이 이루어지면 호출 된 함수의 상태 또는 메모리가 호출 함수의 상태 위에 할당되고 모든 재귀 함수 호출에 대해 다른 로컬 변수 복사본이 만들어집니다.
기본 조건에 도달하면 함수가 호출 함수로 돌아가고 메모리 할당이 해제되고 프로세스가 계속됩니다.
재귀의 스택 오버플로
재귀가 무제한 시간 동안 계속되면 스택 오버플로가 발생할 수 있습니다.
재귀는 언제 이렇게 계속 될 수 있습니까? 한 가지 상황은 기본 조건을 지정하지 않은 경우입니다. 또 다른 상황은 프로그램을 실행하는 동안 기본 조건에 도달하지 못한 경우입니다.
예를 들어,위의 팩토리얼 프로그램을 수정하고 기본 조건을 변경합니다.
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }위의 코드에서 기본 조건을 (n == 1000)으로 변경했습니다. 이제 n = 10을 주면 기본 조건이 절대 도달하지 않는다는 결론을 내릴 수 있습니다. 이런 식으로 어느 시점에서 스택의 메모리가 고갈되어 스택 오버플로가 발생합니다.
따라서 재귀 프로그램을 설계하는 동안 우리가 제공하는 기본 조건에주의해야합니다.
직접 대 간접 재귀
지금까지 재귀에서 자신을 호출하는 함수를 보았습니다. 이것은 직접 재귀입니다.
또 다른 유형의 재귀, 즉 간접 재귀가 있습니다. 여기서 함수는 다른 함수를 호출하고이 함수는 호출 함수를 호출합니다. f1과 f2가 두 가지 기능인 경우. 그런 다음 f1은 f2를 호출하고 f2는 차례로 f1을 호출합니다. 이것은 간접 재귀입니다.
엘 직접 재귀를 보여주기 위해 팩토리얼 프로그램을 수정합니다.
#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout< 산출:
계승을 계산할 숫자 입력 : 5
5! = 120
배열에 요소를 추가하는 방법
위의 예에서는 간접 재귀를 보여주었습니다. 주 함수는 factorial_a를 호출합니다. Factorial_a는 factorial_b를 호출합니다. 차례로 factorial_b는 factorial_a를 호출합니다. 프로그램의 출력은 영향을받지 않습니다.
꼬리와 꼬리가없는 재귀
꼬리 재귀 함수는 함수에서 마지막 호출이 실행되는 재귀 함수입니다.
예를 들어, 다음 기능을 고려하십시오.
void display(int n){ if(n<=1) return; cout<<” ”<위의 예에서 디스플레이는 마지막 함수 호출이되는 꼬리가있는 재귀 함수입니다.
꼬리가없는 함수는 컴파일러에서 최적화 할 수 있으므로 꼬리가없는 재귀 함수보다 더 나은 것으로 간주됩니다. 그 이유는 꼬리가있는 재귀 호출이 함수의 마지막 문이므로이 호출 후에 실행할 코드가 없기 때문입니다.
결과적으로 함수에 대한 현재 스택 프레임을 저장할 필요가 없습니다.
반복 프로그래밍에 대한 재귀의 장단점
재귀 프로그램은 간결하고 깨끗한 코드를 제공합니다. 재귀 프로그램은 프로그램을 작성하는 간단한 방법입니다. 팩토리얼, 피보나치 수열, 하노이의 탑, 트리 순회 등과 같은 몇 가지 내재 된 문제가 있으며 해결을 위해 재귀가 필요합니다.
즉, 재귀를 통해 효율적으로 해결됩니다. 스택 또는 기타 데이터 구조를 사용하는 반복 프로그래밍으로도 해결할 수 있지만 구현하기가 더 복잡해질 가능성이 있습니다.
반복 프로그래밍과 반복 프로그래밍의 문제 해결 능력은 동일합니다. 그러나 재귀 프로그램은 기본 케이스가 일치 할 때까지 모든 함수 호출을 스택에 저장해야하므로 더 많은 메모리 공간을 차지합니다.
재귀 함수는 너무 많은 함수 호출과 반환 값으로 인해 시간 오버 헤드가 있습니다.
재귀의 예
다음으로 재귀 프로그래밍의 몇 가지 예를 구현합니다.
피보나치 시리즈
피보나치 수열은 다음과 같이 주어진 수열입니다.
0 1 1 2 3 5 8 13 ……
위와 같이 피보나치 수열의 처음 두 수는 0과 1입니다. 수열의 다음 수는 이전 두 수의 합입니다.
재귀를 사용하여이 시리즈를 구현해 보겠습니다.
#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '< 산출:
피보나치 수열의 원소 개수 입력 : 10
10 개의 숫자에 대한 피보나치 수열 : 012 34 5 8 13 21 34
이 예에서는 재귀 호출을 사용하여 피보나치 시퀀스를 생성했습니다. 상수 인 처음 두 숫자가 직접 인쇄되고 시퀀스의 다음 숫자에 대해 재귀 함수를 사용합니다.
회문
회문 번호는 역방향으로 읽을 때 왼쪽에서 오른쪽으로 읽은 것과 동일한 숫자입니다.
예를 들어, 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 읽는 동안 숫자 121은 동일하게 읽습니다. 즉, 121입니다. 따라서 121은 회문입니다.
숫자 291은 오른쪽에서 왼쪽으로 즉 역순으로 읽을 때 192와 같이 읽습니다. 따라서 291은 회문이 아닙니다.
#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '< 산출:
회문 확인 번호 입력 : 6556
6556 번은 회문입니다
동일한 스크린 샷은 아래와 같습니다.
위의 프로그램에서 우리는 표준 입력에서 입력 번호를 읽습니다. 그런 다음이 숫자를 재귀 함수에 전달하여 숫자의 자릿수를 뒤집습니다. 반전 된 숫자와 입력 된 숫자가 같으면 그 숫자는 회문입니다.
결론
이것으로 재귀를 마쳤습니다. 이 튜토리얼에서는 다양한 예제와 함께 재귀 프로그래밍, 재귀 함수, 장점 / 단점을 연구했습니다.
이러한 예와 별도로 재귀는 순회 (inorder / preorder / postorder), 하노이의 탑, BFS 순회 등과 같은 일부 표준 문제를 해결하는데도 사용됩니다.
=> 처음부터 C ++를 배우려면 여기를 방문하십시오.
추천 도서
