재귀
프로시저 또는 함수는 그 안에 다른 프로시저에 대한 호출을 포함할 수 있습니다. 포함하여 서브루틴은 자신을 호출할 수 있습니다. 이 경우 컴퓨터는 상관하지 않습니다. 또한 언제나처럼 위에서 아래로 만난 명령을 일관되게 실행합니다.
수학을 기억한다면 그곳에서 수학적 귀납법의 원리를 만날 수 있습니다. 다음과 같습니다.
일부 진술은 모든 자연적인 n if 에 대해 참입니다.
1. n = 1 및 에 대해 유효합니다.
2. 임의의 자연 n = k에 대한 진술의 타당성으로부터 n = k + 1에 대해 참이라는 결론이 나옵니다.
프로그래밍에서는 이 기술을 재귀라고 합니다.
재귀는 주어진 기준을 기반으로 세트 자체 측면에서 객체 세트를 정의하는 방법입니다. 간단한 기본 사례.
재귀는 직접 호출하거나 다른 프로시저 및 함수를 통해 호출하는 프로시저(함수)입니다.
예시
<예비>
def Rec(a):
if (a>0): Rec(a-1)
인쇄(a)
재귀 작업을 도식적으로 순서도로 나타낼 수 있습니다.
Rec() 프로시저는 매개변수 3으로 실행되고, 매개변수 3으로 프로시저 내에서 매개변수 2로 프로시저가 호출되고, 매개변수 0으로 프로시저가 호출될 때까지 계속됩니다. 매개변수 0으로 프로시저가 호출되면, 재귀 호출은 더 이상 발생하지 않으며 매개변수가 0인 프로시저는 숫자 0을 인쇄하고 종료합니다. 그런 다음 매개변수 1이 있는 프로시저로 제어가 다시 전송되고 숫자 1을 인쇄하여 작업을 마치는 식입니다. 매개변수 3이 있는 프로시저 전에.
호출된 모든 프로시저는 작업이 완료될 때까지 메모리에 저장됩니다. 동시 프로시저의 수를 재귀 깊이라고 합니다.
|
루프 교체로서의 재귀
우리는 재귀가 서브루틴에 포함된 명령을 반복적으로 실행하는 것을 보았습니다. 그리고 이것은 차례로 사이클의 작업과 유사합니다. 루프 구성이 전혀 없는 프로그래밍 언어가 있습니다. 예: 프롤로그.
루프 for의 작업을 시뮬레이션해 봅시다.
for 루프에는 걸음 수 카운터 변수가 포함되어 있습니다. 재귀 서브루틴에서 이러한 변수는 매개변수로 전달될 수 있습니다.
<예비>
# 프로시저 LoopImitation() 두 매개변수 포함
# 첫 번째 매개변수 – 걸음 수 카운터, 두 번째 매개변수 – 총 단계 수
def LoopImitation(i, n):
print("Hello N", i) # 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\))은 기본 사례(재귀 종료 조건)이고 두 번째 줄은 다음 단계로의 전환입니다.
<몸>
| 재귀 계승 함수 |
반복 알고리즘 |
|
데프 팩토리얼(n):
n > 1:
n * 계승(n - 1) 반환
또 다른:
반환 1
|
x=1
범위(1, n + 1)의 i에 대해:
x = x * i;
|
함수 호출에는 약간의 추가 오버헤드가 포함되므로 비재귀 요인 계산이 약간 더 빠릅니다.
결론: 재귀 없이 간단한 반복 알고리즘으로 프로그램을 작성할 수 있는 경우 재귀 없이 작성해야 합니다. 그러나 여전히 계산 프로세스가 재귀에 의해서만 구현되는 많은 종류의 문제가 있습니다.
반면에 재귀 알고리즘은 종종 더 이해하기 쉽습니다.
과제
"Tumba-Yumba" 부족 언어의 알파벳으로; 네 글자: "K", "L", "M" 및 "N". 이 알파벳의 문자로 만들 수 있는 n개의 문자로 구성된 모든 단어를 화면에 표시해야 합니다
문제는 더 작은 문제로 축소될 수 있는 일반적인 무차별 대입 문제입니다.
단어를 순차적으로 문자로 대체합니다.
단어의 첫 번째 위치는 알파벳 4자( K, L, M, N) 중 하나일 수 있습니다.
먼저 문자 'K'를 먼저 입력합니다. 그런 다음 첫 번째 문자 'K'로 모든 변형을 가져오려면 나머지 n-1 위치 및 .etc. (그림 참조)
따라서 우리는 재귀 솔루션을 생각해 냈습니다. 루프에서 가능한 모든 첫 글자를 살펴보고 (알파벳의 각 글자를 처음에 차례로 배치) 각 경우에 대해 가능한 모든 "꼬리"를 만듭니다. 길이 <코드>n-1.
문자 반복 반복
나머지 부분이 비어 있을 때(n = 0), 즉, 재귀를 중지하고 완성된 단어를 출력해야 합니다. 모든 문자가 이미 선택되었습니다.
재귀 절차는 다음과 같습니다.
<예비>
def TumbaWords(단어, 알파벳, n):
n < 1:
인쇄(단어)
반품
알파벳 c의 경우:
TumbaWords(단어+c, 알파벳, n - 1)
|
|