재귀란 무엇이며 언제 사용해야 합니까?

Question

메일링 리스트와 온라인 토론에 정기적으로 올라오는 주제 중 하나는 컴퓨터 공학 학위 취득의 장점(또는 단점)입니다.부정적인 측면에서 계속해서 제기되는 주장은 그들이 몇 년 동안 코딩을 해왔고 재귀를 사용한 적이 없다는 것입니다.

질문은 다음과 같습니다.

1. 재귀란 무엇입니까?
2. 재귀는 언제 사용하나요?
3. 사람들은 왜 재귀를 사용하지 않습니까?

Answer 1

에 대한 좋은 설명이 많이 있습니다. 재귀 이 스레드에서 이 답변은 대부분의 언어에서 이를 사용하면 안되는 이유에 대한 것입니다.* 대부분의 주요 명령형 언어 구현(예:C, C++, Basic, Python, Ruby, Java 및 C#의 모든 주요 구현) 반복 재귀보다 훨씬 더 바람직합니다.

이유를 알아보려면 위의 언어에서 함수를 호출하는 데 사용하는 단계를 살펴보세요.

1. 공간이 조각되어 있다 스택 함수의 인수 및 지역 변수에 대해
2. 함수의 인수가 이 새로운 공간에 복사됩니다.
3. 컨트롤이 해당 기능으로 점프합니다.
4. 함수의 코드가 실행됩니다.
5. 함수의 결과가 반환 값으로 복사됩니다.
6. 스택이 이전 위치로 되감겨집니다.
7. 컨트롤은 함수가 호출된 위치로 다시 이동합니다.

이러한 모든 단계를 수행하는 데는 시간이 걸리며 일반적으로 루프를 반복하는 데 걸리는 시간보다 약간 더 걸립니다.그러나 실제 문제는 1단계에 있습니다.많은 프로그램이 시작되면 스택에 단일 메모리 청크를 할당하고 해당 메모리가 부족해지면(종종 재귀로 인해 항상 그런 것은 아님) 프로그램이 충돌합니다. 스택 오버플로.

따라서 이러한 언어에서는 재귀가 느려지고 충돌에 취약해집니다.그러나 그것을 사용하는 것에 대한 몇 가지 주장이 여전히 있습니다.일반적으로 재귀적으로 작성된 코드는 읽는 방법을 알고 나면 더 짧고 좀 더 우아해집니다.

언어 구현자가 사용할 수 있는 기술이 있습니다. 테일 콜 최적화 이는 스택 오버플로의 일부 클래스를 제거할 수 있습니다.간결하게 말하면:함수의 반환 표현식이 단순히 함수 호출의 결과인 경우 스택에 새 수준을 추가할 필요가 없으며 호출되는 함수에 대해 현재 수준을 재사용할 수 있습니다.안타깝게도 테일콜 최적화가 내장된 명령형 언어 구현은 거의 없습니다.

* 나는 재귀를 좋아합니다. 내가 가장 좋아하는 정적 언어 루프를 전혀 사용하지 않으며, 재귀는 어떤 작업을 반복적으로 수행하는 유일한 방법입니다.나는 재귀가 조정되지 않은 언어에서는 일반적으로 좋은 아이디어라고 생각하지 않습니다.

** 그런데 Mario, 당신의 AlignString 함수의 일반적인 이름은 "join"입니다. 그리고 당신이 선택한 언어에 아직 이 기능이 구현되어 있지 않다면 놀랄 것입니다.

Answer 2

재귀의 간단한 영어 예입니다.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Answer 3

가장 기본적인 컴퓨터 과학의 의미에서 재귀는 자기 자신을 호출하는 함수입니다.연결 목록 구조가 있다고 가정해 보겠습니다.

struct Node {
    Node* next;
};

그리고 연결 목록의 길이를 확인하려면 재귀를 사용하여 이 작업을 수행할 수 있습니다.

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(물론 for 루프로도 수행할 수 있지만 개념을 설명하는 데 유용합니다)

Answer 4

함수가 자신을 호출하여 루프를 생성할 때마다 이것이 재귀입니다.모든 것과 마찬가지로 재귀에도 좋은 용도와 나쁜 용도가 있습니다.

가장 간단한 예는 함수의 마지막 줄이 자기 자신에 대한 호출인 꼬리 재귀입니다.

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

그러나 이는 더 효율적인 반복으로 쉽게 대체될 수 있기 때문에 형편없고 거의 무의미한 예입니다.결국 재귀는 함수 호출 오버헤드로 인해 어려움을 겪게 되는데, 위의 예에서는 함수 자체 내부의 작업에 비해 상당히 클 수 있습니다.

따라서 반복보다는 재귀를 수행하는 전체 이유는 호출 스택 영리한 일을 하려고요.예를 들어, 동일한 루프 내에서 서로 다른 매개변수를 사용하여 함수를 여러 번 호출하는 경우 이는 다음을 수행하는 방법입니다. 분기.전형적인 예는 시에르핀스키 삼각형.

호출 스택이 세 방향으로 분기되는 재귀를 사용하여 매우 간단하게 그 중 하나를 그릴 수 있습니다.

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

반복을 통해 동일한 작업을 수행하려고 하면 수행하는 데 훨씬 더 많은 코드가 필요하다는 것을 알게 될 것입니다.

다른 일반적인 사용 사례에는 계층 구조 탐색이 포함될 수 있습니다.웹사이트 크롤러, 디렉토리 비교 등

결론

실용적인 측면에서 반복 분기가 필요할 때마다 재귀가 가장 적합합니다.

Answer 5

재귀는 분할 정복 사고방식을 바탕으로 문제를 해결하는 방법입니다.기본 아이디어는 원래 문제를 더 작은(더 쉽게 풀 수 있는) 인스턴스로 나누고, 해당 작은 인스턴스를 해결한 다음(일반적으로 동일한 알고리즘을 다시 사용하여) 최종 솔루션으로 다시 조립하는 것입니다.

표준 예제는 n의 계승을 생성하는 루틴입니다.n의 팩토리얼은 1과 n 사이의 모든 숫자를 곱하여 계산됩니다.C#의 반복 솔루션은 다음과 같습니다.

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

반복 솔루션에는 놀라운 것이 없으며 C#에 익숙한 사람이라면 누구나 이해할 수 있을 것입니다.

재귀적 해법은 n번째 Factorial이 n * Fact(n-1)임을 인식하여 구합니다.또는 다른 말로 하면, 특정 팩토리얼 숫자가 무엇인지 안다면 다음 팩토리얼 숫자를 계산할 수 있습니다.C#의 재귀 솔루션은 다음과 같습니다.

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

이 함수의 첫 번째 부분은 다음과 같이 알려져 있습니다. 기본 케이스 (또는 때로는 가드 조항) 알고리즘이 영원히 실행되는 것을 방지하는 것입니다.함수가 1 이하의 값으로 호출될 때마다 값 1을 반환합니다.두 번째 부분은 더 흥미롭고 다음과 같이 알려져 있습니다. 재귀 단계.여기서는 약간 수정된 매개 변수(1씩 감소)를 사용하여 동일한 메서드를 호출한 다음 결과에 n 복사본을 곱합니다.

처음 접했을 때 다소 혼란스러울 수 있으므로 실행 시 어떻게 작동하는지 살펴보는 것이 좋습니다.FactRec(5)를 호출한다고 상상해 보세요.우리는 루틴에 들어가고 기본 사례에 의해 선택되지 않으므로 다음과 같이 끝납니다.

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

매개변수 4를 사용하여 메소드를 다시 입력하면 가드 절에 의해 다시 중지되지 않으므로 다음과 같이 끝납니다.

// In FactRec(4)
return 4 * FactRec(3);

이 반환 값을 위의 반환 값으로 대체하면 다음을 얻습니다.

// In FactRec(5)
return 5 * (4 * FactRec(3));

이는 최종 솔루션이 어떻게 도달했는지에 대한 단서를 제공하므로 각 단계를 빠르게 추적하고 표시할 것입니다.

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

최종 대체는 기본 사례가 트리거될 때 발생합니다.이 시점에서 우리는 우선 팩토리얼의 정의와 직접적으로 동일한 간단한 대수 공식을 가지고 있습니다.

메서드를 호출할 때마다 기본 사례가 트리거되거나 매개 변수가 기본 사례에 더 가까운 동일한 메서드에 대한 호출(종종 재귀 호출이라고 함)이 발생한다는 점에 유의하는 것이 좋습니다.그렇지 않은 경우 메서드는 영원히 실행됩니다.

Answer 6

재귀는 자신을 호출하는 함수로 문제를 해결하는 것입니다.이에 대한 좋은 예는 계승 함수입니다.팩토리얼은 예를 들어 5의 팩토리얼이 5 * 4 * 3 * 2 * 1이 되는 수학 문제입니다.이 함수는 C#에서 양의 정수에 대해 이 문제를 해결합니다(테스트되지 않음 - 버그가 있을 수 있음).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Answer 7

재귀는 문제의 더 작은 버전을 해결한 다음 그 결과와 다른 계산을 사용하여 원래 문제에 대한 답을 공식화함으로써 문제를 해결하는 방법을 말합니다.종종 더 작은 버전을 해결하는 과정에서 이 방법은 해결하기 쉬운 "기본 사례"에 도달할 때까지 더 작은 버전의 문제를 해결하는 등의 작업을 계속합니다.

예를 들어, 숫자에 대한 계승을 계산하려면 X, 다음과 같이 나타낼 수 있습니다. X times the factorial of X-1.따라서 이 방법은 다음의 계승을 찾기 위해 "반복"됩니다. X-1, 그런 다음 얻은 모든 것을 곱합니다. X 최종 답변을 드리려고 합니다.물론 팩토리얼을 구하려면 X-1, 먼저 계승을 계산합니다 X-2, 등등.기본 사례는 다음과 같습니다. X 0 또는 1이며, 이 경우 반환해야 한다는 것을 알고 있습니다. 1 ~부터 0! = 1! = 1.

Answer 8

고려 오래되고 잘 알려진 문제:

수학에서는 최대 공약수 (gcd) … 0이 아닌 두 개 이상의 정수 중 나머지 없이 숫자를 나누는 가장 큰 양의 정수입니다.

gcd의 정의는 놀라울 정도로 간단합니다.

모드는 어디에 있나요? 모듈로 연산자 (즉, 정수 나누기 후의 나머지)

영어로, 이 정의는 모든 숫자와 0의 최대 공약수는 그 숫자이며, 두 숫자의 최대 공약수는 다음과 같습니다. 중 그리고 N 의 최대공약수이다 N 그리고 나눈 후 나머지 중 ~에 의해 N.

이것이 작동하는 이유를 알고 싶으면 Wikipedia 기사를 참조하십시오. 유클리드 알고리즘.

예를 들어 gcd(10, 8)을 계산해 보겠습니다.각 단계는 바로 전 단계와 동일합니다.

1. gcd(10, 8)
2. gcd(10, 10 모드 8)
3. gcd(8, 2)
4. gcd(8, 8 모드 2)
5. gcd(2, 0)
6. 2

첫 번째 단계에서 8은 0이 아니므로 정의의 두 번째 부분이 적용됩니다.10 mod 8 = 2 왜냐하면 8은 10에 한 번 들어가고 나머지는 2이기 때문입니다.3단계에서 두 번째 부분이 다시 적용되지만 이번에는 2가 8을 나머지 없이 나누기 때문에 8 mod 2 = 0입니다.5단계에서 두 번째 인수는 0이므로 답은 2입니다.

gcd가 등호의 왼쪽과 오른쪽에 모두 나타나는 것을 보셨나요?수학자들은 이 정의가 재귀적이라고 말할 것입니다. 왜냐하면 여러분이 정의하는 표현식이 재발하다 그 정의 내부.

재귀적 정의는 우아한 경향이 있습니다.예를 들어, 목록의 합계에 대한 재귀적 정의는 다음과 같습니다.

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

어디 head 목록의 첫 번째 요소이고 tail 목록의 나머지 부분입니다.참고하세요 sum 마지막에 정의 내에서 반복됩니다.

어쩌면 목록의 최대값을 선호할 수도 있습니다.

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

음수가 아닌 정수의 곱셈을 재귀적으로 정의하여 일련의 덧셈으로 바꿀 수 있습니다.

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

곱셈을 일련의 덧셈으로 변환하는 방법이 이해가 되지 않는다면 몇 가지 간단한 예를 확장하여 어떻게 작동하는지 확인해 보세요.

병합 정렬 멋진 재귀 정의가 있습니다.

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

무엇을 찾아야 할지 안다면 재귀적 정의는 어디에나 있습니다.이러한 모든 정의가 어떻게 매우 간단한 기본 사례를 가지고 있는지 주목하세요. 예를 들어, gcd(m, 0) = m.재귀 사례는 문제를 조금씩 줄여서 쉬운 답을 얻습니다.

이러한 이해를 통해 이제 다른 알고리즘을 이해할 수 있습니다. 재귀에 관한 Wikipedia의 기사!

Answer 9

1. 자신을 호출하는 함수
2. 기능이 (쉽게) 간단한 작업과 문제의 작은 부분에 대한 동일한 기능으로 분해될 수 있는 경우.오히려 이것이 재귀의 좋은 후보가 된다고 말하고 싶습니다.
3. 그들이하다!

정식 예는 다음과 같은 계승입니다.

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

일반적으로 재귀가 반드시 빠른 것은 아니며(재귀 함수가 작은 경향이 있기 때문에 함수 호출 오버헤드가 높은 경향이 있음, 위 참조) 일부 문제(스택 오버플로가 있는 사람이 있습니까?)가 발생할 수 있습니다.어떤 사람들은 사소한 경우에 '올바르게' 하기가 어렵다고 말하지만 나는 실제로 그런 말을 믿지 않습니다.어떤 상황에서는 재귀가 가장 적합하며 특정 함수를 작성하는 가장 우아하고 명확한 방법입니다.일부 언어는 재귀 솔루션을 선호하고 훨씬 더 최적화한다는 점에 유의해야 합니다(LISP가 떠오릅니다).

Answer 10

재귀 함수는 자기 자신을 호출하는 함수입니다.내가 그것을 사용하는 가장 일반적인 이유는 트리 구조를 탐색하기 때문입니다.예를 들어, 확인란이 있는 TreeView가 있는 경우(새 프로그램 설치, "설치할 기능 선택" 페이지 생각) 다음과 같은 "모두 선택" 버튼이 필요할 수 있습니다(의사 코드).

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

따라서 checkRecursively는 먼저 전달된 노드를 확인한 다음 해당 노드의 각 자식에 대해 자신을 호출하는 것을 볼 수 있습니다.

재귀에 대해서는 약간 주의가 필요합니다.무한 재귀 루프에 빠지면 스택 오버플로 예외가 발생합니다. :)

사람들이 적절할 때 그것을 사용해서는 안되는 이유를 생각할 수 없습니다.어떤 상황에서는 유용하지만 다른 상황에서는 유용하지 않습니다.

내 생각에 이것은 흥미로운 기술이기 때문에 일부 코더는 실제로 정당한 이유 없이 필요한 것보다 더 자주 사용하게 될 수도 있습니다.이로 인해 일부 서클에서는 재귀가 나쁜 이름을 갖게 되었습니다.

Answer 11

재귀는 자신을 직접 또는 간접적으로 참조하는 표현입니다.

간단한 예로 재귀적 약어를 생각해 보세요.

• 암소 비슷한 일종의 영양 약자 GNU는 유닉스가 아니다
• PHP 약자 PHP:하이퍼텍스트 전처리기
• YAML 약자 YAML은 마크업 언어가 아닙니다
• 와인 약자 와인은 에뮬레이터가 아닙니다
• 비자 약자 비자 국제 서비스 협회

Wikipedia의 더 많은 예

Answer 12

재귀는 내가 "프랙탈 문제"라고 부르는 것과 가장 잘 작동합니다. 여기서는 큰 것의 더 작은 버전으로 구성된 큰 것을 처리하고, 각 버전은 큰 것의 더 작은 버전입니다.트리 또는 중첩된 동일한 구조와 같은 항목을 탐색하거나 검색해야 하는 경우 재귀의 좋은 후보가 될 수 있는 문제가 있는 것입니다.

사람들은 여러 가지 이유로 재귀를 피합니다.

1. 나를 포함한 대부분의 사람들은 함수형 프로그래밍이 아닌 절차적 또는 객체 지향 프로그래밍을 선호합니다.그러한 사람들에게는 반복적 접근 방식(일반적으로 루프 사용)이 더 자연스럽게 느껴집니다.

2. 절차적 또는 객체 지향 프로그래밍에 초보적인 프로그래밍을 해본 사람들은 오류가 발생하기 쉬우므로 재귀를 피하라는 말을 자주 들어왔습니다.

3. 우리는 재귀가 느리다는 말을 자주 듣습니다.루틴에서 반복적으로 호출하고 반환하려면 많은 스택 푸시 및 팝핑이 필요하며 이는 루핑보다 느립니다.나는 일부 언어가 다른 언어보다 이를 더 잘 처리한다고 생각하며, 그러한 언어는 지배적인 패러다임이 절차적이거나 객체 지향적인 언어가 아닐 가능성이 높습니다.

4. 내가 사용해 본 프로그래밍 언어 중 적어도 두어 개는 스택이 그다지 깊지 않기 때문에 특정 깊이를 넘어서면 재귀를 사용하지 말라는 권고를 들었던 기억이 납니다.

Answer 13

재귀문은 입력 내용과 이미 수행한 작업의 조합으로 다음에 수행할 프로세스를 정의하는 명령문입니다.

예를 들어 계승을 사용합니다.

factorial(6) = 6*5*4*3*2*1

그러나 Factorial(6)도 다음과 같다는 것을 쉽게 알 수 있습니다:

6 * factorial(5) = 6*(5*4*3*2*1).

그래서 일반적으로:

factorial(n) = n*factorial(n-1)

물론, 재귀에서 까다로운 점은 이미 수행한 작업의 관점에서 사물을 정의하려면 시작할 곳이 필요하다는 것입니다.

이 예에서는 Factorial(1) = 1을 정의하여 특별한 경우를 만듭니다.

이제 우리는 그것을 아래에서 위로 봅니다:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Factorial(1) = 1로 정의했으므로 "바닥"에 도달합니다.

일반적으로 재귀 프로시저는 두 부분으로 구성됩니다.

1) 동일한 절차를 통해 "이미 수행한" 작업과 결합된 새로운 입력 측면에서 일부 절차를 정의하는 재귀 부분.(즉. factorial(n) = n*factorial(n-1))

2) 시작할 위치를 제공하여 프로세스가 영원히 반복되지 않도록 하는 기본 부분(예: factorial(1) = 1)

처음에는 머리를 이해하는 것이 다소 혼란스러울 수 있지만, 여러 가지 예를 살펴보면 모든 것이 하나로 합쳐질 것입니다.개념을 더 깊이 이해하고 싶다면 수학적 귀납법을 공부하세요.또한 일부 언어는 재귀 호출에 최적화되어 있지만 다른 언어는 그렇지 않다는 점에 유의하세요.주의하지 않으면 엄청나게 느린 재귀 함수를 만드는 것은 꽤 쉽지만 대부분의 경우 성능을 향상시키는 기술도 있습니다.

도움이 되었기를 바랍니다...

Answer 14

나는 이 정의를 좋아한다:
재귀에서 루틴은 문제 자체의 작은 부분을 해결하고 문제를 더 작은 조각으로 나눈 다음 각 작은 조각을 해결하기 위해 자신을 호출합니다.

나는 또한 Code Complete에서 재귀에 대한 Steve McConnell의 논의를 좋아합니다. 그는 재귀에 관한 컴퓨터 과학 책에서 사용된 예를 비판했습니다.

계승이나 피보나치 수에 재귀를 사용하지 마세요

컴퓨터 과학 교과서의 한 가지 문제는 재귀의 바보 같은 예를 제시한다는 것입니다.전형적인 예는 Factorial을 계산하거나 Fibonacci 시퀀스를 계산하는 것입니다.재귀는 강력한 도구이며, 그 중 어느 경우에도 그것을 사용하는 것이 정말 바보입니다.저를 위해 일한 프로그래머가 재귀를 사용하여 계승을 계산하면 다른 사람을 고용 할 것입니다.

나는 이것이 제기하기에 매우 흥미로운 점이며 재귀가 종종 오해되는 이유일 수 있다고 생각했습니다.

편집하다:이것은 Dav의 답변을 파헤친 것이 아닙니다. 이 글을 게시했을 때 해당 답변을 본 적이 없었습니다.

Answer 15

1.) 방법은 스스로 호출 할 수 있다면 재귀 적입니다.직접적으로:

void f() {
   ... f() ... 
}

또는 간접적으로:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) 재귀를 사용하는 경우

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) 사람들은 반복 코드를 작성하는 것이 매우 복잡한 경우에만 재귀를 사용합니다.예를 들어, 사전 주문, 사후 주문과 같은 트리 순회 기술은 반복적 및 재귀적으로 만들 수 있습니다.그러나 일반적으로 우리는 단순성 때문에 재귀를 사용합니다.

Answer 16

간단한 예는 다음과 같습니다.세트의 요소 수.(물건을 세는 더 좋은 방법이 있지만 이것은 좋은 간단한 재귀 예제입니다.)

먼저 두 가지 규칙이 필요합니다.

1. 세트가 비어 있으면 세트의 항목 개수는 0입니다(이런!).
2. 세트가 비어 있지 않으면 개수는 하나의 항목이 제거된 후 세트에 있는 항목 수에 1을 더한 값입니다.

다음과 같은 집합이 있다고 가정합니다.[xxx].얼마나 많은 항목이 있는지 세어 봅시다.

1. 집합은 비어 있지 않은 [x x x]이므로 규칙 2를 적용합니다.항목 수는 [x x]의 항목 수에 1을 더한 것입니다(예:항목을 제거했습니다).
2. 집합은 [x x]이므로 규칙 2를 다시 적용합니다.1 + [x]의 항목 수.
3. 집합은 [x]이며 여전히 규칙 2와 일치합니다.하나 + [] 안의 항목 수.
4. 이제 집합은 규칙 1과 일치하는 []입니다.개수는 0입니다!
5. 이제 4단계(0)의 답을 알았으므로 3단계(1 + 0)를 풀 수 있습니다.
6. 마찬가지로 이제 3단계(1)의 답을 알았으므로 2단계(1+1)를 풀 수 있습니다.
7. 그리고 마지막으로 이제 2단계(2)에서 답을 알았으므로 1단계(1 + 2)를 풀고 [x x x]의 항목 수인 3을 얻을 수 있습니다.만세!

우리는 이것을 다음과 같이 표현할 수 있습니다.

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

재귀 솔루션을 적용할 때 일반적으로 최소한 두 가지 규칙이 있습니다.

• 기본은 모든 데이터를 "소진"했을 때 어떤 일이 발생하는지 설명하는 간단한 사례입니다.이는 일반적으로 "처리할 데이터가 부족한 경우 대답은 X입니다."의 변형입니다.
• 아직 데이터가 있는 경우 어떤 일이 발생하는지 설명하는 재귀 규칙입니다.이는 일반적으로 "데이터 세트를 더 작게 만들고 규칙을 더 작은 데이터 세트에 다시 적용"하는 일종의 규칙입니다.

위의 내용을 의사 코드로 변환하면 다음과 같은 결과를 얻습니다.

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

다른 사람들이 다룰 것이라고 확신하는 더 많은 유용한 예(예: 트리 통과)가 있습니다.

Answer 17

글쎄, 그것은 당신이 가지고 있는 꽤 괜찮은 정의입니다.그리고 위키피디아에도 좋은 정의가 있습니다.그래서 나는 당신을 위해 또 다른 (아마도 더 나쁜) 정의를 추가하겠습니다.

사람들이 "재귀"를 언급할 때 일반적으로 작업이 완료될 때까지 반복적으로 자신을 호출하는 자신이 작성한 함수에 대해 이야기합니다.재귀는 데이터 구조의 계층 구조를 탐색할 때 도움이 될 수 있습니다.

Answer 18

예:계단의 재귀적 정의는 다음과 같습니다.계단은 다음으로 구성됩니다.- 단일 단계와 계단 (재귀) - 또는 단일 단계 만 (종료)

Answer 19

해결된 문제를 반복하려면:아무것도 하지 마세요. 이제 끝났습니다.
미해결 문제를 반복하려면 다음 안내를 따르세요.다음 단계를 수행한 후 나머지 단계를 반복합니다.

Answer 20

일반 영어로:다음 3가지 작업을 수행할 수 있다고 가정합니다.

1. 사과 하나 가져가세요
2. 탈리 마크를 적어보세요
3. 집계 표시 계산

당신의 테이블 위에는 많은 사과가 있는데, 사과가 몇 개 있는지 알고 싶습니다.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

완료될 때까지 동일한 작업을 반복하는 과정을 재귀라고 합니다.

이것이 당신이 찾고 있는 "평범한 영어" 답변이기를 바랍니다!

Answer 21

재귀 함수는 자신에 대한 호출을 포함하는 함수입니다.재귀 구조체는 자신의 인스턴스를 포함하는 구조체입니다.두 가지를 재귀 클래스로 결합할 수 있습니다.재귀 항목의 핵심 부분은 자체 인스턴스/호출을 포함한다는 것입니다.

서로 마주보는 두 개의 거울을 생각해 보세요.우리는 그들이 만드는 깔끔한 무한대 효과를 보았습니다.각 반사는 거울의 다른 인스턴스 등에 포함된 거울의 인스턴스입니다.자신의 모습을 담은 거울이 재귀이다.

ㅏ 이진 검색 트리 재귀의 좋은 프로그래밍 예입니다.구조는 각 노드가 노드 인스턴스 2개를 포함하는 재귀적입니다.이진 검색 트리에서 작업하는 함수도 재귀적입니다.

Answer 22

이것은 오래된 질문이지만 물류 관점(즉, 알고리즘 정확성 관점이나 성능 관점이 아닌)에서 답변을 추가하고 싶습니다.

업무에 Java를 사용하는데 Java는 중첩 기능을 지원하지 않습니다.따라서 재귀를 수행하려면 외부 함수를 정의해야 할 수도 있고(내 코드가 Java의 관료적 규칙에 충돌하기 때문에 존재함) 코드를 완전히 리팩토링해야 할 수도 있습니다(정말 하기 싫습니다).

따라서 나는 종종 재귀를 피하고 대신 스택 작업을 사용합니다. 왜냐하면 재귀 자체가 본질적으로 스택 작업이기 때문입니다.

Answer 23

트리 구조가 있을 때마다 이를 사용하고 싶습니다.XML을 읽는 데 매우 유용합니다.

Answer 24

프로그래밍에 적용되는 재귀는 기본적으로 작업을 수행하기 위해 다른 매개 변수를 사용하여 자체 정의 내부(자체 내부)에서 함수를 호출하는 것입니다.

Answer 25

"나에게 망치가 있다면 모든 것을 못처럼 보이게 만들어라."

재귀는 문제 해결 전략이다. 거대한 문제는 모든 단계에서 매번 같은 망치를 사용하여 "2개의 작은 것을 하나의 더 큰 것으로 바꾸는 것"입니다.

예

당신의 책상이 1024장의 서류들로 가득 차 있다고 가정해 보십시오.재귀를 사용하여 엉망진창에서 깔끔하고 깨끗한 종이 더미를 어떻게 만드나요?

1. 나누다: 모든 시트를 펼치면 각 "스택"에 시트가 하나만 있게 됩니다.
2. 정복하다:
   2. 돌아다니며 각 시트를 다른 시트 위에 놓으십시오.이제 2개의 스택이 생겼습니다.
   3. 돌아다니며 각 2개 스택을 다른 2개 스택 위에 놓으십시오.이제 4개의 스택이 생겼습니다.
   4. 돌아다니며 각 4개 스택을 다른 4개 스택 위에 놓으십시오.이제 8개의 스택이 생겼습니다.
   5. ...계속해서 ...
   6. 이제 1024장의 거대한 더미가 하나 생겼습니다!

모든 것을 세는 것(꼭 필요한 것은 아님)을 제외하면 이는 매우 직관적이라는 점에 유의하세요.실제로는 1장 스택까지 내려갈 수는 없지만 가능하며 여전히 작동합니다.중요한 부분은 망치입니다.팔을 사용하면 언제든지 하나의 스택을 다른 스택 위에 올려 더 큰 스택을 만들 수 있으며, 어느 스택이 얼마나 큰지는 (합당한 범위 내에서) 중요하지 않습니다.

Answer 26

재귀는 특정 작업을 수행할 수 있도록 메서드 자체를 호출하는 프로세스입니다.코드의 중복성을 줄입니다.대부분의 재귀 함수나 메서드에는 재귀 호출을 중단하기 위한 조건이 있어야 합니다.조건이 충족되면 자체 호출을 중지합니다. 이렇게 하면 무한 루프가 생성되는 것을 방지할 수 있습니다.모든 함수가 재귀적으로 사용하기에 적합한 것은 아닙니다.

Answer 27

안녕하세요, 죄송합니다. 내 의견이 다른 사람의 의견과 일치한다면 그냥 일반 영어로 재귀를 설명하려고 하는 것뿐입니다.

Jack, John, Morgan이라는 세 명의 관리자가 있다고 가정해 보겠습니다.Jack은 2명의 프로그래머(John 3명, Morgan 5명)를 관리합니다.당신은 모든 관리자에게 300달러를 주려고 하는데 그 비용이 얼마인지 알고 싶습니다.대답은 분명합니다. 하지만 Morgan의 직원 중 2명이 관리자이기도 하면 어떻게 될까요?

여기에 재귀가 옵니다.계층 구조의 맨 위에서 시작합니다.여름 비용은 0$입니다.Jack으로 시작한 다음 직원으로 관리자가 있는지 확인하십시오.그 중 누구라도 발견되면 직원으로 관리자가 있는지 확인하십시오.관리자를 찾을 때마다 여름 비용에 300$를 추가하세요.Jack과의 작업이 끝나면 John과 그의 직원에게 간 다음 Morgan에게 가십시오.

당신은 얼마나 많은 관리자가 있고 얼마나 많은 예산을 지출할 수 있는지 알고 있지만 답변을 얻기 전에 얼마나 많은 주기를 거치게 될지는 결코 알 수 없습니다.

재귀는 각각 부모와 자식이라고 불리는 가지와 잎이 있는 나무입니다.재귀 알고리즘을 사용하면 어느 정도 의식적으로 데이터로부터 트리를 구축하게 됩니다.

Answer 28

일반 영어에서 재귀는 어떤 것을 계속해서 반복하는 것을 의미합니다.

프로그래밍의 한 가지 예는 함수 자체를 호출하는 것입니다.

숫자의 계승을 계산하는 다음 예를 살펴보십시오.

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Answer 29

모든 알고리즘이 표시됩니다. 구조적 기본적으로 데이터 유형의 각 사례에 대한 사례가 있는 스위치 문으로 구성된 경우 데이터 유형에 대한 재귀입니다.

예를 들어, 유형 작업을 할 때

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

구조적 재귀 알고리즘은 다음과 같은 형식을 갖습니다.

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

이것은 실제로 데이터 구조에서 작동하는 알고리즘을 작성하는 가장 확실한 방법입니다.

이제 Peano 공리를 사용하여 정의된 정수(자연수)를 보면

 integer = 0 | succ(integer)

정수에 대한 구조적 재귀 알고리즘은 다음과 같습니다.

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

너무 잘 알려지지 않은 계승 기능은이 형식의 가장 사소한 예에 관한 것입니다.

Answer 30

함수 자체를 호출하거나 자체 정의를 사용합니다.