이 재귀 함수는 반복 할 수 없습니까?

Question

이 함수를 반복적으로 만들기 위해 조금 생각했습니다. 가능한 것처럼 보였지만 현재로서는 그렇게 할 수있는 방법을 찾을 수 없습니다. 그렇다면이 함수가 어떤 방식 으로든 반복 될 수 없다는 것을 증명할 수 있습니까? 반복에서 의미하는 것은 재귀 함수 호출을 전혀 사용하지 않는 것입니다.

//이 새로운 auto 키워드를 좋아합니다.

void every_permutation(const std::vector<int>& v, std::vector<std::vector<int>>& vs) { 
    if (v.size() == 1) { 
     vs.push_back(v); 
     return; 
    } 
    for (auto i = v.begin(); i != v.end(); ++i) { 
     std::vector<int> v_2; 
     for (auto j = v.begin(); j != v.end(); ++j) { 
      if (j != i) { 
       v_2.push_back(*j); 
      } 
     } 
     std::vector<std::vector<int>> vs_2; 
     every_permutation(v_2, vs_2); 
     for (auto j = vs_2.begin(); j != vs_2.end(); ++j) { 
      j->push_back(*i); 
     } 
     vs.insert(vs.end(), vs_2.begin(), vs_2.end()); 
    } 
} 

Answer 1

이 함수는 확실히 반복적 일 수 있습니다. 사실 표준 라이브러리에는 반복적으로 수행하는 함수가 있습니다 : std::next_permutation. 당신은 너무처럼 사용할 수 있습니다 물론

         // v-- note: v is a copy here 
void every_permutation(std::vector<int> v, std::vector<std::vector<int>>& vs) { 
    // because we need to start with a sorted vector to get all permutations. 
    std::sort(v.begin(), v.end()); 

    do { 
    vs.push_back(v); 
    } while(std::next_permutation(v.begin(), v.end())); 
} 

,이 조각은 std::next_permutation이 그것을 수행하는 방법을 이야기하지만, 행복하게 가능한 구현이 here 설명이되지 않습니다.

Answer 2

나는 무엇을 요구하는지 것은이 재귀 함수가 재귀 꼬리인지 생각합니다. Tail 재귀 함수는 루프처럼 쉽게 재 작성 될 수 있으며 스택의 여러 변수를 추적 할 필요가 없습니다. 이 함수는 이 아니고 꼬리 재귀입니다. 실제로 반복마다 한번 이상 호출 할 수있는 재귀 함수는 꼬리 재귀 적이 될 수 없습니다.

꼬리 재귀가 아닌 재귀 함수는 반복적으로 작성할 수 있지만 중첩 된 하위 문제를 해결 한 후에 다시 돌아갈 수 있도록 계산 상태를 추적하려면 일종의 스택이 필요합니다. 사용되는 공간의 양은 적어도 중첩 깊이에 비례합니다.

물론 꼬리 재귀가 아닌 함수는 꼬리 재귀가되도록 재 작성 될 수 있습니다. 경우에 따라이를 수행하기 위해 사용 된 알고리즘을 완전히 변경해야합니다.