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: %.0f\n", 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/STACKS 数字越大？

Answer 1

首先我建议你画出递归树。查看 pegs = 30 时它有多大。请参阅 Complexity for towers of Hanoi? 它的复杂度为 O(2^n)。 http://www.iitk.ac.in/esc101/08Jan/lecnotes/lecture32.pdf

第二种解决方案不是以传统方式计算它。它正在打一个电话。 T(n-1) + c = O(n^2)

所以，2^30 与 30^2。猜猜看，哪个更快!

自己看看。

为函数添加一个计数器，例如 (使'c'和'd'全局化)

float power(int multi)
{
    printf("d = %d\n",d);
    d++;
    if(!multi)
    {
        return 1;
    }

    else
    {
        return 2 * power(multi - 1);
    } 
}

float count_moves(int layers)
{
    printf("c = %d\n",c);
    c++;
    if(!layers)
    {
        return 0;
    }

    else
    {
        return power(layers - 1) + count_moves(layers - 1);
    }
}

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