It turns out that the Fibonacci sequence is also written this way, did you know?

There are many answers to "Non-recursive writing of Fibonacci" on Baidu, but they are not satisfactory. Firstly, it is too difficult to understand, and secondly, the performance is similar to that of recursion.

When it comes to the Fibonacci sequence, whether you are a novice programmer or a technical veteran, the first thing that comes to mind is definitely the recursive writing method. Then, the difference between technical veterans and program novices is that they will think of saving the results of recursion to reduce repeated calculations. These are very common operations, but have you ever thought that the Fibonacci sequence can also be written in a non-recursive way?
There are many answers to "Non-recursive writing of Fibonacci" on Baidu, but they are not satisfactory. Firstly, it is too difficult to understand, and secondly, the performance is similar to that of recursion. At the beginning, I also wanted to write one myself, as long as it simulates the call stack of recursive calls, but this idea is a bit taken for granted, and the program written is also very complicated. How to do it? At this time, Depth-first traversal of the tree can come in handy.
First, we define the tree nodes:

public class Node
        {
            public Node(long value, bool visited)
            {
                Value = value;
                Visited = visited;
            }

            public long Value { get; set; }//存放结点的值
            public bool Visited { get; set; }
        }

Then, we can happily learn how to write the stack of 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;
        }

The core idea of ​​the above algorithm is to traverse the stack and pop out the stack If the top element has been visited (visited is true), skip it (the above code uses the optimization of saving subtree results, there will be a special case to be handled, which will be detailed below); otherwise, the current parent node The visited mark is true, which means it has been visited and pushed to the stack; then all its child nodes are pushed to the stack.

If you follow this idea, the code you write will not look like the one above. The amount of code will be much smaller and more concise. However, the complexity of the algorithm will be similar to that of recursive writing because there will be repeated calculations.

What should we do? There is only one solution. Exchange space for time and store the results of the subtree. If the corresponding subtree has been calculated and has results, we will no longer traverse the depth of the next layer. Use the results directly. We save the subtree results in an array:

long[] childrenResultMemo = new long[n+1];

Usually if the subtree already has results, logically it should have been visited. However, there are special cases, which are subtree 0 and subtree 1 at the beginning:

childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;

Just add the results in the branch of this special case:

sum += childrenResultMemo[cur.Value];

How about this way of writing? rarely seen? In fact, the evaluation process of the Fibonacci sequence is like a depth-first traversal of the tree. So as long as it is the implementation of depth-first traversal, it is completely feasible.

Related articles:

Python prints Fibonacci sequence examples

PHP implements Fibonacci sequence

Related videos:

Data Structure Adventure—Queue Chapter

The above is the detailed content of It turns out that the Fibonacci sequence is also written this way, did you know?. For more information, please follow other related articles on the PHP Chinese website!