一说到斐波拉契数列，无论是顺序菜鸟，照样手艺熟手，起首想到的，肯定是递归写法。然后，手艺熟手与顺序菜鸟差别的处所，就是会想到将递归的效果存起来以削减反复盘算。这些都是些很通例的操纵，然则你有无想过，斐波拉契数列还能用非递归的要领来写？
百度下“斐波拉契的非递归写法”，也有不少的答案，然则并不令人满意，起首是太复制难明，其次是机能和递归差不多。一开始我也想本身写个，只需模仿递归挪用的挪用栈不就行了嘛，不过这类主意真是有点想当然了，写出来的顺序也很庞杂。怎么办呢？这时候， 树的深度优先遍历就能够派上用场了。
起首，我们定义树结点：
public class Node
{
public Node(long value, bool visited)
{
Value = value;
Visited = visited;
}
public long Value { get; set; }//寄存结点的值
public bool Visited { get; set; }
}
然后，我们就能够兴奋地上DFS的栈写法啦
public static long Fblc(int n)
{
Stack<Node> s = new Stack<Node>();
s.Push(new Node(n, false));
long sum = 0;
long[] childrenResultMemo = new long[n+1];
childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;
//long children = 0;
while (s.Any())
{
var cur = s.Pop();
if (cur.Visited == false)
{
if (childrenResultMemo[cur.Value] == 0)
{
cur.Visited = true;
if (childrenResultMemo[cur.Value - 1] != 0 && childrenResultMemo[cur.Value - 2] != 0)
{
var result = childrenResultMemo[cur.Value - 1] + childrenResultMemo[cur.Value - 2];
childrenResultMemo[cur.Value] = result;
sum += result;
s.Push(cur);
}
else
{
s.Push(cur);
s.Push(new Node(cur.Value - 1, false));
s.Push(new Node(cur.Value - 2, false));
}
}
else
{
sum += childrenResultMemo[cur.Value];//保留子树效果的优化，会有个特殊情况要处置惩罚
}
}
}
return sum;
}
上述算法的中心头脑是，遍历栈，pop出栈顶元素，假如已访问过（visited为true）,就跳过（上面代码由于采用了保留子树效果的优化，会有个特殊情况要处置惩罚，下文会详述）；不然，将当前父结点的visited标记为true，代表已访问过，并push到栈；然后将其子结点都push到栈。
假如根据这个思绪，写出来的代码不会是上面谁人模样的，代码量少很多也简约很多，不过算法庞杂度就会像递归写法差不多，由于存在反复盘算。
那怎么办呢，解决办法只要一个，空间换时候，将子树的效果存起来，假如对应子树已盘算过有效果，就不再往下一层的深度遍历了，直接运用效果。我们将子树效果保留在了一个数组内里：
long[] childrenResultMemo = new long[n+1];
一般假如子树已有效果，按逻辑来讲应当就会被访问过。不过存在惯例，就是一开始的子树0和子树1：
childrenResultMemo[0] = 1; childrenResultMemo[1] = 1;
只需在这个惯例的分支内里累加效果即可：
sum += childrenResultMemo[cur.Value];
怎样，这类写法是否是很少见？实在斐波拉契数列的求值历程就像是树的深度优先遍历。所以只需是深度优先遍历的完成，完整就是可行的。
相干文章：
Python打印斐波拉契数列实例
PHP完成斐波那契数列
相干视频：
数据结构探险—行列篇
以上就是本来斐波拉契数列另有这类写法，你知道吗？的细致内容，更多请关注ki4网别的相干文章！
