서브루틴. 재귀

프로시저 또는 함수는 내부에 있는 다른 프로시저에 대한 호출을 포함할 수 있습니다. 포함하여 서브루틴은 자신을 호출할 수 있습니다. 이 경우 컴퓨터는 상관하지 않습니다. 그는 언제나처럼 위에서 아래로 만난 명령을 일관되게 실행합니다.

수학을 기억한다면 그곳에서 수학적 귀납법의 원리를 만날 수 있다. 그것은 다음과 같습니다: 어떤 진술은 모든 자연적인 n if
에 대해 참입니다.     1)  n = 1에 대해 유효합니다.
    2) 임의의 자연 n = k 에 대한 진술의 유효성에서 n = k+1에 대해 참이라는 결론이 나옵니다.

프로그래밍에서 이 기술을 재귀라고 합니다.

재귀는 주어진 간단한 기본 사례를 기반으로 집합 자체의 관점에서 개체 집합을 정의하는 방법입니다.

재귀 직접 호출하거나 다른 프로시저 및 함수를 통해 호출하는 프로시저(함수)입니다.
재귀 절차의 예:

보이드 Rec(int a)
{
  if(a>0) { Rec(a-1); }
  Console.WriteLine(a);
}

재귀 작업은 도식적으로 순서도로 나타낼 수 있습니다.

우리는 재귀가 서브루틴에 포함된 명령의 반복 실행이라는 것을 알아냈습니다. 그리고 이것은 차례로 사이클의 작업과 유사합니다. Prolog와 같이 루프 구성이 전혀 없는 프로그래밍 언어가 있습니다. 
루프 for의 작업을 시뮬레이트해 봅시다. 
for 루프에는 걸음 수 카운터 변수가 포함되어 있습니다. 재귀 서브루틴에서는 이러한 변수를 매개변수로 전달할 수 있습니다. <예비> // 두 개의 매개변수가 있는 procedure LoopImitation() // 첫 번째 매개변수 – 걸음 수 카운터, 두 번째 매개변수 – 총 단계 수 정적 무효 LoopImitation(int i, int n) { Console.WriteLine("Hello N" + i); // 모든 값 i 에 대해 반복되는 문장 if (i < n) // 루프 카운터가 n과 같을 때까지, { LoopImitation(i+1, n); // 새 i+1 매개변수가 있는 인스턴스 프로시저(다음 i 값으로 이동)<코드> } }

재귀 및 반복

반복 프로그래밍 - 주기적인 데이터 처리 프로세스의 한 단계입니다. 
종종 현재 단계(반복)의 반복 알고리즘은 이전 단계에서 계산된 동일한 작업 또는 작업의 결과를 사용합니다.  이러한 계산의 한 예는 순환 관계의 계산입니다. 
재귀 값의 간단한 예는 \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \ \cdot N\)입니다.
각 단계(반복)에서의 값 계산은 \(N=N \cdot i\) 입니다.  \(N\) 값을 계산할 때 이미 저장된 값\(N\).< br />
숫자의 계승은 반복 공식을 사용하여 설명할 수도 있습니다.
\(\begin{방정식*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

이 설명이 재귀 함수에 불과하다는 것을 알 수 있습니다.
여기서 첫 번째 줄(\(n <= 1\))은 기본 사례(재귀 종료 조건)이고 두 번째 줄은 다음 단계로의 전환입니다.  < br />   <몸>
함수 호출에는 약간의 추가 오버헤드가 포함되므로 비재귀 요인 계산이 약간 더 빠릅니다. 

결론: 재귀 없이 간단한 반복 알고리즘으로 프로그램을 작성할 수 있는 경우 재귀 없이 작성해야 합니다. 그러나 여전히 계산 프로세스가 재귀에 의해서만 구현되는 많은 종류의 문제가 있습니다.
반면에 재귀 알고리즘은 종종 더 이해하기 쉽습니다.

재귀 계승 함수	반복 알고리즘
<예비> 정적 int Factorial(int n){ if (n > 1) return n * 계승(n - 1); 그렇지 않으면 1을 반환합니다. }	<예비> int x = 1; for (int i = 2; i <= n; i++) x = x * i; Console.WriteLine("%d", x);
한 숫자 체계에서 다른 숫자 체계로 숫자를 재귀적으로 변환 프로시저의 일부 상황에서는 인수 없이 return 이라는 단어를 사용할 수 있습니다. 즉, 프로시저는 여전히 아무 것도 반환하지 않습니다. ;return 는 매개변수 값이 반복되는 기본 사례에서 하강을 종료하는 데 사용됩니다. 예를 들어 숫자를 10진수에서 2진수로 변환하는 절차는 다음과 같습니다. 정적 void printTwo(int n) {     if (n == 0) 반환;   printTwo(n / 2);   if (n % 2 == 0) Console.Write(0);   그렇지 않으면 Console.Write(1); } Training problem 재귀 번역: 8진수 시스템의 숫자
과제 Tumba-Yumba 부족 언어의 알파벳으로; 네 글자: "K", "L", "M" 및 "N". 이 알파벳의 문자로 만들 수 있는 n개의 문자로 구성된 모든 단어를 표시해야 합니다. 문제는 더 작은 문제로 축소될 수 있는 일반적인 무차별 대입 문제입니다. 단어를 순차적으로 문자로 대체합니다. 단어의 첫 번째 위치는 알파벳 4자(K. L, M, N) 중 하나일 수 있습니다. 문자 K를 먼저 넣겠습니다. 그런 다음 첫 번째 문자 K가 있는 모든 변형을 가져오려면 나머지 n - 1 위치 등에서 문자의 가능한 모든 조합을 열거해야 합니다. (그림 참조). 따라서 문제는 길이가 n - 1인 네 가지 문제를 해결하는 것으로 축소됩니다.   n자를 재귀적으로 반복 w[0]='K';; // 마지막 L-1 문자를 반복합니다. w[0]='L';; // 마지막 L-1 문자를 반복합니다. w[0]='M';; // 마지막 L-1 문자를 반복합니다. w[0]='N'; // 마지막 L-1 문자를 반복합니다. w - 작업 단어를 저장하는 문자열. 따라서 우리는 재귀를 얻었습니다. 재귀 절차의 형태로 문제의 해결책을 마련할 수 있습니다.  재귀가 언제 끝날지 결정하는 것이 남아 있습니까? 모든 문자가 설정된 경우, 즉 설정된 문자의 수는 n입니다. 이 경우 결과 단어를 화면에 표시하고 절차를 종료해야 합니다. C# 프로그램은 다음과 같습니다. <사업부> // w - 변경 가능한 매개변수(문자열 결과) // TumbaWords 프로시저는 알파벳을 문자열로 전달하고, // 단어 단어와 이미 설정된 문자 수(처음에 – 0) 정적 무효 TumbaWords( 문자열 A, 참조 문자열 w, int N ) { if (N == w.Length) // w.Length - 문자열의 문자 수 {   // 모든 문자가 이미 해당 단어로 설정된 경우       // 그런 다음 문자열을 출력하고 프로시저를 종료해야 합니다. Console.WriteLine(w); 반품; } for ( int i = 0; i < w.Length; i ++ ) // 위의 조건이 거짓인 경우(즉, 모든 문자가 간격을 두지 않고, {     // 위의 조건이 false인 경우(즉, 모든 문자가 공백이 아닌 경우     // 그런 다음 루프에서 알파벳의 모든 문자를 살펴보고   // 번갈아 가며 첫 번째 여유 공간에 문자를 놓습니다. w += A[i]; TumbaWords(A, ref w, N+1); w = w.Remove(w.Length - 1); // 그런 다음 마지막으로 추가된 문자를 제거합니다.   // 동일한 접두사를 가진 새 단어를 만들기 위해 } } 정적 무효 메인() { int n = Convert.ToInt32(Console.ReadLine()); 문자열 단어 = "";; TumbaWords("KLMN", 참조 단어, 0); } 참고 w는 변경 가능한 매개변수(결과 문자열)입니다! Training problem 여러 줄 반복