재귀 또는 반복?
재귀 대신 루프를 사용하거나 둘 다 동일한 목적을 수행 할 수있는 알고리즘에서 루프를 사용하면 성능이 저하됩니까? 예 : 주어진 문자열이 회문인지 확인하십시오. 간단한 반복 알고리즘이 계산서에 적합 할 때 보여주기위한 수단으로 재귀를 사용하는 많은 프로그래머를 보았습니다. 컴파일러는 무엇을 사용해야할지 결정하는 데 중요한 역할을합니까?
재귀 함수가 꼬리 재귀 인지 여부에 따라 재귀가 더 비쌀 수 있습니다 (마지막 줄은 재귀 호출). 테일 재귀 는 컴파일러에 의해 인식되고 반복 대응에 최적화되어야합니다 (코드에서 간결하고 명확한 구현을 유지하면서).
몇 개월 또는 몇 년 동안 코드를 유지해야하는 빈약 한 빨판 (자신 또는 다른 사람)에게 가장 적합한 방식으로 알고리즘을 작성합니다. 성능 문제가 발생하면 코드를 프로파일 링 한 다음 반복 구현으로 이동하여 최적화를 살펴보십시오. 메모 및 동적 프로그래밍 을 살펴볼 수 있습니다 .
루프는 프로그램 성능을 향상시킬 수 있습니다. 재귀는 프로그래머의 성능을 향상시킬 수 있습니다. 귀하의 상황에서 더 중요한 것을 선택하십시오!
재귀를 반복과 비교하는 것은 십자 드라이버를 일자 드라이버와 비교하는 것과 같습니다. 대부분의 경우 평평한 머리를 가진 모든 십자 나사를 제거 할 수 있지만 해당 나 사용으로 설계된 드라이버를 사용하면 더 쉬울까요?
일부 알고리즘은 설계된 방식 (피보나치 시퀀스, 구조와 같은 트리 탐색 등)으로 인해 재귀에 적합합니다. 재귀는 알고리즘을 간결하고 이해하기 쉽게 만듭니다 (따라서 공유 가능하고 재사용 가능).
또한 일부 재귀 알고리즘은 "지연 평가"를 사용하여 반복 형제보다 더 효율적입니다. 즉, 루프가 실행될 때마다 필요한 시간보다 비싼 계산 만 수행합니다.
시작하기에 충분해야합니다. 나는 당신을 위해 몇 가지 기사와 예제를 파헤칠 것입니다.
링크 1 : Haskel vs PHP (재귀 vs 반복)
다음은 프로그래머가 PHP를 사용하여 큰 데이터 세트를 처리해야하는 예입니다. 그는 재귀를 사용하여 Haskel에서 처리하는 것이 얼마나 쉬운지를 보여 주지만 PHP는 동일한 방법을 쉽게 수행 할 수있는 방법이 없기 때문에 반복을 사용하여 결과를 얻었습니다.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
링크 2 : 마스터 링 재귀
재귀의 나쁜 평판은 대부분 명령형 언어의 높은 비용과 비 효율성에서 비롯됩니다. 이 기사의 저자는 재귀 알고리즘을 더 빠르고 효율적으로 최적화하는 방법에 대해 설명합니다. 또한 기존 루프를 재귀 함수로 변환하는 방법과 테일 엔드 재귀 사용의 이점을 설명합니다. 그의 마지막 말은 실제로 내가 생각하는 핵심 요점 중 일부를 요약했습니다.
"재귀 프로그래밍은 프로그래머가 유지 관리 가능하고 논리적으로 일관된 방식으로 코드를 구성하는 더 나은 방법을 제공합니다."
링크 3 : 재귀가 루핑보다 훨씬 빠릅니까? (대답)
다음은 귀하와 유사한 stackoverflow 질문에 대한 답변 링크입니다. 저자는 되풀이 또는 반복과 관련된 많은 벤치 마크가 언어 마다 매우 다르다고 지적합니다 . 명령형 언어는 일반적으로 루프를 사용하여 더 빠르며 재귀를 사용하면 속도가 느리고 그 반대도 기능적 언어입니다. 이 링크에서 취해야 할 요점은 언어에 구애받지 않고 상황 맹목적으로 질문에 대답하기가 매우 어렵다는 것입니다.
각 재귀 호출은 일반적으로 메모리 주소를 스택으로 푸시해야하므로 나중에 재귀가 메모리에서 비용이 많이 들기 때문에 나중에 프로그램이 해당 지점으로 돌아갈 수 있습니다.
그럼에도 불구하고 재귀가 루프보다 훨씬 자연스럽고 읽기 쉬운 경우가 많이 있습니다. 이 경우 재귀를 고수하는 것이 좋습니다.
일반적으로 성능 저하가 다른 방향으로 나타날 것으로 예상합니다. 재귀 호출은 추가 스택 프레임을 구성 할 수 있습니다. 이에 대한 형벌은 다양합니다. 또한 Python과 같은 일부 언어 (보다 정확하게는 일부 언어의 일부 구현에서는 ...)에서 트리 데이터 구조에서 최대 값을 찾는 것과 같이 재귀 적으로 지정할 수있는 작업에 대해 스택 제한을 쉽게 실행할 수 있습니다. 이 경우 루프를 고수하려고합니다.
좋은 재귀 함수를 작성하면 테일 재귀 등을 최적화하는 컴파일러가 있다고 가정 할 때 성능 저하가 다소 줄어들 수 있습니다. 또한 함수가 실제로 테일 재귀인지 확인하기 위해 두 번 확인하십시오. 많은 사람들이 실수하는 것 중 하나입니다 의 위에.)
"가장자리"사례 (고성능 컴퓨팅, 매우 큰 재귀 깊이 등) 외에도 의도를 가장 명확하게 표현하고 설계가 잘되어 있으며 유지 관리가 가능한 접근 방식을 채택하는 것이 좋습니다. 요구를 파악한 후에 만 최적화하십시오.
재귀는 여러 개의 작은 조각 으로 나눌 수있는 문제에 대해 반복보다 낫습니다 .
예를 들어 재귀 피보나치 알고리즘을 만들려면 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)이 두 번 계산됩니다!
더 좋은 예는 트리의 재귀 알고리즘입니다. 부모 노드를 분석하는 문제는 각 자식 노드를 분석하는 여러 가지 작은 문제 로 나눌 수 있습니다 . 피보나치 예제와 달리 작은 문제는 서로 독립적입니다.
예, 재귀는 여러 개의 작고 독립적이며 유사한 문제로 나눌 수있는 문제에 대해 반복보다 낫습니다.
어떤 언어로든 메소드를 호출하면 많은 준비가 필요하기 때문에 재귀를 사용할 때 성능이 저하됩니다. 호출 코드는 리턴 주소, 호출 매개 변수, 프로세서 레지스터와 같은 기타 컨텍스트 정보가 어딘가에 저장 될 수 있으며 리턴 시간에 호출 된 메소드는 리턴 값을 게시 한 다음 호출자가 검색하며 이전에 저장된 컨텍스트 정보가 복원됩니다. 반복적 접근과 재귀 적 접근 사이의 성능 차이는 이러한 작업에 걸리는 시간에 있습니다.
구현 관점에서 호출 컨텍스트를 처리하는 데 걸리는 시간이 메소드를 실행하는 데 걸리는 시간과 비교할 때 차이를 인식하기 시작합니다. 재귀 적 메서드가 호출 컨텍스트 관리 부분을 실행하는 데 시간이 오래 걸리면 코드를 일반적으로 더 읽기 쉽고 이해하기 쉽고 재귀 적 방식으로 수행하므로 성능 손실을 알 수 없습니다. 그렇지 않으면 효율성상의 이유로 반복적으로 진행하십시오.
Java의 꼬리 재귀가 현재 최적화되어 있지 않다고 생각합니다. 자세한 내용은 LtU 및 관련 링크에 대한 이 토론 전체에 뿌려 집니다. 그것은 수 다가오는 버전 7의 기능,하지만 분명히 특정 프레임이 누락 될 수 있기 때문에 스택 검사와 함께 특정 어려움을 선물한다. 스택 검사는 Java 2부터 세밀한 보안 모델을 구현하는 데 사용되었습니다.
http://lambda-the-ultimate.org/node/1333
이진 트리를 순회하는 일반적인 예인 반복 방법에 비해 훨씬 더 우아한 솔루션을 제공하는 경우가 많으므로 유지 관리가 더 어려울 필요는 없습니다. 일반적으로 반복 버전은 일반적으로 약간 빠르며 (최적화 중에 재귀 버전을 대체 할 수 있음) 재귀 버전은 이해하고 올바르게 구현하기가 더 간단합니다.
재귀는 일부 상황에서 매우 유용합니다. 예를 들어 계승을 구하는 코드를 고려하십시오.
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)코드가 얼마 동안 실행되고 일반적으로 스택 오버플로로 끝납니다.
대부분의 경우 캐싱으로 인해 재귀가 빨라져 성능이 향상됩니다. 예를 들어, 다음은 전통적인 병합 루틴을 사용하는 반복 버전의 병합 정렬입니다. 캐싱 성능 향상으로 인해 재귀 구현보다 느리게 실행됩니다.
반복 구현
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);
}
추신-이것은 코스 라에 제시된 알고리즘에 대한 과정에서 케빈 웨인 교수 (프린스턴 대학교)에 의해 알려졌습니다.
재귀를 사용하면 각 "반복"마다 함수 호출 비용이 발생하지만 루프에서는 일반적으로 지불하는 것이 증가 / 감소뿐입니다. 따라서 루프 코드가 재귀 솔루션 코드보다 훨씬 복잡하지 않은 경우 일반적으로 루프가 재귀보다 우수합니다.
재귀와 반복은 구현하려는 비즈니스 로직에 따라 다르지만 대부분의 경우 상호 교환하여 사용할 수 있습니다. 대부분의 개발자는 이해하기 쉽기 때문에 재귀를 찾습니다.
언어에 따라 다릅니다. Java에서는 루프를 사용해야합니다. 기능적 언어는 재귀를 최적화합니다.
목록을 반복하는 중이라면 반복하십시오.
다른 몇 가지 대답은 (심도 우선) 나무 통과를 언급했습니다. 매우 일반적인 데이터 구조에 대해 수행하는 것이 매우 일반적이기 때문에 정말 훌륭한 예입니다. 재귀는이 문제에 대해 매우 직관적입니다.
여기서 "찾기"방법을 확인하십시오. http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
재귀는 반복의 가능한 정의보다 더 단순하고 따라서 더 근본적입니다. 콤비 네이터 쌍 만으로 Turing-complete 시스템을 정의 할 수 있습니다 (예, 재귀 자체도 그러한 시스템의 파생 개념 임). Lambda 미적분학은 재귀 함수를 특징으로하는 강력한 기본 시스템입니다. 그러나 반복을 올바르게 정의하려면 시작하기 위해 훨씬 더 많은 프리미티브가 필요합니다.
코드에 관해서는, 대부분의 데이터 구조는 재귀 적이므로 재귀 코드는 순전히 반복적 인 코드보다 이해하고 유지하기가 훨씬 쉽습니다. 물론, 그것을 올바르게 얻으려면 최소한 모든 표준 결합기와 반복자를 깔끔하게 얻으려면 고차 함수와 클로저를 지원하는 언어가 필요합니다. 물론 C ++에서는 FC ++ 의 하드 코어 사용자가 아니라면 복잡한 재귀 솔루션이 약간 추한 것처럼 보일 수 있습니다 .
나는 (비 꼬리) 재귀에서 함수가 호출 될 때마다 (물론 언어에 따라) 새 스택 등을 할당하면 성능이 저하 될 것이라고 생각합니다.
"재귀 깊이"에 따라 다릅니다. 함수 호출 오버 헤드가 총 실행 시간에 얼마나 영향을 미치는지에 달려 있습니다.
예를 들어, 재귀 방식으로 고전적 계승을 계산하는 것은 다음과 같은 이유로 매우 비효율적입니다.-데이터 오버플로 위험-스택 오버플로 위험-함수 호출 오버 헤드가 실행 시간의 80 %를 차지함
후속 N 이동을 분석 할 체스 게임에서 위치 분석을위한 최소-최대 알고리즘을 개발하는 동안 "분석 깊이"에 대한 재귀로 구현할 수 있습니다 (^_^)
재귀? Wiki는 어디서부터 시작합니까?“자기 비슷한 방식으로 항목을 반복하는 과정입니다”
내가 C를하고 있었을 때, C ++ 재귀는 "Tail recursion"과 같은 신이 보낸 것이 었습니다. 또한 재귀를 사용하는 많은 정렬 알고리즘을 찾을 수 있습니다. 빠른 정렬 예 : http://alienryderflex.com/quicksort/
재귀는 특정 문제에 유용한 다른 알고리즘과 같습니다. 아마도 당신은 곧바로 또는 자주 사용하지 않을 수도 있지만 사용 가능한 것이 기쁠 것입니다.
C ++에서 재귀 함수가 템플릿 함수 인 경우 모든 유형 공제 및 함수 인스턴스화가 컴파일 시간에 발생하므로 컴파일러는이를 최적화 할 수 있습니다. 최신 컴파일러는 가능한 경우 함수를 인라인 할 수도 있습니다. 따라서 -O3또는 -O2in 과 같은 최적화 플래그를 사용하면 g++재귀가 반복보다 빠를 수 있습니다. 반복 코드에서는 컴파일러가 이미 최적의 상태 (충분히 작성된 경우)에 있으므로 최적화 할 기회가 줄어 듭니다.
필자의 경우, Armadillo 행렬 객체를 재귀 및 반복 방식으로 제곱하여 행렬 지수를 구현하려고했습니다. 알고리즘은 https://en.wikipedia.org/wiki/Exponentiation_by_squaring 에서 찾을 수 있습니다 . 내 함수는 템플릿이었고 나는 1,000,000 12x12거듭 제곱 행렬 을 계산했습니다 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을 사용하여 얻었습니다. 인텔 컴파일러도 비슷한 결과를 보여줍니다.
마이크가 맞습니다. 테일 재귀는 Java 컴파일러 또는 JVM에 의해 최적화 되지 않습니다 . 항상 다음과 같은 스택 오버플로가 발생합니다.
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
너무 깊은 재귀를 사용하면 허용되는 스택 크기에 따라 스택 오버플로가 발생한다는 점을 명심해야합니다. 이를 방지하려면 재귀를 끝내는 기본 사례를 제공하십시오.
재귀는 재귀를 사용하여 작성하는 알고리즘에 O (n) 공간 복잡성이 있다는 단점이 있습니다. 반복적 인 aproach는 O (1)의 공간 복잡성을 가지지 만, 이것은 재귀에 대한 반복을 사용하는 이점입니다. 그렇다면 왜 재귀를 사용합니까?
아래를 참조하십시오.
때로는 반복을 사용하여 알고리즘을 작성하는 것이 더 쉬운 반면 반복을 사용하여 동일한 알고리즘을 작성하는 것이 약간 더 어려울 수 있습니다.이 경우 반복 접근 방식을 선택하면 스택을 직접 처리해야합니다.
내가 아는 한 Perl은 꼬리 재귀 호출을 최적화하지는 않지만 가짜로 만들 수 있습니다.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
처음 호출되면 스택에 공간을 할당합니다. 그런 다음 인수를 변경하고 스택에 더 이상 아무것도 추가하지 않고 서브 루틴을 다시 시작합니다. 그러므로 그것은 결코 자기 자신을 부르지 않은 것처럼 가장하여 반복적 인 과정으로 바꾼다.
" my @_;"또는 " local @_;"가 없으면 더 이상 작동하지 않습니다.
Chrome 45.0.2454.85m 만 사용하면 재귀가 훨씬 빠릅니다.
코드는 다음과 같습니다.
(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 회 실행
루프 실행을위한 100x. 완료 시간 : 7.683ms
// 꼬리 재귀와 함께 기능 재귀 접근 방식을 사용하여 100 회 실행
100x 재귀 실행. 완료 시간 : 4.841ms
아래 스크린 샷에서 테스트 당 300 사이클로 실행하면 재귀가 더 큰 마진으로 다시 승리합니다.
If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them, then a recursive approach could yield a huge performance boost when combined with multithreading. If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system.
For example, in some languages, there are recursive multithreaded merge sort implementations.
But again, multithreading can be used with looping rather than recursion, so how well this combination will work depends on more factors including the OS and its thread allocation mechanism.
I'm going to answer your question by designing a Haskell data structure by "induction", which is a sort of "dual" to recursion. And then I will show how this duality leads to nice things.
We introduce a type for a simple tree:
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
We can read this definition as saying "A tree is a Branch (which contains two trees) or is a leaf (which contains a data value)". So the leaf is a sort of minimal case. If a tree isn't a leaf, then it must be a compound tree containing two trees. These are the only cases.
Let's make a tree:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
Now, let's suppose we want to add 1 to each value in the tree. We can do this by calling:
addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a) = Leaf (a + 1)
First, notice that this is in fact a recursive definition. It takes the data constructors Branch and Leaf as cases (and since Leaf is minimal and these are the only possible cases), we are sure that the function will terminate.
What would it take to write addOne in an iterative style? What will looping into an arbitrary number of branches look like?
Also, this kind of recursion can often be factored out, in terms of a "functor". We can make Trees into Functors by defining:
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
and defining:
addOne' = fmap (+1)
We can factor out other recursion schemes, such as the catamorphism (or fold) for an algebraic data type. Using a catamorphism, we can write:
addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b
Stack overflow will only occur if you're programming in a language that doesn't have in built memory management.... Otherwise, make sure you have something in your function (or a function call, STDLbs, etc). Without recursion it would simply not be possible to have things like... Google or SQL, or any place one must efficiently sort through large data structures (classes) or databases.
Recursion is the way to go if you want to iterate through files, pretty sure that's how 'find * | ?grep *' works. Kinda dual recursion, especially with the pipe (but don't do a bunch of syscalls like so many like to do if it's anything you're going to put out there for others to use).
Higher level languages and even clang/cpp may implement it the same in the background.
참고 URL : https://stackoverflow.com/questions/72209/recursion-or-iteration
'Programing' 카테고리의 다른 글
| 절대 파일 경로를 포함하는 문자열에서 파일 이름을 어떻게 얻습니까? (0) | 2020.04.29 |
|---|---|
| 프로세스가 종료되면 프로세스를 다시 시작하기 위해 bash 스크립트를 작성하는 방법 (0) | 2020.04.29 |
| 기본 FirebaseApp이 초기화되지 않았습니다 (0) | 2020.04.29 |
| 정기적으로 어떤 Xcode 키보드 단축키를 사용하십니까? (0) | 2020.04.29 |
| DROP 데이터베이스 권한없이 명령 행에서 모든 MySQL 테이블을 제거하는 방법은 무엇입니까? (0) | 2020.04.29 |