为什么我的递归调用次数和书上的不一样?
2021/10/16 23:39:42
本文主要是介绍为什么我的递归调用次数和书上的不一样?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
为什么我的递归次数和书上的不一样
根据《算法导论》中钢条切割问题的描述
我按照他的描述,计算了一遍函数调用次数
按理说:
cut_rod(int * p , int n)
当 n = 0 时,cut_rod(p,0) 会直接返回,调用次数为 1。
当 n = 1 时,会调用一次 cut_rod(p, 1),在 cut_rod(p, 1) 内部,还有一次 cut_rod(p, 0),一共调用2 次。
由数学归纳法,可以推导出,调用次数 $$ T(n) = 2^n $$
然而,我运行的结果却是:
下面是我的代码,你能看出是哪里出了问题吗?
#include <stdio.h> #include <limits.h> #define N 10 #define max(x, y) ((x)>(y) ? (x) : (y)) unsigned int times = 0; int cut_rod(int * p, int n); void main(void) { int p[N+1] = {0,1,5,8,9,10,17,17,20,24,30}; int i; for (i = 0; i <= N; i++) { times = 0; printf("The optimal profit of %d is %3d\n", i, cut_rod(p, i)); printf("function call times: %4d \n", times); } } int cut_rod(int * p, int n) { int r; int i; times++; if (n == 0) return 0; r = INT_MIN; for (i = 1; i <= n; i++) { r = max(r, p[i] + cut_rod(p, n-i)); } return r; }
我用了 gdb 看,愣是没看出问题在哪。
幸好,我还有一个好兄弟,他火眼金睛,一下子就找到问题所在:
问题出现在这里
r = max(r, p[i] + cut_rod(p, n-i));
我调用了一个宏定义函数 max
#define max(x, y) ((x)>(y) ? (x) : (y))
宏定义其实是在预编译阶段将程序中出现的宏替换成宏后面的字符串
max(r, p[i] + cut_rod(p, n-i))
将按照下面的步骤被替换
x 被换成 r, y 被换成 p[i] + cut_rod(p, n-i)
如下图:
于是,替换后的程序就变成了
for (i = 1; i <= n; i++) { r = (r) > (p[i] + cut_rod(p, n-i)) ? (r) : (p[i] + cut_rod(p, n-i)); }
这样,我能明显的看出
当 r <= p[i] + cut_rod(p, n-i)
时,cut_rod(p, n-i)
被执行了2次
这样就能解释,GDB调试时,当n = 1时进行到递归调用时,为什么会出现第2次cut_rod()调用了。
这篇关于为什么我的递归调用次数和书上的不一样?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-30我的第一个Go命令行工具
- 2024-09-30初学者指南:轻松掌握模块化编程
- 2024-09-30顶级5款免费的IntelliJ插件,助你Java开发之路更顺畅
- 2024-09-30提高应用程序可用性:冗余和持久性
- 2024-09-30Twitter 系统设计面试示例
- 2024-09-30JSON对象入门教程:轻松掌握基础用法
- 2024-09-30封装入门:Java面向对象编程的第一步
- 2024-09-30后台交互入门:轻松掌握基础知识与实践技巧
- 2024-09-30轻松入门:后台交互教程详解
- 2024-09-30后台交互项目实战:新手指南