C에서 재귀를 사용한 열거의 예. 재귀. 훈련 작업. 산술 표현식 구문 분석

바르그 말한다:

안녕하세요. 이 함수가 어떻게 계산을 수행하는지 정말 이해할 수 없습니다.

{
(n==1)인 경우 1을 반환합니다. //새 값이 1이면 이전 값이 아닌 1을 추가합니다. 왜냐하면 이전 것은 0입니다. 1+0의 합은 무한대입니다.
그렇지 않으면 합계(n-1)+n을 반환합니다. //그러나 n>1이면 n까지의 모든 요소의 합과 동일한 이전 값을 추가합니다.
}

내 이해에 따르면 n에는 5가 있고 조건이 일치하지 않으면 만족됩니다. 이 코드 sum(n-1)+n 즉, 괄호 안에 빼서 얻은 것을 5에 더하는데, (5 - 1)+5는 무엇이고 그렇다면 이를 멈추는 것은 무엇입니까? 산술 연산:?: :?: :?: 이전 값은 무엇이며, 어디서 왔으며, 다음과 같은 값은 무엇입니까:?: :?: :?:

예, 거의 모든 것이 제가 이해한 대로입니다(마지막 단락에서 재귀를 보여주었습니다)). 그러나 질문은 남아 있습니다. 합계는 어떻게 얻은 다음 화면에 표시됩니까?
저는 Dev C++로 작업하고 있습니다. 이 예금액 ==15로 표시되는데, 예시에 적힌 대로 계산하면 금액이 다른 것으로 나타납니다.
위에서 썼으니 (5-1)+5=4+5=9를 취해보자

:
1+2+3+4+5 = 15. 예제에서는 올바르게 출력됩니다.

(5) //함수에 5를 주었고 1과 같은지 확인했습니다. 같지 않음, 함수를 다시 호출하고 5-1을 전달합니다.
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))

2-1 == 1, 함수 호출이 완료되었습니다.
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
이것이 결과입니다.
여기서 함수의 결과는 처음 두 숫자의 차이이고 n은 오른쪽의 나머지입니다.
__________________________________
단지 함수를 정확하게 이해하고 변수로 이해하지 않고 계산된 값으로 받아들이면 됩니다. 변수와 비슷하지만 계산된 상수에 더 가깝고, 상수는 아니지만 이렇게 인식하는 것이 더 편리할 뿐입니다.

예, 예, 예, 이해했다고 쓸 시간이 없었습니다. 모든 것이 정확하고 문제가 즉시 해결되지 않았습니다. 좋은 사이트 감사합니다))

그리고 반환된 숫자를 return 1에서 2로 변경하면 8번째 줄에서는 여전히 완전히 논리적이지 않으며 금액은 16으로 변경됩니다. 이 조건은 9번째 줄과 어떤 관련이 있습니까?
이것으로도 모든 것이 명확합니다. 말하자면, 2를 반환하면 그 박탈을 합계에 추가하면 됩니다.

:
여분의 별이 아니라 이 두 개입니다. 그리고 -3을 쓰면 한 번 더할 때 세 개를 빼게 됩니다.
전체 논리는 모든 재귀 함수에는 반환 지점이 필요하다는 것입니다.
아홉 번째 줄과의 연관성은 다음과 같습니다. 합계 함수 main 내부에서 호출할 때 숫자가 전달되고 재귀 호출을 통해 이 숫자는 매번 1(n-1)씩 감소합니다. 이 n-1 결과는 1과 동일한지 확인하고 동일성이 true이면 전체 결과 금액은 해당 수익에 포함된 숫자와 합산됩니다. 그렇지 않으면 전체 합계가 이 새로운 n-1로 합산됩니다.

안녕하세요 하브라하브르!

이번 글에서는 재귀 문제와 그 해결 방법에 대해 알아보겠습니다.

재귀에 대해 간략하게

재귀는 과학 분야뿐만 아니라 다른 분야에서도 발생하는 매우 일반적인 현상입니다. 일상 생활. 예를 들어 Droste 효과, Sierpinski 삼각형 등이 있습니다. 재귀를 확인하는 한 가지 방법은 먼저 웹 카메라를 켠 후 자연스럽게 컴퓨터 모니터 화면을 가리키는 것입니다. 따라서 카메라는 컴퓨터 화면의 이미지를 기록하고 이 화면에 표시하며 이는 폐쇄 루프와 같습니다. 결과적으로 우리는 터널과 비슷한 것을 관찰하게 될 것입니다.

프로그래밍에서 재귀는 함수와 밀접하게 관련되어 있습니다. 보다 정확하게는 재귀 또는 재귀 함수와 같은 것이 프로그래밍의 함수 덕분입니다. 간단한 말로에서 재귀는 함수(메서드)의 일부를 자체적으로 정의하는 것입니다. 즉, 직접(본문에서) 또는 간접적으로(다른 함수를 통해) 자신을 호출하는 함수입니다.

재귀에 관해 많은 이야기가 있었습니다. 다음은 몇 가지 좋은 리소스입니다.

• 재귀 및 재귀 문제. 재귀 적용 분야

독자는 이론적으로 재귀에 익숙하고 그것이 무엇인지 알고 있다고 가정합니다. 이번 글에서는 재귀 문제에 대해 좀 더 자세히 살펴보겠습니다.

작업

재귀를 배울 때 재귀를 이해하는 가장 효과적인 방법은 문제를 해결하는 것입니다.

재귀 문제를 해결하는 방법은 무엇입니까?

우선, 재귀는 일종의 과잉이라는 점을 이해해야 합니다. 일반적으로 반복적으로 해결되는 모든 문제는 재귀적으로, 즉 재귀 함수를 사용하여 해결될 수 있습니다.

네트워크에서

재귀 형식으로 구현된 모든 알고리즘은 반복 형식으로 다시 작성할 수 있으며 그 반대의 경우도 마찬가지입니다. 이것이 필요한지, 얼마나 효과적일지는 여전히 의문입니다.

이를 정당화하기 위해 다음과 같은 주장이 제시될 수 있습니다.

우선, 재귀와 반복의 정의를 떠올려 보겠습니다. 재귀는 프로그램이 직접 호출하거나 다른 프로그램의 도움을 받아 데이터 처리를 구성하는 방법입니다. 반복은 재귀적인 프로그램 호출로 이어지지 않고 특정 작업이 여러 번 반복되는 데이터 처리를 구성하는 방법입니다.

그런 다음 상호 교환이 가능하지만 리소스와 속도 측면에서 비용이 항상 동일한 것은 아니라는 결론을 내릴 수 있습니다. 이를 정당화하기 위해 다음 예를 들 수 있습니다. 특정 알고리즘을 구성하기 위해 카운터의 현재 값에 따라 일련의 작업을 수행하는 루프가 있는 함수가 있습니다. 그것). 주기가 있다는 것은 신체가 일련의 동작, 즉 주기의 반복을 반복한다는 것을 의미합니다. 작업을 별도의 서브루틴으로 이동하고 카운터 값(있는 경우)을 전달할 수 있습니다. 서브루틴 실행이 완료되면 루프 실행 조건을 확인하고, true이면 서브루틴에 대한 새로운 호출을 진행하고, false이면 실행을 완료합니다. 왜냐하면 루프의 모든 내용을 서브루틴에 배치했습니다. 즉, 루프를 실행하기 위한 조건도 서브루틴에 배치되었으며 함수의 반환 값, 서브루틴에 대한 참조 또는 포인터로 전달된 매개변수를 통해 얻을 수 있습니다. , 전역 변수도 마찬가지입니다. 또한, 루프에서 주어진 서브루틴에 대한 호출은 일부 조건(해당 조건에 따라)에 따라 서브루틴 자체의 호출 또는 비호출(값을 반환하거나 단순히 작업 완료)로 쉽게 변환될 수 있음을 쉽게 보여줍니다. 이전에는 루프 상태였습니다). 이제 우리의 모습을 보면 추상 프로그램, 이는 서브루틴에 값을 전달하고 이를 사용하는 것과 대략 비슷하며, 서브루틴은 완료 시 변경됩니다. 주어진 알고리즘을 해결하기 위해 반복 루프를 서브루틴에 대한 재귀 호출로 대체했습니다.

반복적 접근 방식으로 재귀를 가져오는 작업은 대칭적입니다.

요약하면 다음과 같은 생각을 표현할 수 있습니다. 각 접근 방식에는 특정 작업에 대한 특정 요구 사항에 따라 결정되는 자체 작업 클래스가 있습니다.

이에 대해 자세히 알아볼 수 있습니다.

열거(주기)와 마찬가지로 재귀에도 중지 조건(기본 사례)이 있어야 합니다(그렇지 않으면 주기와 마찬가지로 재귀도 영원히 작동합니다 - 무한). 이 조건은 재귀가 진행되는 경우(recursion step)입니다. 각 단계에서 다음 호출이 기본 조건을 트리거하고 재귀가 중지될 때까지(또는 오히려 다음으로 돌아갈 때까지 재귀 함수가 호출됩니다.) 마지막 호출기능). 전체 솔루션은 기본 사례를 해결하는 것으로 귀결됩니다. 복잡한 문제를 해결하기 위해 재귀 함수가 호출되는 경우(기본 사례 아님) 문제를 더 간단한 문제로 줄이기 위해 여러 재귀 호출 또는 단계가 수행됩니다. 그리고 우리가 기본적인 해결책을 얻을 때까지 계속합니다.

따라서 재귀 함수는 다음과 같이 구성됩니다.

• 정지 조건 또는 기본 케이스
• 연속 조건 또는 재귀 단계는 문제를 더 간단한 문제로 줄이는 방법입니다.

계승을 찾는 예를 사용하여 이를 살펴보겠습니다.

Public class Solution ( public static int recursion(int n) ( // 종료 조건 // 기본 사례 // 재귀 반복을 언제 중지할까요? if (n == 1) ( return 1; ) // 재귀 단계 / 재귀 조건 return 재귀(n - 1) * n ) 공개; 정적 공백 main(String args) ( System.out.println(recursion(5)); // 재귀 함수 호출 ) )

여기서 기본 조건은 n=1일 때의 조건입니다. 우리는 1!=1임을 알고 1!을 계산하기 때문입니다. 우리는 아무것도 필요하지 않습니다. 2를 계산합니다! 우리는 1!을 사용할 수 있습니다. 2!=1!*2. 3을 계산합니다! 우리는 2!*3이 필요합니다... n을 계산하려면! (n-1)!*n이 필요합니다. 이것이 재귀 단계입니다. 즉, 숫자 n의 계승 값을 얻으려면 이전 숫자의 계승 값에 n을 곱하면 충분합니다.

태그: 태그 추가

안녕하세요 하브라하브르!

이번 글에서는 재귀 문제와 그 해결 방법에 대해 알아보겠습니다.

재귀에 대해 간략하게

재귀는 과학 분야뿐만 아니라 일상생활에서도 일어나는 꽤 흔한 현상이다. 예를 들어 Droste 효과, Sierpinski 삼각형 등이 있습니다. 재귀를 확인하는 한 가지 방법은 먼저 웹 카메라를 켠 후 자연스럽게 컴퓨터 모니터 화면을 가리키는 것입니다. 따라서 카메라는 컴퓨터 화면의 이미지를 기록하고 이 화면에 표시하며 이는 폐쇄 루프와 같습니다. 결과적으로 우리는 터널과 비슷한 것을 관찰하게 될 것입니다.

프로그래밍에서 재귀는 함수와 밀접하게 관련되어 있습니다. 보다 정확하게는 재귀 또는 재귀 함수와 같은 것이 프로그래밍의 함수 덕분입니다. 간단히 말해서 재귀는 함수(메서드)의 일부를 자체적으로 정의하는 것입니다. 즉, 직접적으로(본문에서) 또는 간접적으로(다른 함수를 통해) 자신을 호출하는 함수입니다.

재귀에 관해 많은 이야기가 있었습니다. 다음은 몇 가지 좋은 리소스입니다.

• 재귀 및 재귀 문제. 재귀 적용 분야

독자는 이론적으로 재귀에 익숙하고 그것이 무엇인지 알고 있다고 가정합니다. 이번 글에서는 재귀 문제에 대해 좀 더 자세히 살펴보겠습니다.

작업

재귀를 배울 때 재귀를 이해하는 가장 효과적인 방법은 문제를 해결하는 것입니다.

재귀 문제를 해결하는 방법은 무엇입니까?

우선, 재귀는 일종의 과잉이라는 점을 이해해야 합니다. 일반적으로 반복적으로 해결되는 모든 문제는 재귀적으로, 즉 재귀 함수를 사용하여 해결될 수 있습니다.

네트워크에서

재귀 형식으로 구현된 모든 알고리즘은 반복 형식으로 다시 작성할 수 있으며 그 반대의 경우도 마찬가지입니다. 이것이 필요한지, 얼마나 효과적일지는 여전히 의문입니다.

이를 정당화하기 위해 다음과 같은 주장이 제시될 수 있습니다.

우선, 재귀와 반복의 정의를 떠올려 보겠습니다. 재귀는 프로그램이 직접 호출하거나 다른 프로그램의 도움을 받아 데이터 처리를 구성하는 방법입니다. 반복은 재귀적인 프로그램 호출로 이어지지 않고 특정 작업이 여러 번 반복되는 데이터 처리를 구성하는 방법입니다.

그런 다음 상호 교환이 가능하지만 리소스와 속도 측면에서 비용이 항상 동일한 것은 아니라는 결론을 내릴 수 있습니다. 이를 정당화하기 위해 다음 예를 들 수 있습니다. 특정 알고리즘을 구성하기 위해 카운터의 현재 값에 따라 일련의 작업을 수행하는 루프가 있는 함수가 있습니다. 그것). 주기가 있다는 것은 신체가 일련의 동작, 즉 주기의 반복을 반복한다는 것을 의미합니다. 작업을 별도의 서브루틴으로 이동하고 카운터 값(있는 경우)을 전달할 수 있습니다. 서브루틴 실행이 완료되면 루프 실행 조건을 확인하고, true이면 서브루틴에 대한 새로운 호출을 진행하고, false이면 실행을 완료합니다. 왜냐하면 루프의 모든 내용을 서브루틴에 배치했습니다. 즉, 루프를 실행하기 위한 조건도 서브루틴에 배치되었으며 함수의 반환 값, 서브루틴에 대한 참조 또는 포인터로 전달된 매개변수를 통해 얻을 수 있습니다. , 전역 변수도 마찬가지입니다. 또한, 루프에서 주어진 서브루틴에 대한 호출은 일부 조건(다음과 같은 조건)에 따라 서브루틴 자체의 호출 또는 비호출(값을 반환하거나 단순히 작업 완료)로 쉽게 변환될 수 있음을 쉽게 보여줍니다. 이전에는 루프 상태였습니다). 이제 우리의 추상 프로그램을 보면 서브루틴에 값을 전달하고 이를 사용하는 것과 대략 비슷해 보입니다. 서브루틴은 완료되면 변경됩니다. 주어진 알고리즘을 해결하기 위해 반복 루프를 서브루틴에 대한 재귀 호출로 대체했습니다.

반복적 접근 방식으로 재귀를 가져오는 작업은 대칭적입니다.

요약하면 다음과 같은 생각을 표현할 수 있습니다. 각 접근 방식에는 특정 작업에 대한 특정 요구 사항에 따라 결정되는 자체 작업 클래스가 있습니다.

이에 대해 자세히 알아볼 수 있습니다.

열거(주기)와 마찬가지로 재귀에도 중지 조건(기본 사례)이 있어야 합니다(그렇지 않으면 주기와 마찬가지로 재귀도 영원히 작동합니다 - 무한). 이 조건은 재귀가 진행되는 경우(recursion step)입니다. 각 단계에서 다음 호출이 기본 조건을 트리거하고 재귀가 중지될 때까지(또는 마지막 함수 호출로 돌아갈 때까지) 재귀 함수가 호출됩니다. 전체 솔루션은 기본 사례를 해결하는 것으로 귀결됩니다. 복잡한 문제를 해결하기 위해 재귀 함수가 호출되는 경우(기본 사례 아님) 문제를 더 간단한 문제로 줄이기 위해 여러 재귀 호출 또는 단계가 수행됩니다. 그리고 우리가 기본적인 해결책을 얻을 때까지 계속합니다.

따라서 재귀 함수는 다음과 같이 구성됩니다.

• 정지 조건 또는 기본 케이스
• 연속 조건 또는 재귀 단계는 문제를 더 간단한 문제로 줄이는 방법입니다.

계승을 찾는 예를 사용하여 이를 살펴보겠습니다.

Public class Solution ( public static int recursion(int n) ( // 종료 조건 // 기본 사례 // 재귀 반복을 언제 중지할까요? if (n == 1) ( return 1; ) // 재귀 단계 / 재귀 조건 return recursion( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // 재귀 함수 호출 ) )

여기서 기본 조건은 n=1일 때의 조건입니다. 우리는 1!=1임을 알고 1!을 계산하기 때문입니다. 우리는 아무것도 필요하지 않습니다. 2를 계산합니다! 우리는 1!을 사용할 수 있습니다. 2!=1!*2. 3을 계산합니다! 우리는 2!*3이 필요합니다... n을 계산하려면! (n-1)!*n이 필요합니다. 이것이 재귀 단계입니다. 즉, 숫자 n의 계승 값을 얻으려면 이전 숫자의 계승 값에 n을 곱하면 충분합니다.

태그:

• 재귀
• 작업
• 자바

태그 추가

C++의 수많은 재귀 예제가 있는 거대한 기사를 작성하지 않기 위해 여기에 재귀 예제를 하나 더 작성하겠습니다. 에 의해 대체로함수에서 직접 재귀의 기본과 사용을 이해하는 사람은 이 자료를 건너뛰어도 됩니다. 다음은 초보자를 위한 C++ 함수 문서에서와 같이 재귀를 사용하는 예입니다. 재귀

문제 1 - 재귀를 사용하여 1부터 N까지의 계승을 표시합니다.
코드 작성
=============================
STAGE No. 1 빈 프로그램 작성
=============================

#포함하다

#포함하다

#포함하다

정수 메인()
{
system("cls");

getch();
0을 반환합니다;
}

빈 프로그램이 만들어졌으니 코멘트할 필요는 없을 것 같습니다
STAGE No. 2 우리는 재귀 함수 자체를 작성합니다.
=========================================

#포함하다

#포함하다

#포함하다

//재귀 함수
int 사실 (int N )
{

//0! = 1, 1!=1, 2!=2, 3!=6... 왜냐면 처음 2개의 숫자는 1이고 순서가 엄격하지 않으므로 코드에서 이 점을 강제로 적용합니다.

만약 n이라면<2 return 1 ;
그렇지 않으면 n *을 반환합니다. 사실(n–1) //여기서 함수는 자신을 호출합니다.

}

정수 메인()
{
system("cls");
시합<//재귀 함수 호출 지점. 화면에 10의 계승을 인쇄
getch();
0을 반환합니다;
}
ddd
============

C++ 재귀 프로그램의 주요 부분
n * 반환 사실(n–1)

우리 함수는 이전 값을 얻기 위해 다시 계산합니다. 실제 값은 전달된 매개변수입니다. N함수 호출 시점부터. 우리 함수를 호출하는 요점은 프로그램의 메인 블록에서 호출하는 것입니다. 우리의 경우에는 함수에서 호출합니다. 정수 메인()
왜 다음 글이 아닌 이전 글을 쓰고 있는 걸까요? 숫자를 곱하면 여기에서 처음 0 * 1이 현재 값 1이고 0은 이전 계산 값입니다. 이것이 재귀의 본질입니다. 이전 값을 사용하여 현재 값을 계산하고 동일한 계산을 통해 이전 값을 얻습니다. 컴파일러 자체는 이전 값을 계산하고 이 값을 메모리에 저장합니다. 우리가 해야 할 일은 지시를 내리는 것뿐입니다. . 컴파일러의 이러한 기능 덕분에 함수는 자신을 호출하라는 명령을 만나게 됩니다(우리의 경우 사실(n–1) ) 전달된 매개변수를 덮어쓰지 않습니다. N함수를 계산합니다. 전달된 매개변수 N기억 속에 남아있습니다. 이 경우, 우리의 재귀 함수가 이전 결과를 얻기 위해 재귀 계산을 수행하는 또 다른 메모리 영역이 추가로 정의됩니다.

프로그래머들이 그렇게 씹어먹는 판단을 한 것을 용서해주기를 바랍니다. 이것은 대략 초보자가 재귀를 인식하는 방식입니다.

초보자를 위한 이 C++ 블로그가 누군가에게 유용하고 누군가가 C++ 재귀 함수의 기본 개념을 이해하는 데 도움이 되기를 바랍니다.

메모. 이번 글에서도 이전 글과 마찬가지로 1부터 N까지 계산을 한 것이 아니고, 프로그램 내부에 입력된 값까지 계산을 했습니다. 요점은 추가 코드 줄을 작성하고 싶지 않았고 사용자가 이미 데이터를 입력하고 화면에 표시하는 데 능숙하다고 가정했다는 것입니다.

재귀는 과학 분야뿐만 아니라 일상생활에서도 일어나는 꽤 흔한 현상이다. 예를 들어 Droste 효과, Sierpinski 삼각형 등이 있습니다. 재귀를 확인하는 가장 쉬운 방법은 웹 카메라를 처음 켠 후 자연스럽게 컴퓨터 모니터 화면을 가리키는 것입니다. 따라서 카메라는 컴퓨터 화면의 이미지를 기록하고 이 화면에 표시하며 이는 폐쇄 루프와 같습니다. 결과적으로 우리는 터널과 비슷한 것을 관찰하게 될 것입니다.

프로그래밍에서 재귀는 함수와 밀접하게 관련되어 있습니다. 보다 정확하게는 재귀 또는 재귀 함수와 같은 것이 프로그래밍의 함수 덕분입니다. 간단히 말해서 재귀는 함수(메서드)의 일부를 자체적으로 정의하는 것입니다. 즉, 직접적으로(본문에서) 또는 간접적으로(다른 함수를 통해) 자신을 호출하는 함수입니다. 일반적인 재귀 문제는 n!, 피보나치 수를 찾는 것입니다. 우리는 이미 이러한 문제를 해결했지만 루프를 사용하여 즉 반복적으로 해결했습니다. 일반적으로 반복적으로 해결되는 모든 문제는 재귀적으로, 즉 재귀 함수를 사용하여 해결될 수 있습니다. 전체 솔루션은 기본 케이스 또는 기본 케이스라고도 불리는 문제를 해결하는 것으로 귀결됩니다. 재귀 단계 또는 재귀 호출과 같은 것이 있습니다. 복잡한 문제를 해결하기 위해 재귀 함수가 호출되는 경우(기본 사례 아님) 문제를 더 간단한 문제로 줄이기 위해 여러 재귀 호출 또는 단계가 수행됩니다. 그리고 우리가 기본적인 해결책을 얻을 때까지 계속합니다. n을 계산하는 재귀 함수를 선언하는 프로그램을 개발해 봅시다!

"stdafx.h" #include << "Enter n!: "; cin >>n; 시합<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

// 코드 코드::블록

// Dev-C++ 코드

//factorial.cpp: 콘솔 애플리케이션의 진입점을 정의합니다. #포함하다 네임스페이스 std 사용; unsigned long int Factorial(unsigned long int); // 재귀 함수의 프로토타입 int i = 1; // 재귀 호출 횟수를 계산하기 위해 전역 변수를 초기화합니다. unsigned long int result; // 재귀 함수의 반환 결과를 저장하기 위한 전역 변수 int main(int argc, char* argv) ( int n; // 키보드에서 입력된 숫자를 전달하기 위한 지역 변수 cout<< "Enter n!: "; cin >>n; 시합<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

안에 7, 9, 21행데이터 유형은 unsigned long int 로 선언됩니다. 왜냐하면 계승 값이 매우 빠르게 증가하기 때문입니다(예: 이미 10!). = 3,628,800. 데이터 유형의 크기가 충분하지 않으면 결과는 완전히 잘못된 값이 됩니다. 코드는 n!을 찾는 데 필요한 것보다 더 많은 연산자를 선언합니다. 이는 실행 후 프로그램이 재귀 호출의 각 단계에서 어떤 일이 발생하는지 표시하기 위해 수행됩니다. 강조 표시된 코드 줄을 참고하세요. 23, 24, 28행 n!에 대한 재귀적 해법입니다. 23, 24행재귀 함수의 기본 솔루션입니다. 즉, 변수의 값이 에프 1 또는 0과 같습니다(1! = 1 및 0! = 1임을 알고 있으므로) 재귀 호출이 중지되고 각 재귀 호출에 대해 값이 반환되기 시작합니다. 첫 번째 재귀 호출의 값이 반환되면 프로그램은 계산된 계승 값을 반환합니다. 안에 28번째 줄계승() 함수는 자신을 호출하지만 그 인수는 하나 적습니다. 특정 솔루션에 도달할 때마다 인수가 줄어듭니다. 프로그램의 결과(그림 1 참조)

n을 입력하세요!: 5 1단계 결과= 0 2단계 결과= 0 3단계 결과= 0 4단계 결과= 0 5!=120

그림 1 - C++의 재귀

프로그램 결과에 따라 각 단계가 명확하게 표시되며 마지막 재귀 호출을 제외하고 각 단계의 결과는 0입니다. 5개의 계승값을 계산해야 했습니다. 프로그램은 4번의 재귀 호출을 수행했으며 다섯 번째 호출에서 기본 사례를 찾았습니다. 그리고 프로그램이 기본 사례에 대한 솔루션을 얻은 후에는 이전 단계를 해결하고 전체 결과를 출력했습니다. 그림 1에서는 다섯 번째 단계에서 부분 솔루션이 발견되어 궁극적으로 최종 솔루션(예: 120)을 반환했기 때문에 네 단계만 표시됩니다. 그림 2는 재귀 계산 체계 5!를 보여줍니다. 다이어그램은 특정 솔루션에 도달하면 첫 번째 결과가 반환되지만 각 재귀 호출 후에 즉시 반환되지는 않는다는 것을 명확하게 보여줍니다.

그림 2 - C++의 재귀

그래서 5개를 찾으세요! 꼭 알아야 할 4! 그리고 5를 곱합니다. 4! = 4 * 3! 등등. 그림 2에 표시된 다이어그램에 따르면 계산은 특수한 경우, 즉 1!을 찾는 것으로 축소되며, 그 후 각 재귀 호출에 값이 차례로 반환됩니다. 마지막 재귀 호출은 값 5!를 반환합니다.

계승 테이블을 얻기 위해 계승을 찾는 프로그램을 다시 작업해 보겠습니다. 이를 위해 재귀 함수를 호출하는 for 루프를 선언합니다.

네임스페이스 std 사용; unsigned long int Factorial(unsigned long int); // 재귀 함수의 프로토타입 int i = 1; // 재귀 호출 횟수를 계산하기 위해 전역 변수를 초기화합니다. unsigned long int result; // 재귀 함수의 반환 결과를 저장하기 위한 전역 변수 int main(int argc, char* argv) ( int n; // 키보드에서 입력된 숫자를 전달하기 위한 지역 변수 cout<< "Enter n!: "; cin >>n; for (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <>n; for (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i < << "Enter number from the Fibonacci series: "; cin >> <= entered_number; counter++) cout << setw(2) <

// 코드 코드::블록

// Dev-C++ 코드

// fibonacci.cpp: 콘솔 애플리케이션의 진입점을 정의합니다. #포함하다 // 화면에 표시되는 서식 정보를 위한 라이브러리 #include 네임스페이스 std 사용; unsigned long fibonacci(unsigned long); // 피보나치 수열에서 숫자를 검색하기 위한 재귀 함수의 프로토타입 int main(int argc, char* argv) ( unsigned long enter_number; cout<< "Enter number from the Fibonacci series: "; cin >> 입력_번호; for (int 카운터 = 1; 카운터<= entered_number; counter++) cout << setw(2) <

첫 번째 막대에서 세 번째 막대로 세 개의 디스크를 이동해야 한다고 가정해 보겠습니다. 이는 두 번째 막대가 보조 막대임을 의미합니다. 이 문제에 대한 시각적 솔루션은 Flash에서 구현됩니다. 애니메이션을 시작하려면 시작 버튼을 클릭하고, 중지하려면 중지 버튼을 클릭하세요.

프로그램은 n번째 디스크에 대해 작성되어야 합니다. 이 문제를 재귀적으로 해결하기 때문에 먼저 해결책의 특별한 경우를 찾아야 합니다. 이 문제에는 특별한 경우가 하나뿐입니다. 이는 하나의 디스크만 이동해야 하는 경우이며, 이 경우 보조 로드도 필요하지 않지만 우리는 이에 주의를 기울이지 않습니다. 이제 디스크 수가 2개 이상인 경우 재귀 솔루션을 구성해야 합니다. 너무 많이 쓰지 않기 위해 몇 가지 표기법을 소개하겠습니다.

<Б> - 디스크가 처음 위치하는 막대(베이스 막대)
<П> - 보조 또는 중간 막대;
<Ф> — 최종 막대 – 디스크를 이동해야 하는 막대.

또한 문제 해결을 위한 알고리즘을 설명할 때 이러한 표기법을 사용합니다. 세 개의 디스크를 이동하려면 <Б> ~에 <Ф> 먼저 두 개의 디스크를 <Б> ~에 <П> 그런 다음 세 번째 디스크(가장 큰 디스크)를 <Ф> , 왜냐하면 <Ф> 무료

이동 N디스크 <Б> ~에 <Ф> 우리 먼저 움직여야 해 n-1디스크 <Б> ~에 <П> 그런 다음 n번째 디스크(가장 큰 디스크)를 <Ф> , 왜냐하면 <Ф> 무료 이 후에는 이동해야 합니다. n-1디스크 <П> ~에 <Ф> , 막대를 사용하는 동안 <Б> 보조자로. 이 세 가지 작업은 전체 재귀 알고리즘입니다. 의사코드의 동일한 알고리즘:
n-1이동하다 <П>
N이동하다 <Ф>
n-1~에서왔다 <П> ~에 <Ф> , 사용하는 동안 <Б> 보조자로서

// hanoi_tower.cpp: 콘솔 애플리케이션의 진입점을 정의합니다. // 하노이탑 문제를 재귀적으로 해결하는 프로그램 #include "stdafx.h" #include #포함하다 네임스페이스 std 사용; 무효 타워(int, int, int, int); // 재귀 함수의 프로토타입 선언 int count = 1; // 걸음 수를 계산하기 위한 전역 변수 int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>번호; 시합<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> 기본_막대; 시합<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> 최종 막대; int help_rod; // 보조 로드 개수 결정 블록, 초기 로드 개수와 최종 로드 개수 분석 if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(//하노이탑 문제를 풀기 위한 재귀 함수 실행 number, //이동해야 할 디스크 수를 저장하는 변수 basic_rod, //디스크가 처음에 놓일 막대의 수를 저장하는 변수 help_rod 위치, // 보조 막대로 사용되는 막대의 개수를 저장하는 변수 final_rod); // 디스크를 이동해야 하는 로드의 번호를 저장하는 변수 system("pause"); 0을 반환합니다. ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // 재귀 호출 종료 조건 ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

// 코드 코드::블록

// Dev-C++ 코드

// hanoi_tower.cpp: 콘솔 애플리케이션의 진입점을 정의합니다. // 하노이탑 문제를 재귀적으로 해결하는 프로그램 #include #포함하다 네임스페이스 std 사용; 무효 타워(int, int, int, int); // 재귀 함수의 프로토타입 선언 int count = 1; // 단계 수를 계산하기 위한 전역 변수 int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>번호; 시합<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> 기본_막대; 시합<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> 최종 막대; int help_rod; // 보조 로드 개수 결정 블록, 초기 로드 개수와 최종 로드 개수 분석 if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(//하노이탑 문제를 풀기 위한 재귀 함수 실행 number, //이동해야 할 디스크 수를 저장하는 변수 basic_rod, //디스크가 처음에 놓일 막대의 수를 저장하는 변수 help_rod 위치, // 보조 막대로 사용되는 막대의 개수를 저장하는 변수 final_rod); // 디스크를 이동해야 하는 막대의 번호를 저장하는 변수 return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // 재귀 호출 종료 조건 ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

그림 5는 하노이 타워 재귀 프로그램의 예를 보여줍니다. 먼저 디스크 수를 3개로 입력한 다음 베이스 로드(첫 번째)를 도입하고 마지막 로드(세 번째)를 지정했습니다. 자동으로 두 번째 막대가 보조 막대가 되었습니다. 프로그램은 이 문제에 대한 애니메이션 솔루션과 완전히 일치하는 결과를 생성했습니다.

디스크 수 입력: 3 기본 로드 수 입력: 1 최종 로드 수 입력: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

그림 5 - C++의 재귀

그림에서 볼 수 있듯이 먼저 디스크가 1번 막대에서 3번 막대로 이동한 다음 1번 막대에서 2번 막대로, 3번 막대에서 3번 막대로 이동합니다.즉, 프로그램은 디스크 이동 순서와 모든 디스크가 이동되는 최소 단계 수만 표시합니다.

이러한 모든 문제는 반복적으로 해결될 수 있습니다. "반복적으로 해결하는 방법과 재귀적으로 해결하는 방법 중 어느 것이 더 낫습니까?"라는 질문이 생깁니다. 저는 이렇게 대답합니다. “재귀의 단점은 반복보다 훨씬 더 많은 컴퓨터 리소스를 소비한다는 것입니다. 이로 인해 RAM과 프로세서 모두에 과부하가 발생합니다. 특정 문제가 반복적인 방식으로 해결될 수 있다는 것이 명백하다면 재귀를 사용하여 다르게 사용해야 합니다!” 해결되는 문제에 따라 하나 또는 다른 해결 방법을 사용할 때 프로그램 작성의 복잡성이 변경됩니다. 그러나 코드 가독성 측면에서 재귀적 방법을 사용하여 문제를 해결하는 것이 훨씬 더 명확하고 짧은 경우가 더 많습니다.