recursion - 종류 - 재귀함수 파이썬




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

메일 링리스트와 온라인 토론에서 정기적으로 나타나는 주제 중 하나는 컴퓨터 과학 학위를 수행하는 것의 장점 (또는 부족)입니다. 부정적인 당사자에게 계속해서 등장하는 주장은 몇 년 동안 코딩을 해 왔으며 재귀를 사용한 적이 없다는 것입니다.

따라서 질문은 다음과 같습니다.

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

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

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

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

  return a*fact(a-1);
}

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


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.) 사람들은 반복 코드를 작성하는 것이 매우 복잡한 경우에만 재귀를 사용합니다. 예를 들어, 프리오더 (preorder), 포스트 오더 (postorder)와 같은 트리 순회 기술은 반복 및 재귀 둘 다로 만들 수 있습니다. 그러나 일반적으로 단순하기 때문에 재귀를 사용합니다.


글쎄, 그것은 당신이 가진 꽤 괜찮은 정의입니다. 위키 백과도 잘 정의되어 있습니다. 그래서 나는 당신을 위해 또 다른 (아마도 더 나쁜) 정의를 추가 할 것입니다.

사람들이 "재귀"를 언급 할 때, 그들은 일반적으로 그들이 작성한 작업에 대해 반복적으로 호출되는 함수에 대해 이야기하고 있습니다. 재귀는 데이터 구조에서 계층 구조를 탐색 할 때 유용 할 수 있습니다.


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

나는 또한 Steve McConnells가 Code Complete에서의 재귀에 대한 토론을 좋아하는데, 여기서 재귀에 대한 컴퓨터 과학 책에서 사용 된 예를 비판합니다.

계승 또는 피보나치 수에 재귀를 사용하지 마십시오

컴퓨터 과학 교과서의 한 가지 문제점은 재귀의 바보 같은 예를 제시한다는 것입니다. 전형적인 예는 계승을 계산하거나 피보나치 시퀀스를 계산하는 것입니다. 재귀는 강력한 도구이므로 두 경우 모두에 사용하는 것이 멍청합니다. 나를 위해 일한 프로그래머가 재귀를 사용하여 계승을 계산하면 다른 사람을 고용 할 것입니다.

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

편집 : 이것은 Dav의 답변을 발굴하지 않았습니다-나는 이것을 게시했을 때 그 대답을 보지 못했습니다.


다음은 간단한 예입니다. 한 세트에 몇 개의 요소가 있습니까? (물건을 계산하는 더 좋은 방법이 있지만 이것은 좋은 간단한 재귀 예제입니다.)

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

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

[xxx]와 같은 세트가 있다고 가정하십시오. 몇 개의 아이템이 있는지 세어 봅시다.

  1. 세트는 [xxx]이며 비어 있지 않습니다. 따라서 규칙 2를 적용합니다. 항목 수는 [xx]의 항목 수에 1을 더한 것입니다 (즉, 항목을 제거했습니다).
  2. 세트는 [xx]이므로 규칙 2를 다시 적용합니다 : [x]의 항목 + 하나의 수.
  3. 세트는 [x]이며, 규칙 2 : [+]의 1 + 항목 수와 여전히 일치합니다.
  4. 이제 세트는 규칙 1과 일치하는 []입니다. 카운트는 0입니다!
  5. 이제 4 단계 (0)의 답을 알았으므로 3 단계 (1 + 0)를 풀 수 있습니다.
  6. 마찬가지로 3 단계 (1)의 답을 알았으므로 2 단계 (1 + 1)를 풀 수 있습니다.
  7. 마지막으로 2 단계 (2)의 답을 알았으므로 1 단계 (1 + 2)를 풀고 [xxx] (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)

다른 사람들이 다룰 것이라고 확신하는 훨씬 더 유용한 예가 있습니다 (예를 들어 나무를 가로 지르는 것).


모든 알고리즘은 기본적으로 데이터 유형의 각 사례에 대한 스위치 설명으로 구성된 경우 데이터 유형에 대한 구조적 재귀를 나타냅니다.

예를 들어 유형 작업시

  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 axioms를 사용하여 정의 된 정수 (잘, 자연수)를 볼 때

 integer = 0 | succ(integer)

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

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

너무 잘 알려진 계승 함수는이 형태의 가장 간단한 예에 관한 것입니다.


이 스레드에는 recursion 에 대한 여러 가지 좋은 설명이 있습니다.이 답변은 대부분의 언어에서 이것을 사용해서는 안되는 이유에 대한 것입니다. * 대부분의 주요 명령 언어 구현 (예 : C, C ++, Basic, Python의 모든 주요 구현) , Ruby, Java 및 C #) iteration 은 재귀보다 훨씬 선호됩니다.

이유를 확인하려면 위의 언어가 함수를 호출하는 데 사용하는 단계를 수행하십시오.

  1. 함수의 인수와 지역 변수에 대한 공간이 스택 에 새겨집니다.
  2. 함수의 인수는이 새로운 공간으로 복사됩니다
  3. 제어 기능으로 이동
  4. 함수의 코드 실행
  5. 함수의 결과는 반환 값으로 복사됩니다
  6. 스택이 이전 위치로 되감기
  7. 컨트롤은 함수가 호출 된 곳으로 되돌아갑니다.

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

따라서 이러한 언어에서는 재귀 속도가 느리고 충돌에 취약합니다. 그래도 사용에 대한 몇 가지 주장이 있습니다. 일반적으로 코드를 읽는 방법을 알고 나면 재귀 적으로 작성된 코드는 더 짧고 우아합니다.

언어 구현자가 테일 콜 최적화 라고하는 기술을 사용하여 일부 스택 오버플로 클래스를 제거 할 수 있습니다. 간결하게 말하면 함수의 반환 표현식이 단순히 함수 호출의 결과 인 경우 스택에 새 레벨을 추가 할 필요가 없으면 호출중인 함수에 현재 레벨을 재사용 할 수 있습니다. 유감스럽게도 테일 콜 최적화 기능이 내장 된 명령형 언어 구현은 거의 없습니다.

나는 재귀를 좋아한다. 내가 좋아하는 정적 언어 는 루프를 전혀 사용하지 않으며 재귀는 무언가를 반복적으로 수행하는 유일한 방법입니다. 나는 재귀가 튜닝되지 않은 언어에서 일반적으로 좋은 생각이라고 생각하지 않습니다.

** Mario의 ArrangeString 함수의 일반적인 이름은 "join"입니다. 선택한 언어에 아직 구현되어 있지 않은 경우 놀랍습니다.


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

작업에 Java를 사용하고 Java는 중첩 기능을 지원하지 않습니다. 따라서 재귀를 원한다면 외부 함수 (코드가 Java의 관료적 규칙과 충돌하기 때문에 만 존재 함)를 정의해야하거나 코드를 리팩터링해야합니다 (실제로 싫어합니다).

따라서 재귀 자체는 본질적으로 스택 작업이므로 재귀를 피하고 대신 스택 작업을 사용합니다.


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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

재귀에 약간주의해야합니다. 무한 재귀 루프에 들어가면 스택 오버플로 예외가 발생합니다. :)

적절한 경우 사람들이 사용하지 말아야 할 이유를 생각할 수 없습니다. 일부 환경에서는 유용하지만 다른 환경에서는 유용하지 않습니다.

흥미로운 기술이기 때문에 일부 코더는 아마도 정당화하지 않고 원래보다 더 자주 사용한다고 생각합니다. 이것은 일부 서클에서 재귀에 나쁜 이름을 부여했습니다.


재귀 함수는 자체 호출을 포함하는 함수입니다. 재귀 구조체는 자체 인스턴스를 포함하는 구조체입니다. 이 둘을 재귀 클래스로 결합 할 수 있습니다. 재귀 항목의 핵심 부분은 자체 인스턴스 / 호출이 포함되어 있다는 것입니다.

서로 마주 보는 두 개의 거울을 고려하십시오. 우리는 그들이 만드는 무한한 무한대 효과를 보았습니다. 각 반사는 미러의 다른 인스턴스 내에 포함 된 미러의 인스턴스입니다. 자체의 반사를 포함하는 미러는 재귀입니다.

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


재귀는 내가 "프랙탈 문제"라고 부르는 것에서 가장 잘 작동합니다. 여기서 큰 것의 더 작은 버전으로 만들어진 큰 것을 다루고 있습니다. 각각 큰 것의 더 작은 버전입니다. 나무 또는 중첩 된 동일한 구조와 같은 것을 탐색하거나 검색 해야하는 경우 재귀에 적합한 후보가 될 수 있습니다.

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

  1. 대부분의 사람들 (자체 포함)은 기능적 프로그래밍과 달리 절차 적 또는 객체 지향적 프로그래밍에서 프로그래밍 이빨을 자릅니다. 이러한 사람들에게는 반복적 인 접근 방식 (일반적으로 루프 사용)이 더 자연스럽게 느껴집니다.

  2. 절차 적 또는 객체 지향 프로그래밍에서 프로그래밍 톱니를 자르는 사람들은 종종 오류가 발생하기 때문에 재귀를 피하라는 지시를 받았습니다.

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

  4. 내가 사용한 적어도 두 가지 프로그래밍 언어의 경우 스택이 그렇게 깊지 않아 재귀를 사용하지 않는 것이 좋습니다.


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

예를 들어, 숫자 X 대한 계승을 계산하기 위해 X times the factorial of X-1 로 나타낼 수 있습니다. 따라서이 방법은 "재귀"하여 X-1 의 계승을 찾은 다음 X 가 얻은 값을 곱하여 최종 답을 얻습니다. 물론 X-1 의 계승을 찾으려면 먼저 X-2 의 계승 등을 계산합니다. 기본 사례는 X 가 0 또는 1 일 때입니다.이 경우 0! = 1! = 1 부터 1 을 반환하는 것을 알고 있습니다 0! = 1! = 1 0! = 1! = 1 0! = 1! = 1 입니다.


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

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

    return n * Factorial(n - 1);
}

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

간단한 예를 들어 재귀 약어를 고려하십시오.

  • GNUGNU의 유닉스가 아님
  • PHPPHP : Hypertext Preprocessor의 약자
  • YAMLYAML Ai n't Markup Language의 약자
  • 와인와인은 에뮬레이터가 아닙니다
  • VISAVisa International Service Association의 약자입니다.

Wikipedia에 대한 더 많은 예


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


평범한 영어에서 재귀는 반복해서 몇 번의 반복을 의미합니다.

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

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

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

함수 자체를 호출하거나 자체 정의를 사용하십시오.


함수가 자신을 호출하고 루프를 만들 때마다 재귀입니다. 다른 것들과 마찬가지로 재귀에 대한 좋은 사용과 나쁜 사용이 있습니다.

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

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

그러나 이것은보다 효율적인 반복으로 쉽게 대체 할 수 있기 때문에 거의 의미가없는 불충분 한 예입니다. 결국, 재귀는 함수 호출 오버 헤드로 고통받으며, 위의 예에서는 함수 자체 내부의 작업과 비교할 때 상당 할 수 있습니다.

따라서 반복이 아닌 재귀를 수행하는 모든 이유는 호출 스택 을 활용하여 영리한 작업을 수행해야하기 때문입니다. 예를 들어, 동일한 루프 내에서 다른 매개 변수를 사용하여 함수를 여러 번 호출하면 branching 를 수행하는 방법입니다. 전형적인 예는 Sierpinski 삼각형 입니다.

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

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);
    }
}

반복으로 동일한 작업을 시도하면 달성하는 데 더 많은 코드가 필요하다고 생각합니다.

다른 일반적인 사용 사례에는 웹 사이트 크롤러, 디렉토리 비교 등과 같은 트래버스 계층이 포함될 수 있습니다.

결론

실질적인 관점에서, 반복 분기가 필요할 때마다 재귀가 가장 의미가 있습니다.


오래되고 잘 알려진 문제를 고려하십시오.

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

gcd의 정의는 놀랍도록 간단합니다.

여기서 mod는 모듈로 연산자입니다 (즉, 정수 나누기 후 나머지).

영어에서,이 정의는 임의의 숫자와 0의 최대 공약수는 그 숫자 이고 , 두 숫자의 최대 공약수 mnn 의 최대 공약수 이고 mn으로 나눈 후의 나머지입니다.

이것이 왜 작동하는지 알고 싶다면 유클리드 알고리즘 에 관한 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이 아니므로 정의의 두 번째 부분이 적용됩니다. 8이 2의 나머지 2로 한 번 10으로 들어가기 때문에 10 mod 8 = 2입니다. 3 단계에서 두 번째 부분이 다시 적용되지만 이번에는 8이 나머지 8없이 8을 나누기 때문에 8 mod 2 = 0입니다. 5 단계에서 두 번째 인수는 0이므로 답은 2입니다.

등호의 왼쪽과 오른쪽에 gcd가 나타나는 것을 보셨습니까? 수학자는 정의하는 표현식이 정의 내부에서 recurs 되기 때문에이 정의가 재귀 적이라고 말합니다.

재귀 적 정의는 우아합니다. 예를 들어,리스트의 합에 대한 재귀 적 정의는

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과 같이 이러한 모든 정의에 매우 간단한 기본 사례가있는 방법에 주목하십시오. 재귀 사례는 문제를 해결하기 위해 쉽게 대답 할 수 있습니다.

이러한 이해를 통해 이제 위키 백과의 재귀에 관한 기사 에서 다른 알고리즘을 이해할 수 있습니다!


"해머가 있으면 모든 것이 못처럼 보이게한다."

재귀는 매번 같은 망치로 "2 개의 작은 것을 하나의 큰 것으로 바꾸는" 거대한 문제에 대한 문제 해결 전략입니다.

책상에 1024 장의 종이가 엉망이되어 있다고 가정 해 봅시다. 재귀를 사용하여 엉망에서 깔끔하고 깔끔한 종이를 어떻게 만들 수 있습니까?

  1. 나누기 : 모든 시트를 펼치므로 각 "스택"에 하나의 시트 만 있습니다.
  2. 억누르다:
    1. 각 시트를 다른 시트 위에 올려 놓으십시오. 이제 2의 스택이 있습니다.
    2. 각 2 스택을 다른 2 스택 위에 놓으십시오. 이제 스택이 4입니다.
    3. 각 4 스택을 다른 4 스택 위에 놓으십시오. 이제 8의 스택이 있습니다.
    4. ... 계속해서 ...
    5. 이제 1024 매의 거대한 스택이 생겼습니다!

이것은 모든 것을 세는 것 외에는 매우 직관적입니다 (엄격히 필요하지는 않음). 실제로 1 장짜리 스택으로 내려 가지 않을 수도 있지만 실제로는 가능합니다. 중요한 부분은 망치입니다. 팔을 사용하면 항상 하나의 스택을 다른 스택 위에 놓아 더 큰 스택을 만들 수 있으며 (이유 내에서) 두 스택의 크기가 중요하지 않습니다.







computer-science