BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ wks (cloverprince) 于 (Fri Mar 13 13:10:16 2009) 提到: #include<stdio.h> int f(int x, int y) { if(x==0) { return 0; } else { return f(x-1,f(y-2,x)); } } int main() { printf("%d\n",f(2,1)); return 0; } 按道理说， f(2,1) == f(1,f(1,2)) == f(0,f(f(-1,2)-2,1)) == 0 ☆─────────────────────────────────────☆ AFX (新手上路) 于 (Fri Mar 13 13:39:44 2009) 提到: 【在 wks 的大作中提到: 】 : #include<stdio.h> : int f(int x, int y) { : if(x==0) { : ................... 应用序和正则序你给出的是正则序，实际上C++应该是应用序？即在f(1, f(-1,2))这一步，C++会先求值里面的f(-1,2)，再求值外层的f。所以应用序是“先求值参数而后应用”，请看SICP中文版第十页。顺便参考SICP第13页的练习1.5 ☆─────────────────────────────────────☆ ZMBird (Jack) 于 (Fri Mar 13 14:00:10 2009) 提到: 个人意见是这个程序在可以预见的未来+不可以预见的未来执行的话都会因为堆栈溢出而终止。但考虑到不论f()的参数为什么，都会因为int 类型进行-1操作后会下越界，终有重新调用f(0,???)的时候，此时f()开始返回。可是每次调用f()等到能够返回函数的时候调用f()的次数期望在2^8*sizeof(int)，而f()几乎每次又会重新调用f()，这种计算复杂度在宇宙毁灭的时候必定还没有执行完。 ☆─────────────────────────────────────☆ AFX (新手上路) 于 (Fri Mar 13 14:06:54 2009) 提到: 【在 ZMBird 的大作中提到: 】 : 个人意见是这个程序在可以预见的未来+不可以预见的未来执行的话都会因为堆栈溢出而终止。 : 但考虑到不论f()的参数为什么，都会因为int 类型进行-1操作后会下越界，终有重新调用f(0,???)的时候，此时f()开始返回。可是每次调用f()等到能够返回函数的时候调用f()的次数期望在2^8*sizeof(int)，而f()几乎每次又会重新调用f()，这种计算复杂度在宇宙毁灭的时候必定还没有执行完。也不一定，如果采用应用序，但是如果编译器可以进行尾递归优化的话，就不会存在因为无限递归带来的堆栈溢出的问题，顶多死循环。如果是编译器是按照正则序来求值的话，在第二步程序就终止了，就按照ws大牛列出的式子一样。但是我所见到的C++编译器都是应用序求值，并且不带尾递归优化的 ☆─────────────────────────────────────☆ Vampire (吸血鬼) 于 (Fri Mar 13 14:34:22 2009) 提到: 从汇编代码看是先计算了 return f(x-1,f(y-2,x)); 里面的那个f(y-2,x) ………… ☆─────────────────────────────────────☆ TuBie (PesT是土鳖) 于 (Fri Mar 13 14:38:26 2009) 提到: 绕死我了，我大脑栈溢出了 ☆─────────────────────────────────────☆ nobody (nobody) 于 (Fri Mar 13 14:40:20 2009) 提到: 【在 wks 的大作中提到: 】 : #include<stdio.h> : int f(int x, int y) { : if(x==0) { : ................... f(x-1,f(y-2,x)) f(2, 1) >> f(1, f(-1, 2)) 1>f(-1, 2)>>f(-2, f(0, -1))==f(-2, 0) 到f(-2, 0)这不函数就不会返回了 ☆─────────────────────────────────────☆ ZMBird (Jack) 于 (Fri Mar 13 15:00:06 2009) 提到: To nobody 可是int类型数据不停的-1会下越界啊，然后变成正数，再变成0. 你可以试试 int i=-1; while( i !=0 ) { i--; }; cout<<i<<endl; 这个不会是死循环。调用f(x, y),不论怎样都会调用到 f( 0 ,???)的。 ☆─────────────────────────────────────☆ nobody (nobody) 于 (Fri Mar 13 15:12:15 2009) 提到: 【在 ZMBird 的大作中提到: 】 : To nobody : 可是int类型数据不停的-1会下越界啊，然后变成正数，再变成0. : 你可以试试 : ................... int 越界之后完全是未定义行为，编译器又不给什么保障。之后一切都没有可预见性 ☆─────────────────────────────────────☆ Jarod (学五608鬼魂) 于 (Fri Mar 13 16:49:35 2009) 提到: ....真无聊....不知有啥为什么的..... ☆─────────────────────────────────────☆ yihang (Goodluckfly) 于 (Fri Mar 13 17:08:51 2009) 提到: 【在 nobody 的大作中提到: 】 : f(x-1,f(y-2,x)) : f(2, 1) >> f(1, f(-1, 2)) : 1>f(-1, 2)>>f(-2, f(0, -1))==f(-2, 0) : ................... 大脑栈溢出后，无聊的调试了一下才发现就是这样，会导致函数一直压栈，栈资源耗光而退出 ☆─────────────────────────────────────☆ windam (棒棒糖) 于 (Fri Mar 13 21:45:31 2009) 提到: f(x-1,f(y-2,x)) 这个，C++编译器肯定会先对两个参数求值，然后才能把得结果压栈。。。编译器应该还聪明不到把这种上下文把这种地方直接优化掉吧……

[合集] 这个程序会不会终止？为什么？