chanong 我们使用的策略是重复将该值除以 10 并打印每个余数。 例如，4267除以10的余数是7，但我们不能直接打印这个余数。 我们需要打印的是代表机器字符集中数字“7”的值。 在ASCII码中，字符“7”的值为55，因此我们需要将余数加上48才能得到正确的字符。 不过，使用字符常量代替整型常量可以提高程序的可移植性。 ‘0’的ASCII码是48，所以我们把余数加上‘0’，所以有如下关系：
‘0’+ 0 = ‘0’
‘0’+1 =‘1’
‘0’+ 2 = ‘2’
...
从这些关系中，我们不难看出，余数加上‘0’就可以得到相应字符的编码。 然后打印出剩余的部分。 接下来，取商的值。 4267/10 等于 426。然后用该值重复上述步骤。
这种方法的唯一问题是它以完全相反的顺序产生数字。 它们是反向打印的。 所以在我们的程序中使用递归来解决这个问题。
我们程序中的函数是递归的，因为它包含对自身的调用。 乍一看，该函数似乎永远不会终止。 当函数被调用时，它将调用自身，第二次调用将调用自身，依此类推，似乎永远如此。 这也是我们刚接触递归时最不明白的事情。 然而，事实上这并没有发生。
该程序的递归实现了某种类型的螺旋 while 循环。 每次执行循环体时，while 循环都必须取得一些进展，逐渐接近循环终止条件。 递归函数也是如此，每次递归调用后它必须越来越接近某个约束。 当递归函数满足此约束时，它不再调用自身。
在程序中，递归函数的约束是变量为零。 在每次递归调用之前，我们都会除以 10，因此每次递归调用它都会越来越接近于零。 当它最终变为零时，递归终止。
/*接受一个整数值（无符号0，将其转换为字符并打印，前导零被删除*/
#
int（整数值）
整数；
= 值/10；
如果（！= 0）
( );
（值% 10 + '0'）；
递归如何帮助我们以正确的顺序打印这些字符？ 以下是该函数的工作原理。
1. 将参数值除以10
2. 如果该值非零，则调用-to-ascii 打印当前值的每个数字。
3.接下来，打印步骤1中除法运算的余数
请注意，在第二步中，我们需要打印当前值的数字。 我们面临的问题和原来的问题一模一样，只是变量的值更小了。 我们使用刚刚编写的函数解决这个问题（它将整数转换为单独的数字字符并将其打印出来）。 由于 的值越来越小，递归最终会终止。
一旦理解了递归，阅读递归函数的最简单方法不是关注其执行，而是相信递归函数将成功完成其任务。 如果您正确执行每个步骤，正确设置约束，并且每次调用后都更接近约束，则递归函数将始终正确完成任务。
但是，为了了解递归的工作原理，您需要跟踪递归调用的执行情况，所以让我们这样做。 跟踪递归函数执行的关键是了解函数中声明的变量是如何存储的。 当调用函数时，会在运行时堆栈上为其变量创建空间。 先前调用的函数的变量保留在堆栈中，但它们被新函数的变量遮盖，因此无法访问。
当递归函数调用自身时就会出现这种情况。 每次进行新的调用时，都会创建一批变量，这将屏蔽上一次调用递归函数创建的变量。 当我跟踪递归函数的执行时，我必须将变量与不同的调用分开以避免混淆。
程序中的函数有两个变量：参数值和局部变量。 下图显示了堆栈的状态，当前可访问的变量位于顶部。 所有其他被调用的变量都呈灰色阴影，表示当前正在执行的函数无法访问它们。
假设我们调用值为4267的递归函数。当函数第一次开始执行时，堆栈的内容如下所示：
执行除法后，堆栈内容如下：
接下来，if 语句确定该值非零，因此对该函数进行递归调用。 第二次调用该函数时，堆栈内容如下：
在堆栈上创建一批新变量，隐藏前一批变量。 除非当前递归调用返回，否则无法访问它们。 再次进行除法运算后，栈中的内容如下：
现在 的值是 42，仍然不为零，因此我们需要继续递归调用并创建另一批变量。 执行完本次调用的启动操作后，堆栈内容如下：
此时 的值仍然不为零，仍然需要执行递归调用。 执行除法运算后，栈中的内容如下：
不包括递归调用语句本身，到目前为止执行的语句只是除法运算和对 的值的测试。 由于这些语句是递归调用并重复执行的，所以其效果类似于循环：当 的值非零时，将其值作为初始值重新开始循环。 然而，递归调用会保存一些信息（与循环不同），例如保存在堆栈上的变量值。 这些信息很快就会变得非常重要。
现在该值为零，递归函数不再调用自身并开始打印输出。 然后该函数返回并开始销毁堆栈上的变量值。
每次调用通过对值模 10 进行余数运算来获取变量值的最后一个数字。结果是 0 到 9 之间的整数。将其添加到字符常量 '0'，结果是该数字对应的 ASCII 字符，然后打印这个字符。
输出4：
然后函数返回并且其变量从堆栈中销毁。 然后，先前对递归函数的调用使用其自己的变量（现在位于堆栈顶部）恢复执行。 因为它的值为42，所以调用后打印的数字是2。
输出 42：
然后对递归函数的调用也返回，并且它的变量被销毁。 堆栈顶部是上次调用递归函数的变量。 从此位置继续递归调用，这次打印的数字是6。在本次调用返回之前，堆栈的内容如下：
输出 426：
现在我们已经展开了整个递归并回到了对该函数的原始调用。 此调用打印数字 7，这是其值参数除以 10 后的余数。
输出 4267：
然后，这个递归函数完全返回到其他函数调用它的地方。
如果将打印的字符一个接一个地排列并出现在打印机或屏幕上，您将看到正确的值：4267
汉诺塔问题的递归算法分析：
寺庙里有三根柱子。 第一个有64块盘子，从上到下盘子越来越大。 请寺里的老和尚把64块盘子全部移到第三根柱子上。 移动时，小板只能托住大板。 并且一次只能移动一个。
1、这时，老和尚（我们以后称他为第一和尚）觉得很难，于是他想：如果有人能把前63块盘子搬到第二根柱子上，我就直接把最后一块盘子搬走。 到第三根柱子时，让人把前63块板从第二根柱子移到第三根柱子上。 我的任务完成了，简单。 于是他找到了一位年轻的和尚（我们以后称他为二和尚）并下令：
① 你把前63块盘子移到第二根柱子上
② 然后我自己把第64块板移到了第三根柱子上
③ 你把前63块盘子移到第三根柱子上
2、第二个和尚接手这个任务，觉得很难，于是他像第一个和尚一样想：如果有人能把前62块盘子搬到第三根柱子上，我就把最后一块盘子直接搬到第二根柱子上，然后请人将前 62 个盘子从第三根柱子移到第三根柱子上。 我的任务完成了，简单。 于是他又找到了一位年轻的和尚（我们以后称他为三和尚）并下令说：
① 你把前62块盘子移到第三根柱子上
② 然后我自己把第63块板移到了第二根柱子上
③ 将前 62 个盘子移至第二根柱子上
3、第三个和尚接受了任务，顺利地将搬运前61个盘子的任务交给了第四个和尚，以此类推，直到把任务交给了第64个和尚（估计第64个和尚是非常郁闷，没有机会向别人发号施令，因为他的盘子里只有一盘）。
4. 至此，任务已经移交，是时候大家各司其职了。 推回完成：
第 64 个和尚移动第 1 个盘子，将其移开，然后第 63 个和尚移动他分配给自己的第 2 个盘子。
第 64 号和尚将第一块盘子移到第二块盘子上。 至此，第64位修士的任务就完成了，第63位修士也完成了第62位修士交给他的任务的第一步。
从上面可以看出，只有当第64个修士的任务完成后，第63个修士的任务才能完成。 只有当第2个修士——第64个修士的任务完成后，第1个修士的任务才能完成。 结束。 这是一个典型的递归问题。 现在我们用3个板块来分析一下：
第一个和尚命令：
① 对于第二个和尚，你首先将第一根柱子前面的两个盘子移到第二根柱子上。 （在第三支柱的帮助下）
② 第一个和尚亲自将第一根柱子上的最后一个盘子移到第三根柱子上。
③ 对于第二个和尚，将前两个盘子从第二根柱子移到第三根柱子上。
显然，第二步很容易实现（哎，人总是自私的，把容易的事留给自己，把难的事留给别人）。
第一步，第二个和尚有两个盘子，所以他命令：
① 对于第三个和尚，将第一根柱子上的第一块板移到第三根柱子上。 （在第二支柱的帮助下）
② 第二个和尚亲自将第一根柱子上的第二块板移到第二根柱子上。
③ 第三个和尚将第一个盘子从第三根柱子移到第二根柱子上。
同样，第二步很容易实现，但是第三个和尚只需要移动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个盘子移动7+1+7=15步。 同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此我们可以知道，移动n个盘子需要(2的n次方)-1步。
从上面整体综合分析可以看出，n个板块从区块1（相当于第一支柱）移动到了区块3（相当于第三支柱）：
(1) 在座位 3 的帮助下，将座位 1 上的 (n-1) 个盘子移至座位 2。
(2)将第1个座位上的第n个盘子移动到第3个座位上。
(3)借助1座将2座上的(n-1)块板移至3座。
下面用 hanoi(n,a,b,c) 来表示借助 2 将 n 个板块从 1 移动到 3。
显然： (1) 步骤是 hanoi(n-1,1,3,2)
(3) 步骤为hanoi(n-1,2,1,3)
用C语言表达为：
#
int（int n，字符a，字符b）
("..%d..形成..%c..到..%c.."n",n,a,b);
0;
int hanoi(int n,字符 a,字符 b,字符 c)
if( n==1 ) 移动 (1,a,c);
别的
河内(n-1,a,c,b);
移动（n，a，c）；
河内(n-1,b,a,c);
};
0;
int main()
整数；
scanf("%d",#);
河内(num,'A','B','C');
0;
【深入讲解C语言递归算法】相关文章：
1.C语言递归函数教学方法
2.深入剖析C语言中的野指针
3、C语言实现KMP算法示例
4.C语言中数值与真假的深入分析
5.C语言压缩字符串的算法
6、C语言使用BF-KMP算法示例
7.C语言函数的递归调用
8.C语言三种常见排序算法分析
9、C语言使用快速排序算法对元素进行排序的示例
微信扫一扫打赏
支付宝扫一扫打赏
