用平方递归写斐波那契数列的算法思想

平方递归指的是一种优化递归算法的方法，可以有效地降低递归的深度和运算次数。用平方递归写斐波那契数列的算法思想是：通过降低递归深度和运算次数来提高算法的效率。

具体来说，平方递归是一种分治算法，将原问题分解成若干个相同的子问题，然后通过递归的方式分别解决每个子问题，最后将子问题的解合并起来得到原问题的解。在斐波那契数列的问题中，可以采用平方递归的方式来实现。

平方递归实现斐波那契数列的方法如下：

1. 如果n为0，返回0；
2. 如果n为1，返回1；
3. 如果n为偶数，则递归计算fib(n/2)，然后计算fib(n)=2*fib(n/2-1)+fib(n/2)；
4. 如果n为奇数，则递归计算fib((n-1)/2)和fib((n+1)/2)，然后计算fib(n)=fib((n-1)/2)+fib((n+1)/2)。

需要注意的是，平方递归的时间复杂度是O(log n)，比朴素递归的时间复杂度O(2^n)要快很多，但是仍然不如迭代实现的时间复杂度O(n)快。