這個遞歸函數不可能迭代嗎？

-4

我試着想一點，使這個函數迭代。這似乎是可能的，但我目前無法找到辦法。那麼甚至有可能證明這個函數不能以任何方式迭代？我的意思是迭代根本不使用遞歸函數調用。這個遞歸函數不可能迭代嗎？

//我喜歡這個新的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()); 
    } 
}

來源

2014-12-13 xiver77

理論上講，所有的遞歸算法都可以轉化爲帶有堆棧的迭代算法。 – 2014-12-13 01:31:01

該算法的說明會很好。 – 2014-12-13 01:37:24

這個函數當然可以迭代。實際上，標準庫中有一個函數可以迭代執行：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。

來源

2014-12-13 01:49:20 Wintermute

我想你問的是這個遞歸函數是否尾遞歸。尾遞歸函數可以很容易地重寫爲循環，並且不需要堆棧來跟蹤局部變量的多個幀。這個函數是而不是尾遞歸;實際上，任何可能在每次迭代中多次調用自身的遞歸函數都不可能是尾遞歸的。

不是尾遞歸的遞歸函數仍然可以迭代編寫，但是爲了跟蹤計算狀態，您需要某種堆棧，以便在解決嵌套子問題後再回到它。所用空間的大小至少與嵌套深度成正比。

當然，不是尾遞歸的函數有時可以重寫，以便它是尾遞歸。在某些情況下，您需要完全更改所使用的算法才能完成此操作。

來源

2014-12-13 01:47:47 Brian

這個遞歸函數不可能迭代嗎？

回答

相關問題