23Jul/1016
尾递归以及FP
在某朋友的博看到一篇文章，写了两个不同的递归，一个普通递归，一个尾递归。不过他似乎没有意识到尾递归是什么，所以……嗯……很蛋疼的来凑数更了
尾递归，顾名思义，在尾巴上最后递归，和普通递归比起来的好处就是不需要保存上次调用的上下文信息，可以被编译器优化为直接跳转而非方法调用。
public class Test {
// 普通递归
public static long getSum(long max) {
if (max == 0) return max;
return max + getSum(max - 1);
}
// 尾递归
public static long getSum2(long max, long sum) {
if (max == 0) return sum;
return getSum2(max - 1, sum + max);
}
// 可惜Java并没有对尾递归进行优化 看RP就会栈溢出
public static void main(String[] args) {
System.out.println(getSum(6400L));
System.out.println(getSum2(6400L, 0L));
}
}
上面两个方法都是求和，普通递归方法在每次递归调用返回之后都需要再做一步加法操作，所以必须保存调用栈和上下文。但是尾递归把所有的东西都一起传给了下一次递归调用，因此这次调用的上下文就已经无用了，编译器可以直接无视它们……
只不过这还是要仰仗于编译器大发慈悲……比如说Java、C#、python、Groovy（这货就是Java嘛）都没有尾递归优化（一般FP语言就会有，因为FP语言没有变量，所以循环往往只能用递归，嗯……这就是标题里出现FP的原因）。那没有尾递归优化怎么办呢，我们有循环嘛。递归就是很多人合作做一件事，事没做完谁都别想走；尾递归也是很多人合作做一件事，但是每个人做完之后就没有人care他的死活了；循环呢……就是只有一个苦命人要做事……
另附上蛋疼Groovy尾递归一段：
static sum(a, b={it}) {
if (a==1) return b(1);
return sum(a-1, {c -> b(a + c)});
}
sum(100)
那么，最后还是顺便说下FP吧……FP是什么呢，FP就是
// 我是Groovy
// 命令式计算(x+4)^2
static func(x) {
x = x + 4
x = x * x
}
// 我还是Groovy
// FP式计算(x+4)^2
func = {a->{b->b*b}(a+4)}
July 23rd, 2010 - 20:10
于是哥来吐槽了，难道大家都经常忘记等差数列求和公式么~~
July 23rd, 2010 - 20:13
那是什么东西，我表示忘了o(︶︿︶)o
July 23rd, 2010 - 20:19
放狗搜之~
FP什么的，最看不懂了。
July 23rd, 2010 - 20:26
争当学院派啊
July 23rd, 2010 - 21:46
[code lang="c"]
/*桃子的问题
1毛钱可以买一个桃子，每3个桃核可以换一个桃
问n元钱总共可以吃到多少个桃子
Author:jason
Date:2006.12.23
来源于群中的一个脑筋急转弯的问题。可用递归算法实现
*/
#include "stdio.h";
#include "math.h";
int core(int n,int sum);
void main()
{
int n,money;
int sum;
printf("please input the number of the money: ");
scanf("%d",&money);
n=money*10;
sum=n;
sum=core(n,sum);
printf("The number of the peach:%d",sum);
getch();
}
int core(int n,int sum)
{
int tmp;
while(n>=3)
{
tmp=n/3;
if((n%3)==0)
n=tmp;
else
n=tmp+sum%3;
sum=sum+tmp;
core(n,sum);
}
return sum;
}
[/code]
我竟然在硬盘里发现了这个。。
July 23rd, 2010 - 21:48
[code lang="c"]
int Febc(int n)
{
if(n<=3) return (1);
else return (Febc(n-1)+Febc(n-2));
}
int main(int n)
{
printf(";input the value of N: ";);
scanf(";%d";,&n);
printf(";Febc(%d)=%d";,n,Febc(n));
getch();
}
[/code]
还有这个=。=貌似都是当初学C语言时留下的东西
July 23rd, 2010 - 21:49
尴尬的大于号和小于号。
July 23rd, 2010 - 22:02
这插件调教的好累…
July 23rd, 2010 - 22:05
code插件？
July 23rd, 2010 - 22:08
擦，忘了换号就回了。
你不觉得现在的code比原来拉轰多了么~~~
July 23rd, 2010 - 22:12
各种拉轰啊，不过我倒觉得前几天那个色更好看，更有vim的感觉~
July 23rd, 2010 - 22:19
那必须，哥一点一滴的调教的。不过哥也不知道那是什么风格，反正哥的VS就是那风格~~
July 23rd, 2010 - 23:01
你是administrator啊 干嘛要用我的号调教……
July 24th, 2010 - 13:06
哥的号在后台会被莫名其妙的重置╯_╰
July 24th, 2010 - 13:28
那个貌似是RPWT，你先随便点一个带参数的动态链接就好了……
July 24th, 2010 - 14:50
我的不会被重置，但是貌似会出现warning