재귀 이해하기
학교에서 재귀 를 이해하는 데 큰 어려움을 겪고 있습니다. 교수가 그것에 대해 이야기 할 때마다 나는 그것을 얻는 것처럼 보이지만 혼자서 시도하자마자 그것은 완전히 내 두뇌를 날려 버립니다.
나는 밤새 하노이 타워 를 해결하려고 노력하고 있었고 완전히 마음을 날려 버렸습니다. 내 교과서에는 약 30 페이지의 재귀가 있으므로 너무 유용하지 않습니다. 누구든지이 주제를 명확히하는 데 도움이되는 책이나 자료를 알고 있습니까?
다섯 개의 꽃이 들어있는 꽃병은 어떻게 비우나요?
답 : 꽃병이 비어 있지 않은 경우 하나의 꽃을 꺼내고 네 개의 꽃이 들어있는 꽃병을 비 웁니다.
네 개의 꽃이 들어있는 꽃병은 어떻게 비우나요?
답 : 꽃병이 비어 있지 않으면 꽃 한 개를 꺼내서 세 개의 꽃이 들어있는 꽃병을 비 웁니다.
세 개의 꽃이 들어있는 꽃병을 어떻게 비웁니까?
답 : 꽃병이 비어 있지 않은 경우 하나의 꽃을 꺼내고 두 개의 꽃이 들어있는 꽃병을 비 웁니다.
두 개의 꽃이 들어있는 꽃병을 어떻게 비웁니까?
답 : 꽃병이 비어 있지 않으면 꽃 한 개를 꺼내고 꽃 한 개가 들어있는 꽃병을 비 웁니다.
하나의 꽃이 들어있는 꽃병을 어떻게 비우십니까?
답 : 꽃병이 비어 있지 않으면 꽃 한 개를 꺼내고 꽃이없는 꽃병을 비 웁니다.
꽃이없는 꽃병은 어떻게 비우나요?
답 : 꽃병이 비어 있지 않으면 꽃 하나를 꺼내지 만 꽃병이 비어 있으므로 완료됩니다.
반복적입니다. 그것을 일반화합시다 :
N 개의 꽃이 들어있는 꽃병을 어떻게 비우 십니까?
답 : 꽃병이 비어 있지 않으면 꽃 한 개를 꺼내고 N-1 꽃이 들어있는 꽃병을 비 웁니다 .
흠, 코드에서 볼 수 있습니까?
void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
// take one flower and
emptyVase( flowersInVase - 1 ) ;
} else {
// the vase is empty, nothing to do
}
}
흠, for 루프에서 방금 할 수 없었습니까?
예, 재귀를 반복으로 바꿀 수 있지만 종종 재귀가 더 우아합니다.
나무에 대해 이야기합시다. 컴퓨터 과학에서 트리는 노드 로 구성된 구조로 , 각 노드에는 노드 또는 노드 인 자식 수가 있습니다. 이진 트리가 정확히이 노드 만든 나무입니다 두 아이를, 일반적으로 "왼쪽"과 "오른쪽"이라고; 다시 자식은 노드이거나 null 일 수 있습니다. 루트는 다른 노드의 자식이 아닌 노드입니다.
자식과 더불어 노드에 값과 숫자가 있다고 가정하고 어떤 나무의 모든 값을 합산한다고 상상해보십시오.
한 노드의 값을 합산하기 위해 노드 자체의 값을 왼쪽 자식 값 (있는 경우)과 오른쪽 자식 값 (있는 경우)에 추가합니다. 이제 자식이 null이 아닌 경우 노드이기도합니다.
따라서 왼쪽 자식을 합산하기 위해 자식 노드 자체의 값을 왼쪽 자식 값 (있는 경우)과 오른쪽 자식 값 (있는 경우)에 더합니다.
따라서 왼쪽 자식의 왼쪽 자식 값을 합산하기 위해 자식 노드 자체의 값을 왼쪽 자식 값 (있는 경우)과 오른쪽 자식 값 (있는 경우)에 더합니다.
어쩌면 당신은 내가 어디로 갈 것인지 예상했고 코드를보고 싶습니까? 확인:
struct node {
node* left;
node* right;
int value;
} ;
int sumNode( node* root ) {
// if there is no tree, its sum is zero
if( root == null ) {
return 0 ;
} else { // there is a tree
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
}
}
자식이 노드인지 노드인지 확인하기 위해 명시 적으로 테스트하는 대신, 재귀 함수는 null 노드에 대해 0을 반환합니다.
따라서 다음과 같은 트리가 있습니다 (숫자는 값이고 슬래시는 자식을 가리키고 @는 포인터가 null을 가리킴).
5
/ \
4 3
/\ /\
2 1 @ @
/\ /\
@@ @@
루트 (값이 5 인 노드)에서 sumNode를 호출하면 다음을 반환합니다.
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
그것을 제자리로 확장합시다. sumNode가있는 곳이면 어디에서든 return 문의 확장으로 대체합니다 :
sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + sumNode(null ) + sumNode( null ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + 0 + 0 ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 ;
return 5 + 4
+ 2 + 0 + 0
+ 1
+ 3 ;
return 5 + 4
+ 2
+ 1
+ 3 ;
return 5 + 4
+ 3
+ 3 ;
return 5 + 7
+ 3 ;
return 5 + 10 ;
return 15 ;
이제 복합 템플릿의 반복 적용으로 고려하여 임의의 깊이와 "분기"구조를 어떻게 정복했는지 봅시다. 우리의 sumNode 함수를 통해 매번 우리는 단일 if / then 브랜치를 사용하여 단일 노드만을 처리했으며, 스펙에서 직접 자신을 작성하는 두 개의 간단한 return 문을 사용 했습니까?
How to sum a node:
If a node is null
its sum is zero
otherwise
its sum is its value
plus the sum of its left child node
plus the sum of its right child node
이것이 재귀의 힘입니다.
위의 꽃병 예제는 꼬리 재귀 의 예제입니다 . 모든이 꼬리 재귀 수단은 우리가 (우리가 다시 함수를 호출하는 경우입니다)에 반복 경우 재귀 함수에, 우리가했던 마지막 일이라고하는 것입니다.
트리 예제는 꼬리 재귀가 아니 었습니다. 왜냐하면 우리가 한 마지막 일은 올바른 자식을 되풀이하는 것이었지만 왼쪽 자식을 되풀이하기 전에였습니다.
실제로, 우리는 자식을 호출하고 현재 노드의 값을 추가 한 순서는 전혀 중요하지 않습니다.
이제 순서가 중요한 작업을 살펴 보겠습니다. 이진 노드 트리를 사용하지만 이번에는 보유한 값이 숫자가 아닌 문자가됩니다.
우리의 나무는 특별한 속성을 가질 것입니다. 어떤 노드에 대해서도 그 문자는 왼쪽 자식이 보유한 문자 뒤에 (알파벳순) 그리고 오른쪽 자식이 보유한 문자 앞에 (알파벳순) 있습니다.
우리가 원하는 것은 알파벳 순서로 나무를 인쇄하는 것입니다. 트리의 특별한 속성이 주어지면 쉽게 할 수 있습니다. 왼쪽 자식, 노드의 문자, 오른쪽 자식을 인쇄합니다.
우리는 단지 willy-nilly를 인쇄하고 싶지 않기 때문에 인쇄 할 함수를 전달할 것입니다. 이것은 print (char) 함수를 가진 객체입니다. 우리는 그것이 어떻게 작동하는지에 대해 걱정할 필요가 없습니다. 단지 인쇄가 호출 될 때, 어딘가에 무언가를 인쇄 할 것입니다.
코드에서 그것을 보자.
struct node {
node* left;
node* right;
char value;
} ;
// don't worry about this code
class Printer {
private ostream& out;
Printer( ostream& o ) :out(o) {}
void print( char c ) { out << c; }
}
// worry about this code
int printNode( node* root, Printer& printer ) {
// if there is no tree, do nothing
if( root == null ) {
return ;
} else { // there is a tree
printNode( root->left, printer );
printer.print( value );
printNode( root->right, printer );
}
Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );
이제 중요한 작업 순서 외에도이 예제는 재귀 함수로 전달할 수 있음을 보여줍니다. 우리가해야 할 유일한 일은 매번 재귀 호출마다 계속 전달해야한다는 것입니다. 우리는 노드 포인터와 프린터를 함수에 전달했으며 각 재귀 호출마다 "아래로"전달했습니다.
이제 나무가 다음과 같다면 :
k
/ \
h n
/\ /\
a j @ @
/\ /\
@@ i@
/\
@@
무엇을 인쇄할까요?
From k, we go left to
h, where we go left to
a, where we go left to
null, where we do nothing and so
we return to a, where we print 'a' and then go right to
null, where we do nothing and so
we return to a and are done, so
we return to h, where we print 'h' and then go right to
j, where we go left to
i, where we go left to
null, where we do nothing and so
we return to i, where we print 'i' and then go right to
null, where we do nothing and so
we return to i and are done, so
we return to j, where we print 'j' and then go right to
null, where we do nothing and so
we return to j and are done, so
we return to h and are done, so
we return to k, where we print 'k' and then go right to
n where we go left to
null, where we do nothing and so
we return to n, where we print 'n' and then go right to
null, where we do nothing and so
we return to n and are done, so
we return to k and are done, so we return to the caller
따라서 우리가 줄을 보면 인쇄되었습니다.
we return to a, where we print 'a' and then go right to
we return to h, where we print 'h' and then go right to
we return to i, where we print 'i' and then go right to
we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
we return to n, where we print 'n' and then go right to
알파벳 순으로 "ahijkn"을 인쇄 한 것을 볼 수 있습니다.
알파벳순으로 단일 노드를 인쇄하는 방법을 알면 알파벳순으로 전체 트리를 인쇄 할 수 있습니다. 노드의 값을 인쇄하기 전에 왼쪽 자식을 인쇄하고 노드 값을 인쇄 한 후 오른쪽 자식을 인쇄하는 것을 알고있는 것은 (나무에 알파벳순으로 값을 왼쪽으로 정렬하는 특수 속성이 있기 때문에) 방금입니다.
그리고 그건 재귀의 힘 : 전체의 일부를 수행하는 방법 만 알고 (그리고 재귀 멈춰야 할 때는 아는)에 의해 모든 일을 할 수있는.
대부분의 언어에서 || 연산자 || 첫 번째 피연산자가 true 일 때 ( "또는") 단락은 일반적인 재귀 함수는 다음과 같습니다.
void recurse() { doWeStop() || recurse(); }
Luc M 의견 :
따라서 이러한 종류의 답변에 대한 배지를 만들어야합니다. 축하합니다!
고마워, 루크! 그러나 실제로이 답변을 4 번 이상 편집했기 때문에 (마지막 예를 추가하지만 대부분 오타를 수정하고 연마하기 위해-작은 넷북 키보드로 입력하기가 어렵습니다) 더 이상 포인트를 얻을 수 없습니다 . 미래의 답변에 많은 노력을 기울이지 않는 것이 다소 실망 스럽습니다.
https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699 : 여기에 내 의견을 참조 하십시오
당신의 두뇌는 무한 재귀에 빠졌기 때문에 폭발했습니다. 그것은 일반적인 초보자 실수입니다.
믿거 나 말거나, 당신은 이미 재귀를 이해하고 있습니다. 당신은 기능에 대한 일반적이지만 결함이있는 은유에 끌려 가고 있습니다 : 물건이 들어오고 나가는 작은 상자.
"넷에서의 재귀에 대한 자세한 정보 찾기"와 같은 작업이나 절차 대신 생각하십시오. 재귀 적이며 아무런 문제가 없습니다. 이 작업을 완료하려면 다음을 수행하십시오.
a) "재귀"에 대한 Google 결과 페이지를 읽습니다. b) 일단 읽은 후에는 첫 번째 링크를 따르고 ... a.1) 재귀에 관한 새 페이지를 읽으십시오. b.1) 읽은 후에는 첫 번째 링크를 따르고 ... a.2) 재귀에 관한 새 페이지를 읽으십시오. b.2) 읽은 후에는 첫 번째 링크를 따르고 ...
보시다시피, 문제없이 오랫동안 재귀 작업을 해왔습니다.
얼마나 오랫동안 그 일을 하시겠습니까? 뇌가 터질 때까지 영원히? 물론, 당신은 당신이 작업을 완료했다고 생각할 때마다 주어진 시점에서 멈출 것입니다.
"망상의 재귀에 대해 더 많이 찾아 보라고"요구할 때 이것을 지정할 필요가 없습니다. 왜냐하면 당신은 인간이고 스스로 그것을 추론 할 수 있기 때문입니다.
컴퓨터는 잭을 유추 할 수 없으므로 명시적인 결말을 포함해야합니다. "인터넷에서 재귀에 대해 자세히 알아 보십시오. 이해하거나 최대 10 페이지를 읽을 때까지 "
또한 Google의 결과 페이지에서 "재귀"에 대해 시작해야한다고 추론했으며, 이는 다시 컴퓨터가 할 수없는 일입니다. 재귀 타스크에 대한 전체 설명에는 명시적인 시작점이 포함되어야합니다.
"그물에 재귀에 대한 자세한 내용을 보려면 당신이 그것을 이해하거나 할 때까지 10 페이지의 최대 읽게 하고 www.google.com/search?q=recursion에서 시작 "
모든 것을 이해하기 위해 다음 책 중 하나를 시도해보십시오.
- 공통 리스프 : 상징적 계산에 대한 부드러운 소개. 이것은 재귀에 대한 가장 귀여운 비 수학적 설명입니다.
- 작은 계획자.
재귀를 이해하려면 샴푸 병의 라벨을 보면됩니다.
function repeat()
{
rinse();
lather();
repeat();
}
이것의 문제는 종료 조건이 없으며 재귀가 무기한으로 반복되거나 샴푸 또는 온수가 부족할 때까지 (스택을 날리는 것과 유사한 외부 종료 조건)입니다.
간단한 용어로 재귀를 잘 설명하는 책을 원한다면 Douglas Hofstadter 의 Gödel, Escher, Bach : The Eternal Golden Braid , 특히 5 장을 살펴보십시오 . 재귀와 함께 설명하는 것도 훌륭합니다. 컴퓨터 과학과 수학의 여러 복잡한 개념은 이해하기 쉬운 방식으로 설명이 다른 설명과 함께 제공됩니다. 이전에 이런 종류의 개념에 많이 노출되지 않았다면, 그것은 꽤 마음에 드는 책이 될 수 있습니다.
이것은 질문보다 더 많은 불만입니다. 재귀에 대해 더 구체적인 질문이 있습니까? 곱셈과 마찬가지로 사람들이 많이 쓰는 것은 아닙니다.
곱셈에 대해 생각해보십시오.
질문:
a * b는 무엇입니까?
대답:
b가 1이면 a입니다. 그렇지 않으면 a + a * (b-1)입니다.
a * (b-1)는 무엇입니까? 해결 방법은 위의 질문을 참조하십시오.
이 간단한 방법이 재귀를 이해하는 데 도움이 될 것이라고 생각합니다. 이 메소드는 특정 조건이 충족 될 때까지 자신을 호출 한 후 다음을 리턴합니다.
function writeNumbers( aNumber ){
write(aNumber);
if( aNumber > 0 ){
writeNumbers( aNumber - 1 );
}
else{
return;
}
}
이 함수는 0까지 공급할 첫 번째 숫자부터 모든 숫자를 인쇄합니다. 따라서 :
writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0
기본적으로 발생하는 것은 writeNumbers (10)이 10을 쓴 다음 writeNumbers (9)를 호출하여 9를 쓴 다음 writeNumber (8) 등을 호출하는 것입니다. writeNumbers (1)이 1을 쓴 다음 writeNumbers (0)을 호출하여 0을 쓴다 엉덩이는 writeNumbers (-1)를 호출하지 않습니다.
이 코드는 기본적으로 다음과 같습니다.
for(i=10; i>0; i--){
write(i);
}
그렇다면 for 루프가 본질적으로 동일한 지 여부를 묻는 재귀를 사용하는 이유는 무엇입니까? 잘 for 루프를 중첩해야하지만 얼마나 깊이 중첩되어 있는지 알지 못하는 경우 주로 재귀를 사용합니다. 예를 들어 중첩 배열에서 항목을 인쇄하는 경우 :
var nestedArray = Array('Im a string',
Array('Im a string nested in an array', 'me too!'),
'Im a string again',
Array('More nesting!',
Array('nested even more!')
),
'Im the last string');
function printArrayItems( stringOrArray ){
if(typeof stringOrArray === 'Array'){
for(i=0; i<stringOrArray.length; i++){
printArrayItems( stringOrArray[i] );
}
}
else{
write( stringOrArray );
}
}
printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'
이 함수는 100 레벨로 중첩 될 수있는 배열을 취할 수 있지만 for 루프를 작성하면 100 번 중첩해야합니다.
for(i=0; i<nestedArray.length; i++){
if(typeof nestedArray[i] == 'Array'){
for(a=0; i<nestedArray[i].length; a++){
if(typeof nestedArray[i][a] == 'Array'){
for(b=0; b<nestedArray[i][a].length; b++){
//This would be enough for the nestedAaray we have now, but you would have
//to nest the for loops even more if you would nest the array another level
write( nestedArray[i][a][b] );
}//end for b
}//endif typeod nestedArray[i][a] == 'Array'
else{ write( nestedArray[i][a] ); }
}//end for a
}//endif typeod nestedArray[i] == 'Array'
else{ write( nestedArray[i] ); }
}//end for i
보시다시피 재귀 방법이 훨씬 좋습니다.
실제로 재귀를 사용하여 문제의 복잡성을 줄입니다. 쉽게 해결할 수있는 간단한 기본 사례에 도달 할 때까지 재귀를 적용합니다. 이를 통해 마지막 재귀 단계를 해결할 수 있습니다. 그리고 이것으로 다른 모든 재귀 단계는 원래 문제까지 올라갑니다.
재귀
메소드 A는 메소드 A를 호출합니다. 메소드 A는 메소드 A를 호출합니다. 결국이 메소드 A 중 하나는 호출 및 종료되지 않지만 무언가 호출되기 때문에 재귀입니다.
하드 드라이브의 모든 폴더 이름을 인쇄하려는 재귀의 예 : (C #)
public void PrintFolderNames(DirectoryInfo directory)
{
Console.WriteLine(directory.Name);
DirectoryInfo[] children = directory.GetDirectories();
foreach(var child in children)
{
PrintFolderNames(child); // See we call ourself here...
}
}
예를 들어 설명하려고합니다.
넌 뭔지 알아! 방법? 그렇지 않은 경우 : http://en.wikipedia.org/wiki/Factorial
삼! = 1 * 2 * 3 = 6
여기 의사 코드가 간다
function factorial(n) {
if (n==0) return 1
else return (n * factorial(n-1))
}
시도해 봅시다 :
factorial(3)
n 0입니까?
아니!
그래서 우리는 재귀에 대해 더 깊이 파고 들었습니다.
3 * factorial(3-1)
3-1 = 2
2 == 0입니까?
아니!
그래서 우리는 더 깊이 간다! 3 * 2 * 계승 (2-1) 2-1 = 1
1 == 0입니까?
아니!
그래서 우리는 더 깊이 간다! 3 * 2 * 1 * 계승 (1-1) 1-1 = 0
0 == 0입니까?
예!
우리는 사소한 경우가 있습니다
그래서 우리는 3 * 2 * 1 * 1 = 6
나는 당신이 도움이되기를 바랍니다
어떤 책을 사용하고 있습니까?
실제로 좋은 알고리즘에 대한 표준 교과서는 Cormen & Rivest입니다. 내 경험은 재귀를 아주 잘 가르친다는 것입니다.
재귀는 이해하기 어려운 프로그래밍 부분 중 하나이며 본능이 필요한 반면 배울 수 있습니다. 그러나 좋은 설명, 좋은 예, 좋은 예가 필요합니다.
또한 일반적으로 30 페이지가 많고 단일 프로그래밍 언어로 30 페이지가 혼동됩니다. 일반적인 책에서 일반적으로 재귀를 이해하기 전에 C 또는 Java로 재귀를 배우려고 시도하지 마십시오.
재귀 함수는 단순히 필요한만큼 자신을 호출하는 함수입니다. 무언가를 여러 번 처리해야하는 경우 유용하지만 실제로 몇 번 필요한지 확실하지 않습니다. 어떤 방식으로 재귀 함수를 루프 유형으로 생각할 수 있습니다. 그러나 루프처럼 프로세스가 중단 될 조건을 지정해야합니다. 그렇지 않으면 무한히됩니다.
http://javabat.com 은 재귀를 연습 할 수있는 재미 있고 흥미로운 곳입니다. 그들의 예는 상당히 가벼워지고 광범위하게 작동합니다 (먼저 그것을 원한다면). 참고 : 그들의 접근은 연습을 통해 배웁니다. 다음은 단순히 for 루프를 대체하기 위해 작성한 재귀 함수입니다.
for 루프 :
public printBar(length)
{
String holder = "";
for (int index = 0; i < length; i++)
{
holder += "*"
}
return holder;
}
동일한 작업을 수행하는 재귀가 있습니다. (위와 같이 사용되도록 첫 번째 방법에 과부하가 걸린다는 점에 유의하십시오). 또한 인덱스를 유지 관리하는 또 다른 방법이 있습니다 (for 문이 위의 방법과 비슷 함). 재귀 함수는 자체 인덱스를 유지해야합니다.
public String printBar(int Length) // Method, to call the recursive function
{
printBar(length, 0);
}
public String printBar(int length, int index) //Overloaded recursive method
{
// To get a better idea of how this works without a for loop
// you can also replace this if/else with the for loop and
// operationally, it should do the same thing.
if (index >= length)
return "";
else
return "*" + printBar(length, index + 1); // Make recursive call
}
짧은 이야기를 짧게하려면 재귀는 적은 코드를 작성하는 좋은 방법입니다. 후자의 printBar에는 if 문이 있음을 알 수 있습니다. 조건에 도달하면 재귀를 종료하고 이전 메서드로 돌아가는 이전 메서드로 돌아갑니다. printBar (8)로 보낸 경우 ********를 얻습니다. for 루프와 동일한 기능을 수행하는 간단한 함수의 예를 통해 이것이 도움이되기를 바랍니다. Java Bat에서 더 연습 할 수 있습니다.
재귀 함수를 작성하는 진정한 수학적 방법은 다음과 같습니다.
1 : f (n-1)에 맞는 함수가 있다고 가정하고 f (n)이 올바른 f를 빌드하십시오. 2 : f (1)이 정확하도록 f를 빌드하십시오.
이것은 당신이 기능은 수학적으로 정확하다는 것을 증명할 수 있으며,이 호출 어떻게 유도 . 기본 사례가 다르거 나 여러 변수에 대해 더 복잡한 기능을 갖는 것과 같습니다. f (x)가 모든 x에 대해 정확하다고 상상하는 것과 같습니다.
이제 "간단한"예제입니다. x 센트를 만들기 위해 5 센트와 7 센트의 코인 조합을 가질 수 있는지 여부를 결정할 수있는 기능을 구축하십시오. 예를 들어 17 센트 x 2x5 + 1x7은 가능하지만 16 센트는 불가능합니다.
이제 x <n만큼 x 센트를 만들 수 있는지 알려주는 함수가 있다고 상상해보십시오. 이 함수를 can_create_coins_small로 호출하십시오. n의 함수를 만드는 방법을 상상하는 것은 상당히 간단해야합니다. 이제 함수를 빌드하십시오.
bool can_create_coins(int n)
{
if (n >= 7 && can_create_coins_small(n-7))
return true;
else if (n >= 5 && can_create_coins_small(n-5))
return true;
else
return false;
}
여기서의 트릭은 can_create_coins가 n에 대해 작동한다는 사실을 인식하는 것입니다. can_create_coins를 can_create_coins_small로 대체하여 다음을 제공 할 수 있습니다.
bool can_create_coins(int n)
{
if (n >= 7 && can_create_coins(n-7))
return true;
else if (n >= 5 && can_create_coins(n-5))
return true;
else
return false;
}
마지막으로해야 할 일은 무한 재귀를 막기위한 기본 사례를 갖는 것입니다. 0 센트를 만들려고하면 동전이 없어서 가능합니다. 이 조건을 추가하면 다음이 제공됩니다.
bool can_create_coins(int n)
{
if (n == 0)
return true;
else if (n >= 7 && can_create_coins(n-7))
return true;
else if (n >= 5 && can_create_coins(n-5))
return true;
else
return false;
}
infinite descent 라는 메소드를 사용하여이 함수가 항상 리턴된다는 것을 증명할 수 있지만 여기서는 필요하지 않습니다. f (n)은 더 낮은 값의 n 만 호출하며 항상 0에 도달한다고 상상할 수 있습니다.
이 정보를 사용하여 Tower of Hanoi 문제를 해결하려면 n-1 태블릿을 a에서 b로 (a / b에 대해) 이동하고 n 테이블을 a에서 b로 이동하는 기능이 있다고 가정합니다. .
Common Lisp의 간단한 재귀 예제 :
MYMAP는 목록의 각 요소에 함수를 적용합니다.
1) 빈 목록에는 요소가 없으므로 빈 목록을 반환합니다-() 및 NIL은 모두 빈 목록입니다.
2) 첫 번째 목록에 함수를 적용하고 나머지 목록 (재귀 호출)에 대해 MYMAP을 호출 한 다음 두 결과를 새 목록으로 결합하십시오.
(DEFUN MYMAP (FUNCTION LIST)
(IF (NULL LIST)
()
(CONS (FUNCALL FUNCTION (FIRST LIST))
(MYMAP FUNCTION (REST LIST)))))
추적 된 실행을 보자. 함수를 입력하면 인수가 인쇄됩니다. 기능을 종료하면 결과가 인쇄됩니다. 각 재귀 호출마다 출력이 레벨에서 들여 쓰기됩니다.
이 예는 목록의 각 숫자에서 SIN 함수를 호출합니다 (1 2 3 4).
Command: (mymap 'sin '(1 2 3 4))
1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
| 3 Enter MYMAP SIN (3 4)
| | 4 Enter MYMAP SIN (4)
| | 5 Enter MYMAP SIN NIL
| | 5 Exit MYMAP NIL
| | 4 Exit MYMAP (-0.75680256)
| 3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)
이것이 우리의 결과입니다 .
(0.841471 0.9092975 0.14112002 -0.75680256)
6 살짜리에게 재귀를 설명하려면 먼저 5 살짜리에게 설명하고 1 년을 기다리십시오.
사실, 이것은 재귀 호출이 어렵지 않고 단순해야하기 때문에 유용한 반례입니다. 5 세까지 재귀를 설명하는 것이 더 어려울 수 있으며 0으로 재귀를 멈출 수는 있지만 재귀를 0 세로 설명하는 간단한 해결책은 없습니다.
재귀를 사용하여 문제를 해결하려면 먼저 같은 방법으로 해결할 수있는 하나 이상의 간단한 문제 로 세분화 한 다음 추가 재귀없이 해결할 수있을 정도로 문제가 간단하면 더 높은 수준으로 되돌릴 수 있습니다.
사실, 그것은 재귀 문제를 해결하는 방법에 대한 재귀적인 정의였습니다.
어린이는 암시 적으로 재귀를 사용합니다.
디즈니 월드로 여행
아직 있습니까? (아니요)
아직 거기 있나요? (곧)
아직 있습니까? (거의 ...)
우리는 아직 있습니까? (SHHHH)
우리는 아직있다?(!!!!!)
그 시점에서 아이는 잠들게됩니다 ...
이 카운트 다운 함수는 간단한 예입니다.
function countdown()
{
return (arguments[0] > 0 ?
(
console.log(arguments[0]),countdown(arguments[0] - 1)) :
"done"
);
}
countdown(10);소프트웨어 프로젝트에 적용되는 Hofstadter의 법칙 도 관련이 있습니다.
Chomsky에 따르면 인간 언어의 본질은 유한 한 두뇌가 무한한 문법이라고 생각하는 것을 만들어내는 능력이다. 이를 통해 그는 우리가 말할 수있는 것에 대한 상한선이없고, 언어의 문장 수에 대한 상한선이 없으며, 특정 문장의 크기에 대한 상한선이 없다는 것을 의미합니다. Chomsky는 이러한 인간 언어의 모든 창의성을 뒷받침하는 기본 도구는 재귀라고 주장했다. 한 구절이 같은 유형의 다른 구 내에서 재발 할 수있는 능력. "John 's brother 's house"라고하면 명사 구 "형제 집"에 나오는 명사 "house"가 있고 다른 명사 구 "John 's brother 's house"에 명사 구가 나타납니다. 이것은 많은 의미가 있으며
참고 문헌
재귀 솔루션으로 작업 할 때 항상 다음을 시도합니다.
- 기본 사례를 먼저 설정합니다. 즉 계승에 대한 해에서 n = 1 일 때
- 다른 모든 경우에 대한 일반적인 규칙을 생각해보십시오.
또한 재귀 솔루션에는 여러 가지 유형이 있으며, 프랙탈 및 기타 여러 가지에 유용한 나누기 및 정복 방법이 있습니다.
간단한 문제를 해결하기 위해 먼저 문제를 해결할 수 있다면 도움이 될 것입니다. 일부 예는 계승을 풀고 n 번째 피보나치 수를 생성합니다.
참고로 Robert Sedgewick의 알고리즘을 적극 권장합니다.
희망이 도움이됩니다. 행운을 빕니다.
아야. 나는 작년에 하노이의 탑을 알아 내려고 노력했다. TOH의 까다로운 점은 재귀의 단순한 예가 아니라는 것입니다. 중첩 된 재귀를 사용하면 각 호출에서 타워의 역할도 변경됩니다. 내가 이해할 수있는 유일한 방법은 말 그대로 내 눈의 고리의 움직임을 시각화하고 재귀 호출이 무엇인지 구두로 표현하는 것입니다. 하나의 반지로 시작한 다음 2, 3으로 시작합니다. 나는 실제로 인터넷에서 게임을 주문했다. 그것을 얻기 위해 뇌를 깨뜨리는 데 2 ~ 3 일이 걸렸습니다.
재귀 함수는 각 호출에서 비트를 압축하는 스프링과 같습니다. 각 단계에서 약간의 정보 (현재 컨텍스트)를 스택에 넣습니다. 마지막 단계에 도달하면 스프링이 해제되어 모든 값 (컨텍스트)을 한 번에 수집합니다!
이 은유가 효과적인지 확실하지 않습니다 ... :-)
어쨌든, 조금 인공적인 고전적인 예 (비효율적이고 쉽게 평평하기 때문에 최악의 예인 팩토리얼, 피보나치, 하노이 ...)를 넘어서 (실제로 프로그래밍 사례에서는 거의 사용하지 않습니다) 그것이 실제로 사용되는 곳을 보는 것이 흥미 롭습니다.
가장 일반적인 경우는 나무를 걷는 것입니다 (또는 그래프이지만 일반적으로 나무가 더 일반적입니다).
예를 들어, 폴더 계층 : 파일을 나열하려면 파일을 반복하십시오. 하위 디렉토리를 찾으면 파일을 나열하는 함수가 인수로 새 폴더를 사용하여 자신을 호출합니다. 이 새 폴더 (및 하위 폴더)를 다시 나열하면 컨텍스트가 다음 파일 (또는 폴더)로 다시 시작됩니다.
GUI 구성 요소의 계층 구조를 그릴 때의 또 다른 구체적인 사례는 창과 같은 컨테이너를 갖는 것이 일반적입니다. 창도 될 수있는 구성 요소를 보유하는 구성 요소 나 복합 구성 요소 등이 있습니다. 페인팅 루틴은 각 구성 요소의 페인트 기능을 반복적으로 호출합니다 보유하고있는 모든 구성 요소의 페인트 기능 등을 호출합니다.
확실하지는 않지만 확실하지는 않지만, 과거에 내가 겪고 있었던 것이었기 때문에 실제로 교재를 사용하는 것을 좋아합니다.
일벌을 생각하십시오. 꿀을 만들려고합니다. 그것은 일을하고 다른 일벌이 꿀을 휴식을 취할 것으로 기대합니다. 벌집이 가득 차면 멈 춥니 다.
그것을 마술로 생각하십시오. 구현하려는 것과 동일한 이름의 함수가 있으며 하위 문제를 주면 해결하고 부품의 솔루션을 솔루션과 통합하는 것만으로도 문제를 해결할 수 있습니다 너에게 줬다.
예를 들어,리스트의 길이를 계산하려고합니다. 우리의 함수 magical_length와 magical_length를 가진 우리의 마법 도우미를 호출하자 우리는 첫 번째 요소가없는 서브리스트를 주면, 우리가 서브리스트의 길이를 마술로 줄 것이라는 것을 알고 있습니다. 그런 다음이 정보를 업무에 통합하는 방법 만 생각하면됩니다. 첫 번째 요소의 길이는 1이고 magic_counter는 하위 목록 n-1의 길이를 제공하므로 총 길이는 (n-1) + 1-> n입니다.
int magical_length( list )
sublist = rest_of_the_list( list )
sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
return 1 + sublist_length
그러나 빈 목록을 제공하면 어떤 일이 발생하는지 고려하지 않았기 때문에이 답변은 불완전합니다. 우리는 우리가 가진 목록에 항상 하나 이상의 요소가 있다고 생각했습니다. 따라서 빈리스트가 주어지고 응답이 명백히 0이면 답이 무엇인지 생각해야합니다. 따라서이 정보를 함수에 추가하면 이것을 기본 / 가장자리 조건이라고합니다.
int magical_length( list )
if ( list is empty) then
return 0
else
sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
return 1 + sublist_length
참고 URL : https://stackoverflow.com/questions/717725/understanding-recursion
'IT story' 카테고리의 다른 글
| Swift에서 NSLocalizedString은 무엇입니까? (0) | 2020.04.26 |
|---|---|
| 라 라벨 블레이드 템플릿에서 변수를 설정하는 방법 (0) | 2020.04.26 |
| PHP에서 스위치 케이스 '또는'을 사용하는 방법 (0) | 2020.04.26 |
| 프로그래밍 방식으로 iOS 7 기본 파란색을 얻으려면 어떻게해야합니까? (0) | 2020.04.26 |
| SQL Server의 숨겨진 기능 (0) | 2020.04.26 |