Time Limit Exceeded之短变量声明分析

前言

今天在逛LeetCode的时候，看到了这样一道题目:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

题目意思很简单，就是求斐波那契数列,于是很容易用递归写出如下代码:

func fib(N int) int {
    if N <= 1 {
        return N
    }

    return fib(N - 1) + fib(N - 2)
}

运行正常AC，但想到用递归做的事情，一般都可以用栈来实现，因为递归也可以理解成不断入栈、出栈。
于是很快用栈写出了如下代码:

func fib(N int) int {
    res := 0
    stack := make([]int, 0)
    if N <= 1 {
        return N
    }
    stack = append(stack, N - 1)
    stack = append(stack, N - 2)
    fmt.Println(stack)
    for len(stack) > 0 {
        val, stack := stack[0], stack[1:]
        if val <= 1 {
            res += val
        } else {
            stack = append(stack, val - 1)
            stack = append(stack, val - 2)
        }
    }
    
    return res
}

运行提示Time Limit Exceeded，时间超限一般来说估计是死循环了。当我观察代码时，发现也只有一个用来判断栈是否为空的for循环，该for循环中不断对stack进行push，pop操作，感觉也不会死循环。于是我用GoLand在如下位置打上了断点:

上图很明显看出堆栈中有两个stack。 val, stack := stack[0], stack[1:] 声明了一个作用域为for循环内部的stack，而for循环判断条件中的stack是函数fib作用域中的stack，该stack在for循环中一直没被修改，因此出现了死循环。

而我一开始以为 val, stack := stack[0], stack[1:] 只会新声明一个val，stack会使用外部的stack，因为:=左边只要有一个变量是未被声明的就可以使用它。于是对代码进行了修改，val单独一行声明赋值，代码如下:

func fib(N int) int {
    res := 0
    stack := make([]int, 0)
    if N <= 1 {
        return N
    }
    stack = append(stack, N - 1)
    stack = append(stack, N - 2)
    fmt.Println(stack)
    for len(stack) > 0 {
        val := stack[0]
        stack = stack[1:]
        if val <= 1 {
            res += val
        } else {
            stack = append(stack, val - 1)
            stack = append(stack, val - 2)
        }
    }
    
    return res
}

提交，正常AC。