it-swarm-ko.tech

재귀 또는 반복?

재귀 대신 루프를 사용하거나 둘 다 동일한 목적을 수행 할 수있는 알고리즘에서 루프를 사용하면 성능이 저하됩니까? 예 : 주어진 문자열이 회문인지 확인하십시오. 간단한 반복 알고리즘이 법안에 맞는지 보여주기위한 수단으로 재귀를 사용하는 많은 프로그래머를 보았습니다. 컴파일러는 무엇을 사용해야할지 결정하는 데 중요한 역할을합니까?

210
Omnipotent

재귀 함수가 tail recursive (마지막 줄은 재귀 호출)인지에 따라 재귀가 더 비쌀 수 있습니다. 테일 재귀 should 컴파일러가 인식하고 반복 대응에 최적화됩니다 (코드에서 간결하고 명확한 구현을 유지하면서).

몇 개월 또는 몇 년 동안 코드를 유지해야하는 빈약 한 빨판 (자신 또는 다른 사람)에게 가장 적합한 방식으로 알고리즘을 작성합니다. 성능 문제가 발생하면 코드를 프로파일 링 한 다음 반복 구현으로 이동하여 최적화를 살펴보십시오. memoizationdynamic programming 을 살펴볼 수 있습니다.

176
Paul Osborne

루프는 프로그램 성능을 향상시킬 수 있습니다. 재귀는 프로그래머의 성능을 향상시킬 수 있습니다. 귀하의 상황에서 더 중요한 것을 선택하십시오!

309
Leigh Caldwell

재귀를 반복과 비교하는 것은 십자 드라이버를 일자 드라이버와 비교하는 것과 같습니다. 대부분의 경우 could 평평한 머리로 모든 십자 나사를 제거하지만 해당 나 사용으로 설계된 드라이버를 사용하면 더 쉬울까요?

일부 알고리즘은 설계된 방식 (피보나치 시퀀스, 구조와 같은 트리 탐색 등)으로 인해 재귀에 적합합니다. 재귀는 알고리즘을 간결하고 이해하기 쉽게 만듭니다 (따라서 공유 가능하고 재사용 가능).

또한 일부 재귀 알고리즘은 "지연 평가"를 사용하여 반복 형제보다 더 효율적입니다. 즉, 루프가 실행될 때마다 필요한 시간에 비싼 계산 만 수행합니다.

시작하기에 충분해야합니다. 나는 당신을 위해 몇 가지 기사와 예제를 파헤칠 것이다.

링크 1 : 하스켈 vs PHP (재귀 vs 반복)

다음은 프로그래머가 PHP를 사용하여 큰 데이터 세트를 처리해야하는 예입니다. 그는 재귀를 사용하여 Haskel에서 처리하는 것이 얼마나 쉬운 지 보여 주지만 PHP는 같은 방법을 수행하는 쉬운 방법이 없었으므로 반복을 사용하여 결과를 얻었습니다.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

링크 2 : 마스터 링 재귀

재귀의 나쁜 평판은 대부분 명령형 언어의 높은 비용과 비 효율성에서 비롯됩니다. 이 기사의 저자는 재귀 알고리즘을 더 빠르고 효율적으로 최적화하는 방법에 대해 설명합니다. 또한 기존 루프를 재귀 함수로 변환하는 방법과 테일 엔드 재귀 사용의 이점을 설명합니다. 그의 마지막 말은 실제로 내가 생각하는 핵심 요점 중 일부를 요약했습니다.

"재귀 프로그래밍은 프로그래머가 유지 관리 가능하고 논리적으로 일관된 방식으로 코드를 구성하는 더 나은 방법을 제공합니다."

https://developer.ibm.com/articles/l-recurs/

링크 3 : 재귀가 루핑보다 훨씬 빠릅니까? (답)

다음은 귀하와 유사한 stackoverflow 질문에 대한 답변 링크입니다. 저자는 되풀이 또는 반복과 관련된 많은 벤치 마크가 매우 언어마다 다르다고 지적합니다. 명령형 언어는 일반적으로 루프를 사용하여 더 빠르며 재귀를 사용하면 속도가 느리고 그 반대는 기능적 언어입니다. 이 링크에서 취해야 할 요점은 언어에 구애받지 않고 상황 맹목적으로 질문에 대답하기가 매우 어렵다는 것입니다.

루핑보다 재귀가 더 빠릅니까?

76
Swift

각 재귀 호출은 일반적으로 메모리 주소를 스택으로 푸시해야하므로 나중에 재귀가 메모리에서 비용이 많이 들기 때문에 나중에 프로그램이 해당 지점으로 돌아갈 수 있습니다.

그럼에도 불구하고 재귀가 루프보다 훨씬 자연스럽고 읽기 쉬운 경우가 많이 있습니다. 이 경우 재귀를 고수하는 것이 좋습니다.

16
Doron Yaacoby

일반적으로 성능 저하가 다른 방향으로 나타날 것으로 예상합니다. 재귀 호출은 추가 스택 프레임을 구성 할 수 있습니다. 이에 대한 형벌은 다양하다. 또한 Python과 같은 일부 언어 (보다 정확하게는 일부 언어의 일부 구현에서는 ...)에서 최대 값 찾기와 같이 재귀 적으로 지정할 수있는 작업에 대해 스택 제한을 쉽게 실행할 수 있습니다. 트리 데이터 구조. 이 경우 루프를 고수하려고합니다.

좋은 재귀 함수를 작성하면 테일 재귀 등을 최적화하는 컴파일러가 있다고 가정 할 때 성능 저하가 다소 줄어들 수 있습니다. 또한 함수가 실제로 테일 재귀인지 확인하십시오. 많은 사람들이 실수하는 것 중 하나입니다 의 위에.)

"에지"사례 (고성능 컴퓨팅, 매우 큰 재귀 깊이 등) 외에도 의도를 가장 명확하게 표현하고 잘 설계되고 유지 관리 할 수있는 접근 방식을 채택하는 것이 좋습니다. 요구를 파악한 후에 만 ​​최적화하십시오.

11
zweiterlinde

재귀는 작은 조각으로 multiple으로 나눌 수있는 문제에 대해 반복보다 낫습니다.

예를 들어 재귀 피보나치 알고리즘을 만들려면 fib (n)을 fib (n-1) 및 fib (n-2)로 나누고 두 부분을 모두 계산합니다. 반복을 통해 단일 기능을 반복해서 반복 할 수 있습니다.

그러나 피보나치는 실제로 깨진 예이며 반복이 실제로 더 효율적이라고 생각합니다. fib (n) = fib (n-1) + fib (n-2) 및 fib (n-1) = fib (n-2) + fib (n-3)에 유의하십시오. fib (n-1)이 두 번 계산됩니다!

더 좋은 예는 트리의 재귀 알고리즘입니다. 부모 노드를 분석하는 문제는 multiple 각 자식 노드를 분석하는 작은 문제로 나눌 수 있습니다. 피보나치 예제와 달리 작은 문제는 서로 독립적입니다.

예, 재귀는 여러 개의 작고 독립적이며 유사한 문제로 나눌 수있는 문제에 대해 반복보다 낫습니다.

8
Ben

어떤 언어로든 메소드를 호출하면 많은 준비가 필요하기 때문에 재귀를 사용할 때 성능이 저하됩니다. 호출 코드는 리턴 주소, 호출 매개 변수, 프로세서 레지스터와 같은 기타 컨텍스트 정보가 어딘가에 저장 될 수 있으며 리턴 시간에 호출 된 메소드는 리턴 값을 게시 한 다음 호출자가 검색하며 이전에 저장된 컨텍스트 정보가 복원됩니다. 반복적 접근과 재귀 적 접근 사이의 성능 차이는 이러한 작업에 걸리는 시간에 있습니다.

구현 관점에서, 호출 컨텍스트를 처리하는 데 걸리는 시간이 메소드를 실행하는 데 걸리는 시간과 비교할 때 차이를 인식하기 시작합니다. 재귀 적 메서드가 호출 컨텍스트 관리 부분을 실행하는 데 시간이 오래 걸리면 코드를 일반적으로 더 읽기 쉽고 이해하기 쉽고 재귀 적 방식으로 수행하므로 성능 손실을 알 수 없습니다. 그렇지 않으면 효율성상의 이유로 반복적으로 진행하십시오.

7
entzik

Java의 꼬리 재귀가 현재 최적화되어 있지 않다고 생각합니다. 자세한 내용은 LtU 및 관련 링크에 대한 this 토론 전체에 뿌려집니다. 는 다음 버전 7의 기능 일 수 있지만 특정 프레임이 누락되어 스택 검사와 결합 할 때 특정 어려움이있는 것으로 보입니다. 스택 검사는 Java 2 이후로 세분화 된 보안 모델을 구현하는 데 사용되었습니다.

http://lambda-the-ultimate.org/node/13

6
Mike Edwards

대부분의 경우 캐싱으로 인해 재귀가 빨라져 성능이 향상됩니다. 예를 들어, 다음은 전통적인 병합 루틴을 사용하는 반복 정렬 버전입니다. 캐싱 성능 향상으로 인해 재귀 구현보다 느리게 실행됩니다.

반복 구현

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

재귀 적 구현

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

추신-이것은 코스 프레에 제시된 알고리즘에 대한 과정에서 케빈 웨인 교수 (프린스턴 대학교)가 들었던 것입니다.

5
Nikunj Banka

이진 트리를 순회하는 일반적인 예인 반복 방법에 비해 훨씬 더 우아한 솔루션을 제공하는 경우가 많으므로 유지 관리가 더 어려울 필요는 없습니다. 일반적으로 반복 버전은 일반적으로 약간 빠르며 (최적화 중에 재귀 버전을 대체 할 수 있음) 재귀 버전은 이해하고 올바르게 구현하기가 더 간단합니다.

5
Felix

재귀는 일부 상황에서 매우 유용합니다. 예를 들어 계승을 구하는 코드를 고려하십시오.

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

이제 재귀 함수를 사용하여 고려하십시오.

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

이 두 가지를 관찰하면 재귀를 이해하기 쉽다는 것을 알 수 있습니다. 그러나주의해서 사용하지 않으면 오류가 발생하기 쉽습니다. if (input == 0)을 놓치면 코드가 얼마 동안 실행되어 일반적으로 스택 오버플로로 끝납니다.

5
Harikrishnan

언어에 따라 다릅니다. Java에서는 루프를 사용해야합니다. 기능적 언어는 재귀를 최적화합니다.

4
mc

재귀를 사용하면 각 "반복"마다 함수 호출 비용이 발생하지만 루프에서는 일반적으로 지불하는 것이 증가/감소뿐입니다. 따라서 루프 코드가 재귀 솔루션 코드보다 훨씬 복잡하지 않은 경우 일반적으로 루프가 재귀보다 우수합니다.

4
MovEaxEsp

재귀와 반복은 구현하려는 비즈니스 로직에 따라 다르지만 대부분의 경우 상호 교환하여 사용할 수 있습니다. 대부분의 개발자는 이해하기 쉽기 때문에 재귀를 찾습니다.

4
Warrior

재귀는 반복의 가능한 정의보다 더 간단하고 따라서 더 근본적입니다. 콤비 네이터 쌍 만으로 Turing-complete 시스템을 정의 할 수 있습니다 (예, 재귀 자체도 그러한 시스템의 파생 개념 임). Lambda 미적분은 재귀 함수를 특징으로하는 똑같이 강력한 기본 시스템입니다. 그러나 반복을 올바르게 정의하려면 시작하기 위해 훨씬 더 많은 프리미티브가 필요합니다.

코드에 관해서는, 대부분의 데이터 구조는 재귀 적이므로 재귀 코드는 순전히 반복적 인 코드보다 이해하고 유지하기가 훨씬 쉽습니다. 물론, 그것을 올바르게 얻으려면 최소한 모든 표준 결합기와 반복자를 깔끔하게 얻으려면 고차 함수와 클로저를 지원하는 언어가 필요합니다. 물론 C++에서 하드 코어 사용자가 FC++ 이상이 아닌 한 복잡한 재귀 솔루션은 약간 추악하게 보일 수 있습니다.

3
SK-logic

목록을 반복하는 중이라면 반복하십시오.

다른 몇 가지 답변은 (심도 우선) 트리 탐색을 언급했습니다. 매우 일반적인 데이터 구조에 대해 수행하는 것이 매우 일반적이기 때문에 정말 훌륭한 예입니다. 재귀는이 문제에 대해 매우 직관적입니다.

여기서 "찾기"방법을 확인하십시오. http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

3
Joe Cheng

나는 (비 꼬리) 재귀에서 함수가 호출 될 때마다 (물론 언어에 따라) 새 스택 등을 할당하면 성능이 저하 될 것이라고 생각합니다.

2
metadave

C++에서 재귀 함수가 템플릿 함수 인 경우 모든 유형 공제 및 함수 인스턴스화가 컴파일 시간에 발생하므로 컴파일러는이를 최적화 할 기회가 더 많습니다. 최신 컴파일러는 가능한 경우 함수를 인라인 할 수도 있습니다. 따라서 -O3에서 -O2 또는 g++와 같은 최적화 플래그를 사용하는 경우 재귀가 반복보다 빠를 수 있습니다. 반복 코드에서는 컴파일러가 이미 최적 상태 (충분히 작성된 경우)에 있으므로 최적화 할 기회가 줄어 듭니다.

필자의 경우 Armadillo 행렬 객체를 재귀 및 반복 방식으로 제곱하여 행렬 지수를 구현하려고했습니다. 알고리즘은 여기에서 찾을 수 있습니다 ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . 내 함수가 템플릿 화되었고 1,000,00012x12 거듭 제곱 10로 계산 된 행렬을 계산했습니다. 나는 다음과 같은 결과를 얻었다 :

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

이 결과는 c ++ 11 플래그 (-std=c++11)가있는 gcc-4.8 및 Intel mkl이있는 Armadillo 6.1을 사용하여 얻은 것입니다. 인텔 컴파일러도 비슷한 결과를 보여줍니다.

2
Titas Chanda

재귀? Wiki는 어디서부터 시작합니까?“자기 비슷한 방식으로 항목을 반복하는 과정입니다”

내가 C를하고 있었을 때, C++ 재귀는 "Tail recursion"과 같은 신이 보낸 것이 었습니다. 또한 많은 정렬 알고리즘에서 재귀를 사용합니다. 빠른 정렬 예 : http://alienryderflex.com/quicksort/

재귀는 특정 문제에 유용한 다른 알고리즘과 같습니다. 아마도 당신은 곧바로 또는 자주 사용을 찾지 못할 수도 있지만 사용 가능한 것이 기쁘다는 문제가있을 것입니다.

2
Nickz

"재귀 깊이"에 따라 다릅니다. 함수 호출 오버 헤드가 총 실행 시간에 얼마나 영향을 미치는지에 달려 있습니다.

예를 들어, 재귀 방식으로 클래식 계승을 계산하는 것은 다음과 같은 이유로 매우 비효율적입니다.-데이터 오버플로 위험-스택 오버플로 위험-함수 호출 오버 헤드가 실행 시간의 80 %를 차지함

후속 N 이동을 분석 할 체스 게임에서 위치 분석을위한 최소-최대 알고리즘을 개발하는 동안 "분석 깊이"에 대한 재귀로 구현할 수 있습니다 (^_^)

2
ugasoft

마이크가 맞습니다. 테일 재귀는 not Java 컴파일러 또는 JVM에 의해 최적화됩니다. 항상 다음과 같은 스택 오버플로가 발생합니다.

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}
1
noah

재귀는 재귀를 사용하여 작성하는 알고리즘에 O(n) 공간 복잡성이 있다는 단점이 있습니다. 반복적 인 aproach는 O (1)의 공간 복잡성을 가지지 만, 이것은 재귀에 대한 반복을 사용하는 이점입니다. 그렇다면 왜 재귀를 사용합니까?

아래를 참조하십시오.

반복을 사용하여 알고리즘을 작성하는 것이 더 쉬운 반면 반복을 사용하여 동일한 알고리즘을 작성하는 것이 약간 더 어려운 경우가 있습니다.

1

너무 깊은 재귀를 사용하면 허용되는 스택 크기에 따라 스택 오버플로가 발생한다는 점을 명심해야합니다. 이를 방지하려면 재귀를 끝내는 기본 사례를 제공하십시오.

1
Grigori A.

내가 아는 한 Perl은 꼬리 재귀 호출을 최적화하지는 않지만 가짜로 만들 수 있습니다.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

처음 호출되면 스택에 공간을 할당합니다. 그런 다음 인수를 변경하고 스택에 더 이상 아무것도 추가하지 않고 서브 루틴을 다시 시작합니다. 그러므로 그것은 결코 자기 자신을 부르지 않은 것처럼 가장하여 반복적 인 과정으로 바꾼다.

더 이상 작동하지 않으면 "my @_;"또는 "local @_;"가 없습니다.

0
Brad Gilbert

반복이 원자 적이며 새로운 스택 프레임을 밀어내는 것보다 훨씬 비싸면 and 새 스레드를 만드는 것 and 여러 코어가 있습니다 and 런타임 환경은 이들 모두를 사용할 수 있으므로 재귀 접근 방식은 멀티 스레딩과 결합 할 때 성능을 크게 향상시킬 수 있습니다. 평균 반복 횟수를 예측할 수없는 경우 스레드 할당을 제어하고 프로세스가 너무 많은 스레드를 작성하고 시스템을 호깅하지 못하게하는 스레드 풀을 사용하는 것이 좋습니다.

예를 들어, 일부 언어에는 재귀 멀티 스레드 병합 정렬 구현이 있습니다.

그러나 다시 멀티 스레딩을 재귀가 아닌 루핑과 함께 사용할 수 있으므로이 조합의 작동 방식은 OS 및 스레드 할당 메커니즘을 비롯한 더 많은 요소에 따라 다릅니다.

0
ccpizza

Chrome 45.0.2454.85 m 만 사용하면 재귀가 더 빠른 속도로 보입니다.

코드는 다음과 같습니다.

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

결과

// 표준 for 루프를 사용하여 100 회 실행

루프 실행 100 배. 완료 시간 : 7.683ms

// 꼬리 재귀와 함께 기능 재귀 접근법을 사용하여 100 회 실행

100x 재귀 실행. 완료 시간 : 4.841ms

아래 스크린 샷에서 테스트 당 300 사이클로 실행하면 재귀가 더 큰 마진으로 다시 승리합니다

Recursion wins again!

0
Alpha G33k