C-使这些递归零件的速度如此不同的原因

Question

我必须制定递归功能才能应用于作业（我不允许使用有关河内塔的标准数学库。我偶然发现了以下代码想法是与分配一起工作的好部分，但是不可能（n> 30）运行它，因为它是如此慢：

#include <stdio.h>
#include <stdlib.h>
int TOH(int,char,char,char);
int main()
{
    int n;
    printf("nEnter number of disks:");
    scanf("%d",&n);
    int c = TOH(n,'A','C','B');
    printf("nTotal number of moves = %d n ", c);
    return 0;
}
int TOH(int n,char x,char y,char z)
{
    int count = 0;
    if(n>0){
    count = TOH(n-1, x, z, y);
    count++;
    count += TOH(n-1, z, y, x);
    }
    return count;
}

在寻找速度的解决方案时，我偶然发现了此代码，该代码在使用递归时立即运行。我迷失了这种速度差异的来源：

#include <stdio.h>
#include <stdlib.h>
float count_moves(int);
float power(int);
int main()
{
    int STACKS;
    printf("nEnter numbers of disks: ");
    scanf("%d", &STACKS);
    float total = count_moves(STACKS);
    printf("nTotal number of moves: %.0fn", total);
    return 0;
}
float power(int multi)
{
    if(!multi)
    {
        return 1;
    }
    else
    {
        return 2 * power(multi - 1);
    } 
}
float count_moves(int layers)
{
    if(!layers)
    {
        return 0;
    }
    else
    {
        return power(layers - 1) + count_moves(layers - 1);
    }
}

第二个能够在控制台中立即打印某些东西，而第二个则花费更长的数字，我做了N/堆栈？

Answer 1

首先，我建议您绘制递归树。查看钉子= 30的大小。请参阅河内塔的复杂性？它具有O（2^n）的复杂性。http://www.iitk.ac.in/esc101/08jan/lecnotes/lecture32.pdf

第二个解决方案不是以传统方式计算它。它正在打一个电话。t（n-1） c = o（n^2）

so，2^30 vs 30^2。猜猜，哪一个更快！

亲自见。

添加对函数的计数器（制作'c'和'd'全局）

float power(int multi)
{
    printf("d = %dn",d);
    d++;
    if(!multi)
    {
        return 1;
    }
    else
    {
        return 2 * power(multi - 1);
    } 
}
float count_moves(int layers)
{
    printf("c = %dn",c);
    c++;
    if(!layers)
    {
        return 0;
    }
    else
    {
        return power(layers - 1) + count_moves(layers - 1);
    }
}

并查看它们被调用的次数。

Answer 2

忽略毫无意义的参数，第一个算法是count = (n > 0) ? TOH(n-1)+TOH(n-1)+1 : 0。TOH的每个呼叫都会导致对TOH的另外两个调用。它的复杂性是O（2^n）。每次n上升一个时，成本都会加倍。

第二个是(layers > 0) ? [something linear] + count_moves(layers - 1) : 0。这是两种尾部恢复方法，但每个呼叫最多都会生成一个呼叫。但这是"做n次，每次做这件事n n次"，所以是n*n。是o（n^2）。

o（2^n）比O（n^2）更快地上升。

Answer 3

您的第一个版本遵循该方案，该方案实际上将计算移动环的步骤序列。但是您没有明确计算这些步骤；确实，您的TOH版本忽略了其参数！（除了将它们传递给递归电话，除了将它们传递给递归电话外，也忽略了它们。）

这意味着TOH的返回值仅取决于其第一个参数n。这也意味着您带有n-1的两个递归调用将返回相同的值，因此所有TOH都足够了，并使用返回值两次。更改TOH内部if的主体：

int tmp = TOH(n-1, x, y, z);
count = tmp + 1 + tmp;

使您的代码立即以与以前相同的答案终止。请注意，您可能会在初始n值31中获得算术溢出。

顺便说一句，-O3的GCC似乎足够聪明，可以在您的原始代码上自动执行此优化，而没有任何更改。