재귀를 이해하려면 재귀를 이해해야 합니다...
반복 프로그래밍 — 넓은 의미에서 – 자체 호출로 이어지지 않고 작업이 여러 번 반복되는 데이터 처리 조직( %BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Recursion" >재귀). 좁은 의미에서 — 한 단계 순환 데이터 처리 프로세스.
종종 현재 단계(반복)의 반복 알고리즘은 이전 단계에서 계산된 동일한 작업 또는 작업의 결과를 사용합니다. 이러한 계산의 한 예는 순환 관계의 계산입니다.
재귀 값의 간단한 예는 계승입니다.
\(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \ \cdot N\)
각 단계(반복)에서의 값 계산은
\(N=N \cdot i\) 입니다.
\(N\) 값을 계산할 때 이미 저장된 값
\(N\).< br />
숫자의 계승은
반복 공식을 사용하여 설명할 수도 있습니다.
이 설명이 재귀 함수에 불과하다는 것을 알 수 있습니다.
여기서 첫 번째 줄(
\(n <= 1\)) — 이것은 기본 케이스(재귀의 종료 조건)이고 두 번째 줄은 다음 단계로의 전환입니다.
<몸>
| 재귀 계승 함수는 다음과 같습니다. |
일반적인 비재귀적 방식으로 계승을 찾는 알고리즘 비교 |
function Factorial(n: 정수): 정수;
시작하다
n > 1 그럼
계승 := n * 계승(n - 1)
그렇지 않으면
팩토리얼 := 1;
종료; |
x := 1;
for i := 2 to n do
x := x * i;
writeln(x); |
함수 호출에는 약간의 추가 오버헤드가 포함되므로 비재귀 요인 계산이 약간 더 빠릅니다.
결론: 재귀 없이 간단한 반복 알고리즘으로 프로그램을 작성할 수 있는 경우 재귀 없이 작성해야 합니다. 그러나 여전히 계산 프로세스가 재귀에 의해서만 구현되는 많은 종류의 문제가 있습니다.
반면에 재귀 알고리즘은 종종 더 이해하기 쉽습니다.
Problem
주어진 자연수 n의 자릿수를 반환하는 함수 K(n)을 정의합니다.
자연수 n의 자릿수를 계산하는 재귀 함수를 작성하십시오.
Запрещенные операторы: for;while;until