尾递归还是伪递归，关于老赵blog的一点评论
--------------------编程问答-------------------- 1L预留，用于补充内容。。。--------------------编程问答-------------------- 大染缸高碳钢人认同 --------------------编程问答-------------------- 我在帖子《读取txt内容，并以树状形式显示》贴出的代码（#12楼）中的“插入”方法就是尾递归的。但是我认为这个更自然，真正直接了当地反映我这个人的思路，所以我没有特殊原因不会费那个时间去给成循环——因为修改它也提供不了一毛钱价值。
可能认得思路不同。有的人喜欢凑数，有的人喜欢分析。喜欢分析思路的人首先写出递归的程序，然后只有必要时才考虑修改为迭代程序。 --------------------编程问答--------------------
--------------------编程问答--------------------
不要笑！我不是否定这种重要的“尾递归优化技术”思路。如果只会笑，我就弄瞎你。不要笑！我不是否定这种重要的“尾递归优化技术”思路。是就事论事说那个程序本身，是提供一种另外的编程经历而已。 --------------------编程问答-------------------- 把斐波那契写成递归本身就是一个引人嘲笑的做法……
--------------------编程问答-------------------- 进来看看
--------------------编程问答--------------------
Tail RecursionA recursive function is said to be tail recursive if all recursive calls within it are tail recursive. A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it.
When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.
--------------------编程问答-------------------- 上次我说的 编译器可以把递归优化成尾递归 sorry
This characteristic is important because most modern compilers automatically generate code to take advantage of it.
这句话理解错了 --------------------编程问答--------------------
--------------------编程问答--------------------
http://www.cnblogs.com/carter2000/archive/2012/04/19/2458018.html
--------------------编程问答--------------------
--------------------编程问答--------------------
除
--------------------编程问答--------------------
--------------------编程问答--------------------
原谅我吧！
--------------------编程问答--------------------
话说老赵的blog早就不在cnblogs上更新了有时间会去他自己搭建的blog上看看 --------------------编程问答-------------------- 先收藏了，等考试完再看看 --------------------编程问答-------------------- 除 --------------------编程问答--------------------
写的真长，改天看 --------------------编程问答-------------------- 只会循环迭代的飘过。。
--------------------编程问答--------------------
--------------------编程问答--------------------
把老赵自己的博客地址发来看看啊 --------------------编程问答--------------------
老曹的帖子里面有地址呀：
http://blog.zhaojie.me/ --------------------编程问答--------------------
--------------------编程问答--------------------
去年某人的一篇文章：尾递归本质论
也提到了递归求解斐波那契第n项 --------------------编程问答-------------------- 多谢分享。。。。。。。 --------------------编程问答--------------------
我想强调的是，如果既然你已经写出了尾递归，不如干脆写出循环，看着更直观（在非函数式编程思维/范式中），或者说，如果你找不到有效的办法把递归改写成循环（不用递归），那么即便你知道所谓尾递归多么简洁高效，也是白扯，因为根本没有把递归转换为尾递归的方法。尾递归的本质就是不用递归。 --------------------编程问答-------------------- 我赶脚。。仅限赶脚。。
尾递归啥的就它本身来讲就是个无意义的笑话，就是个“理论叫”。。因为在把一般递归转成尾递归的过程中，你已经完成了从“递归->迭代”的这个过程，所以你压根就不需要再来个“画蛇添足”的尾递归。。
就我的理解，尾递归，tial这个名词的意义在于指出了“递归->迭代”的一种可行的方法：想尽一切办法把递归调用往最后面挤。。其他的什么XXOO的。。别想太多。。
另外，躺枪的fibonacci是迭代定义的，而不是递归。。hanoi tower、树和图都是递归定义的，哪位蛋疼的话不妨整几个尾递归版来爽爽。。
--------------------编程问答--------------------
你理解了我的意思。
顺便指出，尾递归还是有意义的，那就是将程序改写成CPS风格的时候，可以说，尾递归为老赵后续的讲解提供了基础知识。但是老赵忽略的恰恰是这个，他没有深究，而是对尾递归做了不恰当的演绎。 --------------------编程问答--------------------
树也是可以尾递归的（这里说的可以是指不用栈，利用树本身作为回溯状态的存储，用当前节点作为游标，因此并不违反我说的，如果要把递归改写成尾递归（不更换算法），需要额外存储/堆栈模拟/额外计算的原则）。 --------------------编程问答--------------------
我赶脚就是新瓶装旧酒。。理想情况下，所有的递归都能变迭代，方法大把。。那么尾递归跑个龙套也无伤大雅。。。另外。。 --------------------编程问答-------------------- 多谢大大分享 --------------------编程问答-------------------- 学习。学习。 --------------------编程问答-------------------- learning. --------------------编程问答--------------------
public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
c2++;
if (n == 0) return acc1;
return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}
其实这种风格的递归化递归，也不需要一步一步去变换，函数式编程的思路就是把中间结果写到状态里面。
#--------------------------
但还有一个常见的思路，就是考虑当前这一个和以后所有的，
x:xs表示取列表第一个元素是x，后面的元素的列表是xs，xs可以为空:
例如求列表长度，就是1加上去掉第一个元素以后剩下列表的长度（与循环的思路无关）
len [] = 0
len (x:xs) = 1 + len xs
这个熟悉了就不需要从循环去考虑，如果为空，那就是0，否则取一个元素，对剩下的取len递归。
同理也可以有sum:
对所有元素求和就是第一个元素加上对剩下元素的求和（与循环的思路无关）
sum [] = 0
sum (x:xs) = x + sum xs
甚至有乘法和幂：
（只处理自然数乘法和幂）
mul a 0 = 0
mul a n
| n > 0 = a + mul a (n-1)
| otherwise = error "..."
power a 0 = 1
power a n
| n > 0 = a * power a (n-1)
| otherwise = error "..."
同理max也可以这么看:
对所有元素求最大值就是第一个元素与对剩下元素求最大值，两者取较大的
首先nummax是两个数取最大值:
nummax a b
| a > b = a
| otherwise = b
max [] = error "..."
max [x] = x
max (x:xs) = nummax x (max xs)
这些都可以当做某些编程语言的reduce/inject/fold的展开来看。
最后是fibonacci，fibonacci并不只是单纯的一个数在递推，是两个数，但两个数也可以是一个元素：
这是我们刚看到的形式
fibonacci 0 a b = b
fibonacci n a b = fibonacci (n-1) b (a+b)
你说这个形式与前面说的x:xs有什么关系呢？
其实可以变换一下
[a, b] => [b, a+b]实际上相当于向量[a, b]乘上一个2x2矩阵:[0 1; 1 1]，矩阵排版容易乱，因此就用matlab的方式，分号表示换行了。所以[a, b]要递推N次，就相当于乘上[0 1; 1 1]的N次幂：
前面幂乘法我们可以写成下面的形式:
power u 0 = 1
power u n
| n > 0 = power u (n-1) * u
| otherwise = error "..."
现在我们把这个u定死写成[a, b]的形式, 假设不会出现n < 0或者非整数的情况：
power 0 = [a, b]
power n = power (n-1) * [a, b]
这个乘号还是意义不明的，下面继续展开：
fibonacci的定义延伸：如果第[n-2, n-1]个数写成[a,b]那么第[n-1, n]个数就是[b, a+b]
所以:
power (n-1) = [a,b]
power n = power (n-1) * u 也就等于[b, a+b]
我们写成:
power 0 = [1, 1]
power n = [b, a+b] where [a,b] = power (n-1)
这样就十分清晰了，而且也正是fibonacci的延伸定义。
最后，用一个fib把第二个数取出来:
power 0 = [1, 1]
power n = [b, a+b] where [a,b] = power (n-1)
fibonacci n = head(tail(power n))
瞧，我们也可以不需要循环来帮助思维
--------------------编程问答-------------------- 如果说不关心算法只关心代码的话:
平时是:(2的幂数列)
本来是result = power2(n)
现在写成result = power2(n, result):
于是fibnacchi本来是
result = fib(n) = this(n-1) + this(n-2) (this = fib)
看这个代码发现是递归数列的相邻两项，因此拿两项作为递推状态。
现在写成result = fib(n, result1, result)
--------------------编程问答-------------------- 顺便一说先序遍历可以用另一种思路写的，伪码：
调用是order(root, 1)
为什么说这个是尾递归呢，
如果把下文的每一处return preorder(a,b)
都换成 node = a, time = b; 并goto start的话
不影响结果，事实上编译器产生尾递归代码的一种方式就是替换参数并使用goto/jmp：
def preorder(node, time)--------------------编程问答-------------------- 没有看上面的帖子，我只是看了#36、#37两层楼。我想有一点补充介绍，或许上面有所重复：
# start:
if time == 0
输出当前
return preorder(node, 1)
end
if time == 1
if node左儿子存在
return preorder(node左儿子, 0)
end
end
if time == 2
if node右儿子存在
return preorder(node右儿子, 0)
end
end
if time == 3
if node是父亲的左儿子且父亲有右儿子
return preorder(node父亲, 2) #对应上面time == 2的情况
else
return preorder(node父亲, 3)
end
end
end
1. 对于传统的函数式编程语言（例如prolog），就算是有自动化地堆栈迭代机制，往往程序设计者也会手动去设计迭代程序。其做法就是在参数上增加一个“累计器”，就好像#36楼的 fib(n, result1, result) 类似。加入“累计器”的目的，是吧原本“自顶向下分析”的程序变为“从初始状态开始，自底向上累计”的方式的程序。
2. 实际上对于 fib 这类程序，因为假设我们把“曾经计算过的”n对应的值记录到一个static的数据集合中，那么 fib(n-1)就可以立刻使用fib(n-2)的值直接计算出来，而根本不需要重复计算fib(n-2)。因此只要把公式重新改写为
fib(n) = fib(n-2) + fib(n-1)
并且每一次计算出fib(n)之后不要扔掉结果而是缓存起来，那么递归写法中的所谓fib(n-1)的递归深度根本就不是等于1，根本无需担心。 --------------------编程问答-------------------- 递归深度根本就不是等于1 --> 递归深度根本就不会大于1
由于缓存很有用，甚至即使是缓存几秒钟也很有用，因此我们可以不必太在意重写程序算法的工作，而是先研究如何大量利用缓存的技术。 --------------------编程问答-------------------- 其实，突然又觉得，原本fib(n) = fib(n-1) + fib(n-2)是递推形式。
但是：如果写成下面的形式，就不像递推了，而仅仅是一个数的不同表示，就像16 = 0x10 = 020 = 0b10000，我们只是把Fibonacci数的单个十进制数表示法从这些状态里面求出来，但你求不求这个值，他仍然是原来的意义：
fib(k, n, a, b) = fib(n, n, a, b) = fib(n, n-1, b, a+b) = ... = fib(n, 0, Fib(n-1), Fib(n))
比如
fib(6, 6, 1, 1) = fib(6, 5, 1, 2) = ... = fib(6, 0, 11, 13) (= 13)
其实这些状态之间都是等价的。。没有所谓求值，这也可以看做是函数式编程提到的懒惰特性吧。
--------------------编程问答-------------------- 如果用了 yield return 非递归实现就更简单了。 --------------------编程问答-------------------- 来学习开眼界了！ --------------------编程问答--------------------
--------------------编程问答--------------------
http://www.abab123.com/bbs/down.asp?html=1787680
--------------------编程问答--------------------
多谢分享。。。。。。。
--------------------编程问答--------------------
吓着我了。。 --------------------编程问答-------------------- 蛋疼。。又来了。。扯扯淡。。和主题无关。。
斐波纳契数列最早是用“兔子繁殖”这个例子引出来的，所以它的计算方式应该是fib(n+2)=fib(n)+fib(n+1) （n>=1），你只能迭代推算子代，而不应该去倒推父代。。可是自从某个不负责任的家伙为了思考/计算方便，把它改写成了fib(n)=fib(n-1)+fib(n-2) （n>=3)之后，又被某个不刨根问底的家伙加以理解，就成了“递归的”fibonacci了。。于是在数学上，原本好好的迭代，生生的被改成了递归。。。
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
学习
--------------------编程问答--------------------
看了47楼后 他的意思是f(n+2)=f(n)+f(n+1) 和f(n)=f(n-2)+f(n-1)是两个不同的递推关系。元芳，你怎么看？ --------------------编程问答--------------------
打酱油的吧！
--------------------编程问答--------------------
进来看看 
--------------------编程问答--------------------
好文，来看看
--------------------编程问答--------------------
来学习开眼界了！
--------------------编程问答--------------------
看看，学习下，感觉还是依靠编译器吧，既然如此不如直接用使用循环消除递归喽？？
--------------------编程问答--------------------
空间复杂度O(n)的算法强行修改成尾递归，就是自欺欺人，吃饱了没事做。有一点不同意楼主，我个人认为，一般情况下递归程序更易读，运行效率也比数组(或其他)模拟栈要好。 --------------------编程问答--------------------
当然使用递归有个前提，递归深度需要可控。 --------------------编程问答-------------------- 他在结语中提到了：
所以，尾递归是在无法使用循环的时候去使用的。另外有一点必须清楚，IL代码中，也是无法使用循环的，包括汇编也是，都不存在循环这个概念，它们都是使用的条件判断+跳转，如此复杂的逻辑和尾递归相比的话，现在优势就体现出来了。 --------------------编程问答--------------------
学生，鉴定完毕！ --------------------编程问答-------------------- 除 --------------------编程问答-------------------- “给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出
http://attachment:/1/How-to-replace-recursive-functions-using-stack-and.htm --------------------编程问答-------------------- 纠正上帖链接：
http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and --------------------编程问答-------------------- 其实所谓的模拟栈消除递归，和协程(coroutine)/延续(continuation)没多大不同，一个是手动的，一个是语言实现支持的
一个简单的通用例子，可以参考这里：
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html --------------------编程问答-------------------- 看博文加自己敲都花了4个小时...再看回版主的讲解...感觉又上了一课了..
"尾递归和循环则是等价的"..这句话我非常赞同..就像第一个例子的那个尾递归..其实就是把循环给"递归化"了..
"尾递归和递归没有可比性"..但我只感觉是绝大部分的情况下没可比性吧..像现在的这些例子..感觉就是最好的对比了.. --------------------编程问答--------------------
额。。。。。很明显嘛。。
--------------------编程问答--------------------
--------------------编程问答--------------------
哇 都是牛人啊
--------------------编程问答--------------------
学习，
--------------------编程问答--------------------
习惯函数式的编程方式，有些算法想将之转化为尾递归，或者取消递归用循环实现，基本等同于重写一次····还不一定写的好。
我不用递归写出来的东西感觉可读性很糟糕，可能是自己还没适应吧，努力学习··· --------------------编程问答--------------------
用协程式的消除递归，和普通的递归写法很像，只是return的地方做了处理，大可不必每个递归程序都用独特的改写方法，可以用同一种通用的方法的，见http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html --------------------编程问答--------------------
public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
c2++;
if (n == 0) return acc1;
return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}
为了计算出N的裴波那切数，必须先计算出N-1和N-2的裴波那契数，然而从上面代码的参数分配上，完全无法理解acc1和acc2与n的关系，acc1原意是想说的N-1的值，acc2是N-2的值，从调用中FibonacciTailRecursively(10,0,1)来看，acc1和acc2的参数使人无法理解。这段代码的理解是：为了求Fib(N),必须先求fib(0)和fib(1)，因为参数传递的就是fib(0)和fib(1)的值,然后再求fib(1)和fib(2),最后求fib(N-1)和fib(N-2)，这里根本就是把一个for循环的变量强行放置到函数参数的位置上而已，n的值就是个循环控制变量。
static int Max(int[] source, int max, int i)
{
if (i >= source.Length) return max;
if (max < source[i]) max = source[i];
i++;
return Max(source, max, i);
}
上面这段代码依然使人无法理解，很显然这里应该这么调用Max函数，Max(source,0,0);这里应该是这么理解这段代码的：为了求出source[N]的最大值，不得不先求出source[0-0]的最大值，然后再求出source[0-1]的最大值，然后再求出source[0-2]的最大值，最后才求出source[0-N]的最大值。以及函数参数max的意图是为了存储一个变量。
可以说，这样的代码不是一个严格的递归调用，只是强行使用递归而凑的一个循环而已。
假设递归求取多重指针的值，char ********p的值，********p这个该怎么求取。
这样的求法是，为了求N重指针的值,必须先求出N-1重指针的值*(*******p),这里的递归其本质就是一个自右向左结合的一个表达式，递归的本质是倒退求解问题的，把递归使用成正向前进的一个循环是说不通的。 --------------------编程问答-------------------- 虽然看不懂，支持一下 --------------------编程问答-------------------- 太牛了，看来这个网站只适合你们。 --------------------编程问答-------------------- 除 --------------------编程问答-------------------- 顶一个。。。 --------------------编程问答-------------------- 不错，有达人在讨论算法 --------------------编程问答--------------------
我不太了解，但是，我看到了一条，尾递归可以避免发生堆栈溢出。。。
节约函数调用的开销和资源。。。
--------------------编程问答-------------------- 递归分为形式上的递归和算法上的递归。
基本上能用循环实现的算法，都能实现为形式上的尾递归。
真正的递归算法，直接用循环是做不了的，要用栈辅助。这种是形式上的循环，算法上的递归。 --------------------编程问答-------------------- 学习啦，都是高手 --------------------编程问答-------------------- mark.... --------------------编程问答-------------------- 射了
--------------------编程问答--------------------
与强行凑循环没关系。。如果你通过循环这个概念到达递归的形式，但不能说就必须通过循环这个概念到达递归的形式，
直接从问题到递归不经过循环也是可以的，见40楼的讨论。。 --------------------编程问答-------------------- 路过
--------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
除
--------------------编程问答--------------------
从上面一系列的改进中，基本就知道了算法优化的思路跟过程了，好好学习这种分析方法，谢谢！
补充：.NET技术 , C#
