c++吧 关注：630,888贴子：2,113,926
- 21回复贴，共1页
不感兴趣
开通SVIP免广告
……这个问题好像比较典型，可能有必要加到填坑套餐里。。。
首先你搞错了概念，递归函数是递归论研究的计算对象，一般（μ-）递归函数跟图灵机可计算性等价。递归调用跟递归函数是两回事。
其次，你恰恰搞反了，递归调用的函数显然一般不是“逆向思维”。递归函数往往是问题的解的直接描述，因为所有可计算问题的解和求解过程都能用递归函数表示，进而对应到递归的（过程）调用上——只不过有些语言原生对递归调用有限制或者实现起来低效所以才有必要变通。反过来，只有少数问题才有一眼就能看出特殊形式的递归（等价于递推）关系的解，其它问题的解都需要用逆向思维把一般递归函数的解转换为这类特殊递归函数。
这种特殊递归形式称为尾递归(tail recursion) ，计算复杂度等价于循环。本质上，把一般递归形式的解变换为尾递归的解和优化为循环形式的解是相同的过程，只不过用来表达结果的语言使用的具体实现形式不同（尾调用或者循环关键字）。
如果在乎的是算法或者一般的解的结构，这里的区别可以无视；不过你至少需要知道，在只有循环关键字而没有一般尾调用和一等续延(first-class continuation) 支持的语言中，直接表达这类特殊递归的形式的解是无能的，遇到一些典型问题（如遍历一个没有退化成线性表的树的回溯(backtracking) 算法）如果不用原生递归调用，可移植的实现方式就只有显式做CPS变换(continuation-passing style transformation)改写代码暴露活动记录(activation record) 为调用的参数。反过来，对支持这样的特性或者一些在这个问题上至少使用起来有同等能力的特性（比如某些语言的monad或者computational expressions）的语言来讲，你就不需要做这种人肉编译器的体力活，因为这种操作是语言实现的分内事，并且编译器可以用不可移植的手段使用比CPS变换更有效率的方式。很不幸，至少在P0534被接受之前，C++是前者。后者的主要代表是Scheme、Haskell、F#等所谓FP语言。
首先你搞错了概念，递归函数是递归论研究的计算对象，一般（μ-）递归函数跟图灵机可计算性等价。递归调用跟递归函数是两回事。
其次，你恰恰搞反了，递归调用的函数显然一般不是“逆向思维”。递归函数往往是问题的解的直接描述，因为所有可计算问题的解和求解过程都能用递归函数表示，进而对应到递归的（过程）调用上——只不过有些语言原生对递归调用有限制或者实现起来低效所以才有必要变通。反过来，只有少数问题才有一眼就能看出特殊形式的递归（等价于递推）关系的解，其它问题的解都需要用逆向思维把一般递归函数的解转换为这类特殊递归函数。
这种特殊递归形式称为尾递归(tail recursion) ，计算复杂度等价于循环。本质上，把一般递归形式的解变换为尾递归的解和优化为循环形式的解是相同的过程，只不过用来表达结果的语言使用的具体实现形式不同（尾调用或者循环关键字）。
如果在乎的是算法或者一般的解的结构，这里的区别可以无视；不过你至少需要知道，在只有循环关键字而没有一般尾调用和一等续延(first-class continuation) 支持的语言中，直接表达这类特殊递归的形式的解是无能的，遇到一些典型问题（如遍历一个没有退化成线性表的树的回溯(backtracking) 算法）如果不用原生递归调用，可移植的实现方式就只有显式做CPS变换(continuation-passing style transformation)改写代码暴露活动记录(activation record) 为调用的参数。反过来，对支持这样的特性或者一些在这个问题上至少使用起来有同等能力的特性（比如某些语言的monad或者computational expressions）的语言来讲，你就不需要做这种人肉编译器的体力活，因为这种操作是语言实现的分内事，并且编译器可以用不可移植的手段使用比CPS变换更有效率的方式。很不幸，至少在P0534被接受之前，C++是前者。后者的主要代表是Scheme、Haskell、F#等所谓FP语言。
最后值得一提的是原生递归调用的限制。如果一个语言没有一等续延或者等价表达能力的特性而有足够强大的原生递归调用支持（具体而言，proper tail recursion，如Scheme和ML要求的那样，或者更一般地称为PTC(proper tail call) ），那么就表达问题上可能不是很大（实际可能因为算法复杂度太差而不可用，需要手动改写为循环）。ISO C和ISO C++是这里特别糟糕的例子，因为语言规则不但不要求PTC，还对嵌套调用的深度不做可移植性的保证（注意这不只是递归调用的问题）：任意超出若干深度的调用引起未定义行为，程序是不可移植的。最烂的是，这里嵌套深度没个准，不可能用可移植的方式获得，你只能祈祷任何敢让人用的实现在“日常”操作下都不会出问题。考虑到大部分实用算法无法事先预知深度，只能靠具体实现的安全特性擦屁股，显然正常的工程上完全不靠谱的。
这种语言特性设计的限制是人为的瑕疵(artifacts) ——根源之一即是出于对递归的无知。对C和C++来讲，动机主要是使用体系结构的调用栈，而实现这类特性的ISA设计人员在这方面的理解水平普遍处于20世纪70年代（Scheme刚刚提出一等续延的典型形式之前）的水准，其他人却因为兼容性问题而不得不向愚蠢的设计低头，并且会坑到自己人（例如Intel面对自家产品至少有过两次类似的失败）。对Python这样的非native语言来讲，则是设计者知识水平的无能和面对现实问题的一厢情愿——只是不至于连深度多少都无法预知（保证栈溢出能报错）而能让用户有机会积极地试错，可移植性上的实际效果稍微好那么一点点而已。
这种语言特性设计的限制是人为的瑕疵(artifacts) ——根源之一即是出于对递归的无知。对C和C++来讲，动机主要是使用体系结构的调用栈，而实现这类特性的ISA设计人员在这方面的理解水平普遍处于20世纪70年代（Scheme刚刚提出一等续延的典型形式之前）的水准，其他人却因为兼容性问题而不得不向愚蠢的设计低头，并且会坑到自己人（例如Intel面对自家产品至少有过两次类似的失败）。对Python这样的非native语言来讲，则是设计者知识水平的无能和面对现实问题的一厢情愿——只是不至于连深度多少都无法预知（保证栈溢出能报错）而能让用户有机会积极地试错，可移植性上的实际效果稍微好那么一点点而已。
不感兴趣
开通SVIP免广告
