为数字序列创建递归函数

Question

我知道这是基本的CS知识，但是我仍然无法掌握在for loop上执行递归函数的想法。我仍然对递归的想法，尤其是数字感到困惑。假设有一个数字序列3、11、27、59、123 ....我知道如何找出数学递归序列，该序列只是一个= an-1 （8*（n-1）），但是'真的知道如何将其放入C 递归功能中。

有人可以概述上述数值序列的递归函数吗？

Answer 1

递归函数具有两个"部分"，基本情况和递归。基本情况是当您的功能停止递归时（并开始放弃呼叫堆栈）。没有基础，功能只会一直在调用，直到堆栈溢出发生并且程序由OS终止。

递归零件将初始问题（在您的情况下以序列找到ITH数字）并缩小它。这会发生在命中基本案件之前。因此，要以顺序找到ITH数字，可以说第4个开始寻找第四个数字，但这取决于第三个数字，这取决于第二个数字，取决于第一个。初始递归将问题从第四数字缩小到第三个数字

这是您序列的递归函数的刺伤（根本没有测试）。

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的功能。一个非常好的计算机的视频

Answer 2

上述功能的基本递归实现（序列的适当值为3、11、27、51、83、123，…... btw）：

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

但是，此实现不是尾部回复（因此它将使用堆栈，而迭代实现则不会）。我们可以通过引入累加器参数来编写尾部回复版本：

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);
}

或相同的实现，但使用lambda表达式隐藏了seq_r：

#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

如果您的序列函数定义为：A[n] = A[n-1] + 8*(n-1)，则需要两件事。1）保存数字序列的结构，以及2）函数或循环产生这些数字。对于结构，我将使用std :: vector，并且循环或函数可以如下使用：

循环

#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，但这是个人喜好。注意：我没有测试此代码，但希望您明白了。简而言之，一旦定义了序列函数，然后创建一个循环或程序函数来生成数字。