반복보다 재귀를 선호해야하는 이유는 무엇입니까?
반복은 재귀보다 성능이 더 좋습니다. 그렇다면 왜 일부 사람들은 반복이 반복보다 재귀가 더 낫다고 생각합니까? Haskell과 같은 일부 언어가 반복을 허용하지 않고 재귀를 권장하는 이유를 알 수 없습니다. 성능이 좋지 않은 것을 장려하는 것은 터무니없는 일이 아닌가? 이것에 대해 약간의 빛을 비춰주세요. 감사.
반복은 재귀보다 성능이 더 좋습니다.
반드시 그런 것은 아닙니다. 이 개념은 재귀 적이든 아니든 함수를 호출 할 때 많은 오버 헤드가 발생하고 모든 호출에 대해 새로운 스택 프레임을 생성하는 C와 유사한 많은 언어에서 비롯되었습니다.
많은 언어의 경우 그렇지 않으며 재귀는 반복 버전과 동일하거나 더 성능이 좋습니다. 요즘 일부 C 컴파일러조차도 일부 재귀 구조를 반복 버전으로 다시 작성하거나 꼬리 재귀 호출에 스택 프레임을 재사용합니다.
깊이 우선 검색을 재귀적이고 반복적으로 구현하고 어느 것이 더 쉬운 시간을 제공했는지 알려주십시오. 또는 병합 정렬. 많은 문제의 경우 자신의 스택을 명시 적으로 유지하는 것이 아니라 데이터를 함수 스택에 남겨 두는 것입니다.
나는 그것을 사용한 적이 없기 때문에 Haskell과 말할 수는 없지만 이것은 당신의 제목에 제기 된 질문의 더 일반적인 부분을 다루기위한 것입니다.
Haskell은 반복이 변경 가능한 상태 (인덱스)를 포함하므로 반복을 허용하지 않습니다.
다른 사람들이 말했듯이 재귀에 대해 본질적으로 성능이 떨어지는 것은 없습니다. 속도가 느려지는 언어가 있지만 보편적 인 규칙은 아닙니다.
즉, 나에게 재귀는 그것이 합리적 일 때 사용되는 도구입니다. 재귀로 더 잘 표현되는 알고리즘이 있습니다 (일부는 반복을 통해 더 나은 것처럼).
지목 사항:
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
나는 그것보다 의도를 더 명확하게 만들 수있는 반복적 인 해결책을 상상할 수 없다.
다음은 c에서 재귀 및 반복의 장단점에 대한 정보입니다.
http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html
대부분 재귀는 반복보다 이해하기가 더 쉽습니다.
반복은 단지 특별한 형태의 재귀입니다.
몇 가지 :
- 반복이 반드시 더 빠른 것은 아닙니다.
- 모든 악의 근원 : 적당히 빠를 수 있다는 이유만으로 무언가를 장려하는 것은 시기상조입니다. 다른 고려 사항이 있습니다.
- 재귀는 종종 훨씬 더 간결하고 명확하게 의도를 전달합니다.
- 일반적으로 가변 상태를 피함으로써 함수형 프로그래밍 언어는 추론하고 디버그하기가 더 쉽고 재귀가 그 예입니다.
- 재귀는 반복보다 더 많은 메모리를 사용합니다.
재귀는 이론상 우아하거나 효율적으로 보이지만 실제로는 일반적으로 덜 효율적입니다 (컴파일러 또는 동적 재 컴파일러가 코드가 수행하는 작업을 변경하지 않는 한). 일반적으로 불필요한 서브 루틴 호출을 유발하는 모든 것은 느려질 것입니다. 특히 둘 이상의 인수가 푸시 / 팝되는 경우 더욱 그렇습니다. 프로세서 사이클을 제거하기 위해 할 수있는 모든 것, 즉 프로세서가 씹어야하는 명령은 공정한 게임입니다. 일반적으로 컴파일러는이 작업을 상당히 잘 수행 할 수 있지만 효율적인 코드를 직접 작성하는 방법을 아는 것은 항상 좋습니다.
적어도 추상에서는 재귀에 대해 본질적으로 성능이 떨어지는 것은 없다고 생각합니다. 재귀는 특별한 형태의 반복입니다. 언어가 재귀를 잘 지원하도록 설계된 경우 반복과 마찬가지로 수행 할 수 있습니다.
일반적으로 재귀는 다음 반복에서 가져올 상태 (매개 변수)에 대해 명시 적으로 만듭니다. 이렇게하면 언어 프로세서가 실행을 더 쉽게 병렬화 할 수 있습니다. 적어도 그것은 언어 디자이너가 악용하려는 방향입니다.
Java에서 재귀 솔루션은 일반적으로 비 재귀 솔루션보다 성능이 뛰어납니다. C에서는 반대되는 경향이 있습니다. 나는 이것이 일반적으로 적응 적으로 컴파일 된 언어와 미리 컴파일 된 언어에 적용된다고 생각합니다.
편집 : "일반적으로"는 60/40 분할과 같은 것을 의미합니다. 언어가 메서드 호출을 얼마나 효율적으로 처리하는지에 따라 다릅니다. JIT 컴파일은 인라인 처리 방법을 선택하고 최적화에서 런타임 데이터를 사용하는 방법을 선택할 수 있기 때문에 재귀를 선호한다고 생각합니다. 하지만 문제의 알고리즘과 컴파일러에 따라 다릅니다. 특히 Java는 재귀 처리에 대해 계속해서 더 똑똑해지고 있습니다.
Java를 사용한 정량적 연구 결과 (PDF 링크) . 이들은 대부분 정렬 알고리즘이며 이전 Java Virtual Machine (올바르게 읽으면 1.5.x)을 사용하고 있습니다. 그들은 때때로 재귀 구현을 사용하여 2 : 1 또는 4 : 1 성능 향상을 얻지 만 재귀가 상당히 느린 경우는 드뭅니다. 내 개인적인 경험상 그 차이는 그다지 뚜렷하지 않지만 재귀를 현명하게 사용할 때 50 % 향상이 일반적입니다.
나는 항상 하나가 다른 것보다 낫다고 추론하기 어렵다는 것을 알게된다.
사용자 파일 시스템에서 백그라운드 작업을 수행해야하는 모바일 앱에서 작업 중입니다. 백그라운드 스레드 중 하나는 사용자에게 업데이트 된 데이터를 유지하기 위해 수시로 전체 파일 시스템을 스윕해야합니다. 그래서 Stack Overflow를 두려워하여 반복 알고리즘을 작성했습니다. 오늘 나는 같은 직업을 위해 재귀적인 것을 썼다. 놀랍게도 반복 알고리즘이 더 빠릅니다 : 재귀-> 37 초, 반복-> 34 초 (정확히 동일한 파일 구조에서 작동).
재귀 :
private long recursive(File rootFile, long counter) {
long duration = 0;
sendScanUpdateSignal(rootFile.getAbsolutePath());
if(rootFile.isDirectory()) {
File[] files = getChildren(rootFile, MUSIC_FILE_FILTER);
for(int i = 0; i < files.length; i++) {
duration += recursive(files[i], counter);
}
if(duration != 0) {
dhm.put(rootFile.getAbsolutePath(), duration);
updateDurationInUI(rootFile.getAbsolutePath(), duration);
}
}
else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) {
duration = getDuration(rootFile);
dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile));
updateDurationInUI(rootFile.getAbsolutePath(), duration);
}
return counter + duration;
}
반복 : -반복적 역 추적을 사용하는 반복적 깊이 우선 검색
private void traversal(File file) {
int pointer = 0;
File[] files;
boolean hadMusic = false;
long parentTimeCounter = 0;
while(file != null) {
sendScanUpdateSignal(file.getAbsolutePath());
try {
Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL);
} catch (InterruptedException e) {
e.printStackTrace();
}
files = getChildren(file, MUSIC_FILE_FILTER);
if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) {
hadMusic = true;
long duration = getDuration(file);
parentTimeCounter = parentTimeCounter + duration;
dhm.put(file.getAbsolutePath(), duration);
updateDurationInUI(file.getAbsolutePath(), duration);
}
if(files != null && pointer < files.length) {
file = getChildren(file,MUSIC_FILE_FILTER)[pointer];
}
else if(files != null && pointer+1 < files.length) {
file = files[pointer+1];
pointer++;
}
else {
pointer=0;
file = getNextSybling(file, hadMusic, parentTimeCounter);
hadMusic = false;
parentTimeCounter = 0;
}
}
}
private File getNextSybling(File file, boolean hadMusic, long timeCounter) {
File result= null;
//se o file é /mnt, para
if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) {
return result;
}
File parent = file.getParentFile();
long parentDuration = 0;
if(hadMusic) {
if(dhm.containsKey(parent.getAbsolutePath())) {
long savedValue = dhm.get(parent.getAbsolutePath());
parentDuration = savedValue + timeCounter;
}
else {
parentDuration = timeCounter;
}
dhm.put(parent.getAbsolutePath(), parentDuration);
updateDurationInUI(parent.getAbsolutePath(), parentDuration);
}
//procura irmao seguinte
File[] syblings = getChildren(parent,MUSIC_FILE_FILTER);
for(int i = 0; i < syblings.length; i++) {
if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) {
if(i+1 < syblings.length) {
result = syblings[i+1];
}
break;
}
}
//backtracking - adiciona pai, se tiver filhos musica
if(result == null) {
result = getNextSybling(parent, hadMusic, parentDuration);
}
return result;
}
물론 반복이 우아하지는 않지만 현재는 비효율적 인 방식으로 구현되었지만 여전히 재귀보다 빠릅니다. 그리고 나는 그것이 최고 속도로 실행되는 것을 원하지 않기 때문에 더 잘 제어 할 수 있으며 가비지 수집기가 더 자주 작업을 수행하도록 할 것입니다.
Anyway, i wont take for granted that one method is better than the other, and will review other algorithms that are currently recursive. But at least from the 2 algorithms above, the iterative one will be the one in the final product.
I think it would help to get some understanding of what performance is really about. This link shows how a perfectly reasonably-coded app actually has a lot of room for optimization - namely a factor of 43! None of this had anything to do with iteration vs. recursion.
When an app has been tuned that far, it gets to the point where the cycles saved by iteration as against recursion might actually make a difference.
As a low level ITERATION deals with the CX registry to count loops, and of course data registries. RECURSION not only deals with that it also adds references to the stack pointer to keep references of the previous calls and then how to go back.-
My University teacher told me that whatever you do with recursion can be done with Iterations and viceversa, however sometimes is simpler to do it by recursion than Iteration (more elegant) but at a performance level is better to use Iterations.-
Recursion is the typical implementation of iteration. It's just a lower level of abstraction (at least in Python):
class iterator(object):
def __init__(self, max):
self.count = 0
self.max = max
def __iter__(self):
return self
# I believe this changes to __next__ in Python 3000
def next(self):
if self.count == self.max:
raise StopIteration
else:
self.count += 1
return self.count - 1
# At this level, iteration is the name of the game, but
# in the implementation, recursion is clearly what's happening.
for i in iterator(50):
print(i)
I would compare recursion with an explosive: you can reach big result in no time. But if you use it without cautions the result could be disastrous.
I was impressed very much by proving of complexity for the recursion that calculates Fibonacci numbers here. Recursion in that case has complexity O((3/2)^n) while iteration just O(n). Calculation of n=46 with recursion written on c# takes half minute! Wow...
IMHO recursion should be used only if nature of entities suited for recursion well (trees, syntax parsing, ...) and never because of aesthetic. Performance and resources consumption of any "divine" recursive code need to be scrutinized.
"Iteration is more performant than recursion" is really language- and/or compiler-specific. The case that comes to mind is when the compiler does loop-unrolling. If you've implemented a recursive solution in this case, it's going to be quite a bit slower.
This is where it pays to be a scientist (testing hypotheses) and to know your tools...
Iteration is more performant than recursion, right?
Yes.
However, when you have a problem which maps perfectly to a Recursive Data Structure, the better solution is always recursive.
If you pretend to solve the problem with iterations you'll end up reinventing the stack and creating a messier and ugly code, compared to the elegant recursive version of the code.
That said, Iteration will always be faster than Recursion. (in a Von Neumann Architecture), so if you use recursion always, even where a loop will suffice, you'll pay a performance penalty.
Is recursion ever faster than looping?
on ntfs UNC max path as is 32K
C:\A\B\X\C.... more than 16K folders can be created...
But you can not even count the number of folders with any recursive method, sooner or later all will give stack overflow.
Only a Good lightweight iterative code should be used to scan folders professionally.
Believe or not, most top antivirus cannot scan maximum depth of UNC folders.
참고URL : https://stackoverflow.com/questions/2185532/why-should-recursion-be-preferred-over-iteration
'IT박스' 카테고리의 다른 글
| Python에서 "+ ="를 재정의 하시겠습니까? (0) | 2020.11.30 |
|---|---|
| 데이터 유효성을 검사 할 때 예외를 던지는 것이 좋은 생각입니까, 나쁜 생각입니까? (0) | 2020.11.30 |
| 좋아하는 Kohana 팁 및 기능? (0) | 2020.11.30 |
| UITableView에서 빈 행을 숨기고 비어 있지 않은 행을 기반으로 Uitableview의 높이를 변경하는 방법 (0) | 2020.11.29 |
| PHP 치명적인 오류 : 빈 속성에 액세스 할 수 없습니다. (0) | 2020.11.29 |