Tail Recursion A 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. 这句话理解错了
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 = bmax [] = 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))瞧，我们也可以不需要循环来帮助思维
顺便一说先序遍历可以用另一种思路写的，伪码： 调用是order(root, 1) 为什么说这个是尾递归呢，如果把下文的每一处return preorder(a,b) 都换成 node = a, time = b; 并goto start的话 不影响结果，事实上编译器产生尾递归代码的一种方式就是替换参数并使用goto/jmp：def preorder(node, time) # 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
A 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.
This characteristic is important because most modern compilers automatically generate code to take advantage of it.
这句话理解错了
有时间会去他自己搭建的blog上看看
老曹的帖子里面有地址呀：
http://blog.zhaojie.me/
尾递归啥的就它本身来讲就是个无意义的笑话，就是个“理论叫”。。因为在把一般递归转成尾递归的过程中，你已经完成了从“递归->迭代”的这个过程，所以你压根就不需要再来个“画蛇添足”的尾递归。。
就我的理解，尾递归，tial这个名词的意义在于指出了“递归->迭代”的一种可行的方法：想尽一切办法把递归调用往最后面挤。。其他的什么XXOO的。。别想太多。。
另外，躺枪的fibonacci是迭代定义的，而不是递归。。hanoi tower、树和图都是递归定义的，哪位蛋疼的话不妨整几个尾递归版来爽爽。。
你理解了我的意思。顺便指出，尾递归还是有意义的，那就是将程序改写成CPS风格的时候，可以说，尾递归为老赵后续的讲解提供了基础知识。但是老赵忽略的恰恰是这个，他没有深究，而是对尾递归做了不恰当的演绎。
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 = bmax [] = 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))瞧，我们也可以不需要循环来帮助思维
本来是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)
# 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
fib(n) = fib(n-2) + fib(n-1)
并且每一次计算出fib(n)之后不要扔掉结果而是缓存起来，那么递归写法中的所谓fib(n-1)的递归深度根本就不是等于1，根本无需担心。
fib(6, 6, 1, 1) = fib(6, 5, 1, 2) = ... = fib(6, 0, 11, 13) (= 13)其实这些状态之间都是等价的。。没有所谓求值，这也可以看做是函数式编程提到的懒惰特性吧。
斐波纳契数列最早是用“兔子繁殖”这个例子引出来的，所以它的计算方式应该是fib(n+2)=fib(n)+fib(n+1) （n>=1），你只能迭代推算子代，而不应该去倒推父代。。可是自从某个不负责任的家伙为了思考/计算方便，把它改写成了fib(n)=fib(n-1)+fib(n-2) （n>=3)之后，又被某个不刨根问底的家伙加以理解，就成了“递归的”fibonacci了。。于是在数学上，原本好好的迭代，生生的被改成了递归