erlang的斐波那契数列
【递归和循环】
题目：
大家都知道斐波那契数列，现在要求输入一个整数N，请输出斐波那契数列的第N项，以及前N项。 如：N <=39
下面是斐波那契数列的实现：
-module(feibo). -export([feibo_list/1,ele/1]). %% 运行：feibo:feibo_list(5). %% 结果示例：【1,1,2,3,5】 %% 函数element主要为了计算斐波那契数列的第N个元素 ele(1) -> 1; ele(2) -> 1; ele(N) -> ele(N-1) + ele(N-2). %% 给定一个N，求出斐波那契的前N个数 feibo_list(N) -> feibo_list([], N). feibo_list(L, 0) -> L; feibo_list(L, N) -> feibo_list([ele(N)|L], N-1).
典型的数学归纳法，递归算法。
下面是尾递归的实现。运行时间和效率远远高于上面递归算法。可以timer:tc/3自测
-module(fib).
-compile(export_all).
%%尾递归
getfib(N,X,Y) when N<3 ->
Y;
getfib(N,X,Y) ->
getfib(N-1,Y,X+Y).
尾递归相比递归的好处，一次压栈出栈，防止栈爆掉。
问题引申和扩展：
[跳台阶] [题目] 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 [解析] 与斐波那契数列的求解过程类似。典型的动态规划问题。对于第 n 级台阶， 我们可以从第 n-1 级台阶一步到达，也可以从第 n-2 级台阶一步达到， 则有递归式：f[n] = f[n-1] + f[n-2]， 初始状态 f[1] = 1, f[2] = 2。