爲數字序列創建一個遞歸函數

Question

我知道這是基本的CS知識，但我仍然無法理解在for循環上執行遞歸函數的想法。我仍然困惑於遞歸的想法，尤其是數字。假設有一個數字序列3,11,27,59,123 ....我知道如何找出只是An = An-1 +（8 *（n-1））的數學遞歸序列，但不要真的不知道如何將它放入C++遞歸函數中。

有人可以概述爲上述數字序列創建一個遞歸函數嗎？

Answer 1

遞歸函數有兩個「部分」，基本情況和遞歸。基本情況是您的函數停止遞歸（並開始展開調用堆棧）。如果沒有基礎，函數會自動調用自己，直到發生堆棧溢出並且程序被操作系統終止。

遞歸部分採用最初的問題（在你的情況下找到序列中的第i個數字）並縮小它。發生這種情況，直到基本案例被打。因此，爲了找到一個序列中的第i個數字，讓我們說第4個，你開始尋找第4個數字，但這取決於第3個，這取決於第2個取決於第一個數字。最初的遞歸將問題從第四個數字縮小到第三個。

這是一個在您的序列的遞歸函數中刺（未經測試）。

int recursive(int i) { 
    // This is your base case, it prevents infinite recursion. 
    if (i == 0) return 0; // Or whatever you base value is 
    else { 
    int sum = recursive(i-1) + 8 * (i-1); 
    return sum; 
    } 
} 

很多次可以用循環完成遞歸函數。但是有些功能需要遞歸。例如，Ackermann's Function。在Computerphile

Answer 2

基本遞歸實現上述功能的一個非常好的視頻（你的順序正確的值是3，11，27，51，83，123，...順便說一句）：

int seq(int n) 
{ 
    if (n <= 1) 
     return 3; 
    else 
     return seq(n-1) + 8 * (n-1); 
} 

然而，這個實施不是尾遞歸的（因此它將使用堆棧，而迭代實現則不會）。如果您的序列函數定義爲

#include <functional> 

int seq(int n) 
{ 
    std::function<int(int, int)> seq_r = [&] (int n, int acc) -> int { 
     if (n <= 1) 
      return acc; 
     else 
      return seq_r(n-1, acc + 8 * (n-1)); 
    }; 
    return seq_r(n, 3); 
} 

Answer 3

：

int seq_r(int n, int acc) 
{ 
    if (n <= 1) 
     return acc; 
    else 
     return seq_r(n-1, acc + 8 * (n-1)); 
} 

int seq(int n) 
{ 
    return seq_r(n, 3); 
} 

或者，相同的實現但seq_r隱藏你的函數使用lambda表達式中：我們可以通過引入蓄能器參數寫尾遞歸版本A[n] = A[n-1] + 8*(n-1)那麼你需要兩件事。 1）保存數字序列的結構，以及2）產生這些數字的函數或循環。對於結構，我將使用一個std ::矢量和循環或函數可用於如下：

環

#include <vector> 

int main() 
{ 
    std::vector<int> storage; 

    // Seed the storage with a number since the sequence looks back. 
    storage.push_back(3); 

    // Define the maximum number count. 
    int maxNum = 5; 

    // Create the sequence by starting from n=1 since there are [n-1] terms. 
    for(int n = 1; n <= maxNum; n++) 
     storage.push_back(storage[n - 1] + 8*(n - 1)); 

    return 0; 
} 

功能

#include <vector> 

std::vector<int> storage; 

void DoSequence(int maxNum, int n = 0) 
{ 
    // Check the limit. 
    if(n > maxNum) 
     return; 

    // Check seeding condition if adding the first element, 
    // otherwise run the equation. 
    if(n == 0) 
     storage.push_back(3); 
    else 
     storage.push_back(storage[n - 1] + 8*(n-1)); 

    // Call the same function. 
    DoSequence(maxNum, n + 1); 
} 

int main() 
{ 
    // Call the recursive function with upper limit (n=5). 
    DoSequence(5); 

    return 0; 
} 

還有其他的方法來實現的細節例如如何聲明或處理storage，但這是個人偏好。注意：我沒有測試這個代碼，但希望你能明白這個想法。總之，一旦你定義了序列函數，就創建一個循環或程序函數來生成數字。