재귀 및 반복
재귀를 이해하려면 재귀를 이해해야 합니다...
반복 프로그래밍 - 주기적인 데이터 처리 프로세스의
한 단계입니다.
종종 현재 단계(반복)의 반복 알고리즘은 이전 단계에서 계산된 동일한 작업 또는 작업의 결과를 사용합니다. 이러한 계산의 한 예는 순환 관계의 계산입니다.
재귀 값의 간단한 예는
\(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);
|
함수 호출에는 약간의 추가 오버헤드가 포함되므로 비재귀 요인 계산이 약간 더 빠릅니다.
결론: 재귀 없이 간단한 반복 알고리즘으로 프로그램을 작성할 수 있는 경우 재귀 없이 작성해야 합니다. 그러나 여전히 계산 프로세스가 재귀에 의해서만 구현되는 많은 종류의 문제가 있습니다.
반면에 재귀 알고리즘은 종종 더 이해하기 쉽습니다.
Problem
주어진 자연수
n의 자릿수를
로 반환하는 함수
K(n)를 정의합니다.
\(\begin{방정식*} K(n) = \begin{cases} 1 &\text{n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{cases} \end{equation*}\).
위의 비율을 사용하여 자연수
n의 자릿수를 계산하는 재귀 함수를 작성하세요.
Запрещенные операторы: for;while;until