재귀 대 반복

재귀 대 반복

---

모든 곳 recursion에서 for 루프를 사용할 수 있다고 말하는 것이 맞 습니까? 그리고 재귀가 일반적으로 느리다면 for 루프 반복을 통해 그것을 사용하는 기술적 이유는 무엇입니까?

그리고 재귀를 for 루프로 변환하는 것이 항상 가능하다면 그것을 수행하는 경험적 방법이 있습니까?

---

재귀는 일반적으로 호출자 함수로 돌아갈 수 있도록 모든 함수 호출을 스택에 저장해야하기 때문에 훨씬 느립니다. 대부분의 경우 범위 격리를 구현하려면 메모리를 할당하고 복사해야합니다.

꼬리 호출 최적화 와 같은 일부 최적화 는 재귀를 더 빠르게 만들지 만 항상 가능하지는 않으며 모든 언어로 구현되지는 않습니다.

재귀를 사용하는 주된 이유는 다음과 같습니다.

• 문제에 대한 우리의 접근 방식을 모방 할 때 많은 경우에 더 직관적입니다.
• 트리와 같은 일부 데이터 구조는 재귀를 사용하여 탐색하기가 더 쉽습니다 (또는 어떤 경우에도 스택이 필요함).

물론 모든 재귀 는 일종의 루프로 모델링 될 수 있습니다. 이것이 CPU가 궁극적으로하는 일입니다. 그리고 재귀 자체는 더 직접적으로 함수 호출과 범위를 스택에 넣는 것을 의미합니다. 그러나 재귀 알고리즘을 반복 알고리즘으로 변경하려면 많은 작업이 필요하고 코드 유지 관리가 어려워 질 수 있습니다. 모든 최적화에 대해 일부 프로파일 링이나 증거가 필요하다는 것을 보여줄 때만 시도해야합니다.

---

재귀가 사용되는 모든 곳에서 for 루프를 사용할 수 있다고 말하는 것이 맞습니까?

예, 대부분의 CPU에서 재귀는 루프와 스택 데이터 구조로 모델링되기 때문입니다.

그리고 재귀가 일반적으로 느리다면 그것을 사용하는 기술적 이유는 무엇입니까?

"보통 느리다"는 것이 아닙니다. 잘못 적용되는 재귀가 더 느립니다. 게다가, 현대 컴파일러는 묻지 않고 일부 재귀를 루프로 변환하는 데 능숙합니다.

그리고 재귀를 for 루프로 변환하는 것이 항상 가능하다면 그것을 수행하는 경험적 방법이 있습니까?

반복적으로 설명 할 때 가장 잘 이해되는 알고리즘을위한 반복 프로그램을 작성하십시오. 재귀 적으로 가장 잘 설명 된 알고리즘에 대한 재귀 프로그램을 작성합니다.

예를 들어, 이진 트리 검색, 빠른 정렬 실행 및 많은 프로그래밍 언어에서 표현식 구문 분석은 종종 재귀 적으로 설명됩니다. 이것들도 재귀 적으로 코딩하는 것이 가장 좋습니다. 반면에 계승 계산 및 피보나치 수 계산은 반복 측면에서 설명하기가 훨씬 쉽습니다. 그들에게 재귀를 사용하는 것은 큰 망치로 파리를 날리는 것과 같습니다 : 큰 망치가 정말 좋은 일을하더라도 좋은 생각이 아닙니다 ⁺ .

---

⁺ Dijkstra의 "Discipline of Programming"에서 쇠 망치 비유를 빌 렸습니다.

---

질문 :

그리고 재귀가 일반적으로 느리다면 for 루프 반복을 통해 그것을 사용하는 기술적 이유는 무엇입니까?

대답 :

일부 알고리즘에서는 반복적으로 해결하기가 어렵 기 때문입니다. 심도 우선 검색을 재귀 적 및 반복적으로 해결하십시오. 반복을 통해 DFS를 풀기가 어렵다는 생각을 갖게 될 것입니다.

시도해 볼만한 또 다른 좋은 점 : Merge sort를 반복적으로 작성해보십시오. 꽤 시간이 걸릴 것입니다.

질문 :

재귀가 사용되는 모든 곳에서 for 루프를 사용할 수 있다고 말하는 것이 맞습니까?

대답 :

예. 이 스레드 는 이에 대한 매우 좋은 대답을 가지고 있습니다.

질문 :

그리고 재귀를 for 루프로 변환하는 것이 항상 가능하다면 그것을 수행하는 경험적 방법이 있습니까?

대답 :

날 믿어. 깊이 우선 검색을 반복적으로 해결하기 위해 자체 버전을 작성하십시오. 일부 문제는 재귀 적으로 해결하기가 더 쉽다는 것을 알 수 있습니다.

힌트 : 재귀는 분할 정복 기법 으로 해결할 수있는 문제를 풀 때 좋습니다 .

---

느린 것 외에도 재귀는 얼마나 깊이가 있는지에 따라 스택 오버플로 오류를 일으킬 수 있습니다.

---

반복을 사용하여 동등한 메서드를 작성하려면 명시 적으로 스택을 사용해야합니다. 반복적 버전에 솔루션에 대한 스택이 필요하다는 사실은 문제가 재귀로부터 이익을 얻을 수있을만큼 충분히 어렵다는 것을 나타냅니다. 일반적으로 재귀는 고정 된 양의 메모리로 해결할 수없는 문제에 가장 적합하며 결과적으로 반복적으로 해결 될 때 스택이 필요합니다. 재귀와 반복은 서로 다른 패턴을 따르면서 동일한 결과를 보여줄 수 있습니다. 어떤 방법이 더 잘 작동하는지 결정하는 것은 사례별로 이루어지며 모범 사례는 문제가 따르는 패턴을 기반으로 선택하는 것입니다.

예를 들어, Triangular 시퀀스의 n 번째 삼각 수를 찾으려면 : 1 3 6 10 15… 반복 알고리즘을 사용하여 n 번째 삼각 수를 찾는 프로그램 :

반복 알고리즘 사용 :

//Triangular.java
import java.util.*;
class Triangular {
   public static int iterativeTriangular(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i ++)
         sum += i;
      return sum;
   }
   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                            iterativeTriangular(n));
   }
}//enter code here

재귀 알고리즘 사용 :

//Triangular.java
import java.util.*;
class Triangular {
   public static int recursiveTriangular(int n) {
      if (n == 1)
     return 1;  
      return recursiveTriangular(n-1) + n; 
   }

   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                             recursiveTriangular(n)); 
   }
}

---

Most of the answers seem to assume that iterative = for loop. If your for loop is unrestricted (a la C, you can do whatever you want with your loop counter), then that is correct. If it's a real for loop (say as in Python or most functional languages where you cannot manually modify the loop counter), then it is not correct.

All (computable) functions can be implemented both recursively and using while loops (or conditional jumps, which are basically the same thing). If you truly restrict yourself to for loops, you will only get a subset of those functions (the primitive recursive ones, if your elementary operations are reasonable). Granted, it's a pretty large subset which happens to contain every single function you're likely to encouter in practice.

What is much more important is that a lot of functions are very easy to implement recursively and awfully hard to implement iteratively (manually managing your call stack does not count).

---

Yes, as said by Thanakron Tandavas,

Recursion is good when you are solving a problem that can be solved by divide and conquer technique.

For example: Towers of Hanoi

1. N rings in increasing size
2. 3 poles
3. Rings start stacked on pole 1. Goal is to move rings so that they are stacked on pole 3 ...But
   • Can only move one ring at a time.
   • Can’t put larger ring on top of smaller.
4. Iterative solution is “powerful yet ugly”; recursive solution is “elegant”.

---

I seem to remember my computer science professor say back in the day that all problems that have recursive solutions also have iterative solutions. He says that a recursive solution is usually slower, but they are frequently used when they are easier to reason about and code than iterative solutions.

However, in the case of more advanced recursive solutions, I don't believe that it will always be able to implement them using a simple for loop.

---

A lot of good reasons have been given and I would like to share one more point. Some of the problems are beautifully solved by recursion rather can only be solved by recursion. A sample example would be:

Print all the values of an array but the items of an array could be arrays as well. There could be nested arrays as well but we are not sure about the depth of nested arrays.

A beautiful solution would be this:

<?php
  function print_all_items($array){

       foreach($array as $key=>$value){
           if(is_array($value)) { 
             print_all_items($value);
           }
           else{
             echo "$key => $value <br/>";
           }
       }
  }

$array = array("first" => "first value",  
              "second" => "second value",  
              "third" => "third value",  
               "fourth"=>array(1,2,3,4,5),
              "fifth"=>array(
                       "second array 1",
                       "second array 2",
                       "second array 3",
                       array(
                           "third array 1",
                           "third array 2",
                           "third array 3",
                           )
                       ),
              );

print_all_items($array);

Output:

first => first value 
second => second value 
third => third value 
0 => 1 
1 => 2 
2 => 3 
3 => 4 
4 => 5 
0 => second array 1 
1 => second array 2 
2 => second array 3 
0 => third array 1 
1 => third array 2 
2 => third array 3 

Now this kind of problem cannot be solved by iterative approach since the nature of problems demands dynamic solution.

---

recursion + memorization could lead to a more efficient solution compare with a pure iterative approach, e.g. check this: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

---

Short answer: the trade off is recursion is faster and for loops take up less memory in almost all cases. However there are usually ways to change the for loop or recursion to make it run faster

참고URL : https://stackoverflow.com/questions/15688019/recursion-versus-iteration