递归算法的详细分析-

C支持通过运行时堆栈实现递归函数. 递归函数是直接或间接调用自身的函数.

许多教科书使用计算机阶乘和斐波那契数列来说明递归. 不幸的是，我们可爱而著名的老师老谭的《 C语言编程》这本书是从阶乘计算得出的函数递归. 结果，阅读过这段经文的学生看到阶乘计算的第一个想法是递归. 但是在阶乘的计算中，递归没有任何优势. 在斐波那契数列中，它的效率非常低而且很糟糕.

这是一个简单的程序，可用于说明递归. 该程序的目的是将整数从二进制形式转换为可打印字符形式. 例如: 给定值为4267，我们需要按顺序生成字符“ 4”，“ 2”，“ 6”和“ 7”. 就像在printf函数中使用％d格式代码一样，它将执行类似的处理.

我们使用的策略是将该值重复除以10，然后打印每个余数. 例如，将4267除以10的余数为7递归 2次调用，但是我们无法直接打印余数. 我们需要打印的是代表机器字符集中数字“ 7”的值. 在ASCII码中，字符“ 7”的值为55，因此我们需要在余数上加48以得到正确的字符. 但是，使用字符常量而不是整数常量可以提高程序的可移植性. ASCII码“ 0”为48，因此我们将“ 0”添加到余数，因此存在以下关系:

“ 0” + 0 =“ 0”

“ 0” + 1 =“ 1”

“ 0” + 2 =“ 2”

...

从这些关系中，我们可以很容易地看到，在余数上加上“ 0”可以生成相应字符的代码. 然后打印出其余部分. 下一步，取商的值4267/10等于426. 然后使用该值重复上述步骤.

这种处理方法的唯一问题是它产生的数字顺序完全相反，它们以相反的顺序打印. 因此，使用递归可在我们的程序中解决此问题.

我们程序中的函数本质上是递归的，因为它包含对自身的调用. 乍一看，该功能似乎永远不会终止. 调用该函数时，它将调用自身，第二个调用也将调用自身，依此类推，它似乎永远被调用. 这也是我们第一次接触递归时最不了解的事情. 但是递归 2次调用，这实际上并没有发生.

该程序的递归实现了某种类型的螺旋while循环. 每次循环主体执行时，while循环必须取得一定的进展，逐渐接近循环终止条件. 递归函数也是如此，在每次递归调用之后，递归函数必须越来越接近某些限制. 当递归函数满足此限制时，它不会自行调用.

在程序中，递归函数的限制条件是变量商为零. 在每次递归调用之前，我们将商除以10，因此每次进行递归调用时，其值都接近于零. 当它最终变为零时，递归结束.

/ *接受整数值（无符号0，将其转换为字符并打印出来，删除前导零* /

#include

int binary_to_ascii（unsigned int值）

{

无符号整数商；

商=值/ 10;

if（商！= 0）

binary_to_ascii（商）;

putchar（value％10 +'0'）;

}

递归如何帮助我们以正确的顺序打印这些字符？以下是此功能的工作流程.

1. 将参数值除​​以10

2. 如果商的值不为零，请调用binary-to-ascii以打印商的当前值的数字

3. 接下来，在步骤1中打印除法运算的其余部分

请注意，在第二步中，我们需要打印的是商当前值的数字. 我们面临的问题与原始问题完全相同，只是变量商的值变小了. 我们使用刚编写的函数（将整数转换为单个数字字符并打印出来）来解决此问题. 随着商的值越来越小，递归最终将终止.

一旦您了解了递归，读取递归函数的最简单方法就是不纠结其执行过程，而要相信递归函数将成功完成其任务. 如果您的每个步骤都正确，您的约束设置正确，并且每次调用后您都更接近约束，则递归函数始终可以正确完成任务.

但是，为了了解递归的工作原理，您需要跟踪递归调用的执行，因此让我们开始吧. 跟踪递归函数执行的关键是了解如何存储在函数中声明的变量. 调用函数时，将在运行时堆栈上创建其变量空间. 先前调用的函数的变量保留在堆栈中，但是它们被新函数的变量覆盖，因此无法访问.

当递归函数调用自身时就是这种情况. 每次进行新的调用时，都会创建一批变量，它们将掩盖由递归函数的上一次调用创建的变量. 当我跟踪递归函数的执行时，我必须区分在不同时间调用的变量，以避免混淆.

程序中的函数具有两个变量: 参数值和局部变量商. 下图显示了堆栈的状态，当前可访问的变量位于堆栈的顶部. 所有其他被调用变量均以灰色阴影表示，表明当前执行的函数无法访问它们.

假设我们调用值为4267的递归函数. 当该函数首次执行时，堆栈的内容如下图所示:

执行除法后，堆栈的内容如下:

接下来，if语句确定商的值不为零，因此它对函数执行递归调用. 第二次调用此函数时，堆栈的内容如下:

在堆栈上创建了新的一批变量，隐藏了前一批变量，除非当前的递归调用返回，否则无法访问它们. 再次执行除法运算后，堆栈的内容如下:

商数的值现在为42，并且仍然非零，因此您需要继续执行递归调用并创建另一批变量. 执行此调用的启动操作后，堆栈的内容如下:

这时，商的值仍然不为零，并且仍然需要执行递归调用. 执行除法运算后，堆栈的内容如下:

不计算递归调用语句本身，到目前为止执行的语句仅是除法运算并测试商的值. 因为这些语句被递归调用并重复执行，所以其效果类似于循环: 当商的值不为零时，将以其值作为初始值重新启动循环. 但是，递归调用将保存一些信息（这与循环不同），这只是将变量的值保存在堆栈中. 这些信息很快将变得非常重要.

现在商数变为零，递归函数不再调用自身，而是开始打印. 然后函数返回并开始销毁堆栈上的变量值.

每次调用putchar来获取变量值的最后一个数字时，方法是对value执行模10的余数运算，结果是0到9之间的整数. 将其添加到字符常量'0' ，结果是与此数字相对应的ASCII字符，然后打印该字符.

输出4:

然后函数返回，并且其变量从堆栈中销毁. 然后，递归函数的上一个调用恢复执行. 她使用自己的变量，这些变量现在位于堆栈的顶部. 由于其值为42，因此在放置putchar后打印的数字为2.

输出42:

然后，递归函数的此调用返回，并且其变量也被销毁. 此时，堆栈顶部的变量是递归函数再次调用的变量. 从该位置继续进行递归调用，这次打印的数字为6. 在此调用返回之前，堆栈的内容如下:

输出426:

现在，我们已经开始整个递归过程，并返回到该函数的原始调用. 该调用将打印出数字7，这是其value参数除以10的余数.

输出4267:

然后，此递归函数完全返回其他函数调用它的地方.

如果将打印的字符依次排列并出现在打印机或屏幕上，则会看到正确的值: 4267

河内塔问题的递归算法分析:

寺庙中有三大支柱. 第一个有64个盘子. 盘子从上到下越来越大. 庙里的老和尚被要求将所有64个盘子移到第三根柱子上. 移动时，只能将小板压在大板上. 一次只能移动一个.

1. 这时，老和尚（以后会叫他第一个和尚）感到困难，所以他想: 如果有人可以将第一个63个板块移到第二个支柱上，我将把最后一个直接移动到第二个柱子上. 第三杆，然后让此人将前63个板从第二杆移动到第三杆. 我的任务完成了，很简单. 因此，他找到了一个比他年轻的和尚（我们稍后将称他为第二个和尚），命令:

①您将前63个板块移到了第二个柱子上

②然后我独自将第64板块移到了第三支柱上

③您将前63个板块移至第三根支柱

2. 第二名和尚承担了任务并发现困难，因此他认为与第一名和尚相同: 如果一个人可以将前62个盘子移到第三根支柱，我将最后一个盘子直接移到第二列，然后让该人将前62个板块从第三列移动到第三列. 我的任务很简单. 因此，他还找到了一个比他年轻的和尚（我们稍后将称他为第三名和尚），命令:

①您将前62个板块移至第三根支柱

②然后我自己将第63个板块移到了第二个支柱上

③您将前62个板块移至第二个支柱

3. 第三名和尚接管了任务，并将第一批61个盘子移至第四名和尚，并等待任务移交给第64名. 到目前为止，和尚（据估计，第64位和尚很沮丧，因为他只有一个盘子，所以他没有机会订购其他人）.

4. 现在该完成任务并完成任务了. 完成后退:

第64名和尚移动第一个盘子并将其移出，然后第63名和尚移动了他分配给他的第二个盘子.

第64位和尚将第一个盘子移到第二个盘子. 至此，第64位和尚的任务已完成，第63位和尚完成了第62位和尚的第一步.

从上面可以看到，只有第64位和尚的任务完成，第63位和尚的任务可以完成，只有第2位和尚-第64位和尚的任务完成之后，第1位和尚的任务可以完成. 这是一个典型的递归问题. 现在我们要分析3个板块:

第一个和尚命令:

①对于第二位和尚，您首先将两块板移动到第一列之前到第二列. （借助第三支柱）

②第一和尚本人将第一根柱子的最后一盘移到了第三根柱子.

③第二个和尚您将前两个盘子从第二根支柱移到了第三根支柱.

显然，第二步很容易实现（嘿，人们总是自私地将简单性留给自己，将困难留给他人）.

第一步，第二名和尚有2个盘子，所以他命令:

①对于第三位和尚，请将第一根支柱的第一块板移动到第三根支柱. （借助第二个支柱）

②第二位和尚我自己将第一根柱子的第二盘移到了第二根柱子.

③第三位和尚，将第一块板从第三根支柱移到第二根支柱.

类似地，第二步很容易实现，但第三名和尚只需要移动1个盘子，因此他不需要发送任务. （注意: 这是停止递归的条件，也称为边界值）

第三步可以分解为第二名和尚仍有2个盘子，命令:

①第三和尚将第二列的第一板移动到第一列.

②作为第二位和尚，我将第二个盘子从第二根柱子移到了第三根柱子上.

③第三位和尚，将第一根柱子上的盘子移到第三根柱子上.

分析的组合为: 1→3 1→2 3→2在第三列的帮助下移至第二列| 1→3留给自己的私人作品| 2→1 2→3 1→3第一个柱移到第三个柱|总共需要七个步骤.

如果有4个盘子，则在第一个和尚的步骤1和步骤3中有3个盘子，因此每个需要7个步骤，总共14个步骤，加上第一个和尚的1个步骤，因此需要4个盘子总共移动7 + 1 + 7 = 15步. 同样，5个板块需要15 + 1 + 15 = 31步，6个板块需要31 + 1 + 31 = 64步...，要移动n个板块需要（2的n次方）-1步.

从上面的整体综合分析中可以看出，n个板块从1（相当于第一个支柱）移动到3（相当于第三个支柱）:

（1）将座椅1上的（n-1）个板移动到座椅2上.

（2）将座位1上的第n个板移动到3个座位上.

（3）在一个座位的帮助下将2个座位上的（n-1）个板移动到3个座位上.

以下使用hanoi（n，a，b，c）表示n个板块在2个席位的帮助下从1个席位移动到3个席位的运动.

很明显: （1）步骤是hanoi（n-1,1,3,2）

（3）步骤是河内（n-1,2,1,3）

用C语言表示，它是:

#include

int move（int n，char a，char b）

{

printf（“ number ..％d..form ..％c..to ..％c ..” n“，n，a，b）;

返回0；

}

int hanoi（int n，char a，char b，char c）

{

如果（n == 1）移动（1，a，c）;

其他

{

hanoi（n-1，a，c，b）;

move（n，a，c）;

河内（n-1，b，a，c）;

};

返回0；

}

int main（）

{

int num;

scanf（“％d”，＆num）;

hanoi（num，'A'，'B'，'C'）;

返回0；

}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-287215-1.html