반복적 인 알고리즘보다 반복적 인 알고리즘을 선택할 이유가 있습니까?

Question

반복적 인 방법보다 반복적 인 방법을 구현하는 것이 더 편합니다. 시험을 위해 공부하는 동안 대기열을 사용하여 재귀 BFS (Breadth-First Search)를 구현했지만 대기열을 사용하는 재귀 BFS를 온라인에서 검색하는 동안 BFS는 재귀 적 알고리즘이 아니라 반복적 인 알고리즘이라는 것을 계속 읽었습니다. 하나를 선택할 이유가 있습니까?

Answer 1

반복 및 순환 모두 동일한 시간 복잡성을 갖습니다. 재귀 프로그램은 각 재귀 호출이 프로그램의 상태를 스택으로 푸시하고 스택 오버 플로우가 발생할 수 있으므로 더 많은 메모리가 필요합니다. 재귀 코드는 작성하고 관리하기 쉽습니다. tail recursion을 사용하여 재귀 프로그램의 공간 복잡성.

Answer 2

일반적으로 반복 구현이 빠릅니다. 일례로 피보나치 시리즈가 있습니다. 재귀 적 솔루션을 통해 간단한 루프로 구현하는 것이 더 빠릅니다.

더 많은 논의는 여기 Recursion or Iteration?

Answer 3

반복은 컴퓨터에 대한 더 효율적입니다. 재귀 적 (recursive)은 프로그래머에게는 더 효율적이고 좀더 우아하다 (아마).

재귀 호출의 문제는 각 재귀 호출이 상태/프레임을 호출 스택에 푸시함으로써 심층 재귀를 위해 리소스 소모 (스택 오버플로!)로 빠르게 이어질 수 있다는 것입니다. 그러나 솔루션은 종종 코드 작성 및 읽기가 더 쉽습니다.

반복은 모두 로컬 프레임에서 수행되기 때문에 성능이 향상됩니다. 그러나 반복적으로 반복적으로 변환하면 알고리즘의 진행을 수용하기 위해 변수를 도입하기 때문에 판독 가능성을 줄일 수 있습니다.

코드 작성 및 유지 관리가 가장 쉬운 구현을 선택하십시오. 시연 된 문제가있는 경우에만 걱정하십시오.