---

天天看丧气话，搞得整个人都丧了，那个令人丧气的文章就在下面
引文：字节跳动——面试by民工哥技术之路
作为年轻人，不管去哪面软件，总是有公司爱问算法，真是让人脑壳疼。想了想当初大学里自己算法也算是系统学习考试过，该拿出来装装逼了（复习一下）。

算法的基础就不在这里详述了（虽然其实算法很多概念有详细理念），开始！（备注：本系列语言不限，你有可能看到python？c++？c#？java?甚至shell?js?因为算法是基础，语言不应该是限制算法的理由，虽然肯定是用c算法效率最高。。。）

用数学的思想解析算法题

小时候，数学大题正常有三种：证明题、计算题、应用题。当然还有个几何题，不过这个有点高深，不混为一谈了。算法也是这样，连难度都有点类似：应用题>=证明题>计算题。有很多人可能认为，证明题应该比应用题难啊？想想那时候，最后一题都是证明题，难爆了，每次只能做一小问，ε=(´ο｀*)))唉。针对这个观点，只能说，小伙子（美女！），现实永远比想象复杂多了。从开始从事算法有关开始，就是一个对现实生活建模的开始（有些牛逼的公司已经开始用模型来自动建模了！），成功的建模在常见的两样现代技术中十分常见：第一，大数据的筛选、分析、推举；第二，机器学习的监督式学习、非监督式学习、增强学习。之所以所机器比人更可靠，正是因为如今的机器仍然逃不开模型输入和输出的概念，也正是如此先把自己的机器人恐慌症放到一边吧！O(∩_∩)O哈哈~

第一题：递归OR循环？

说到算法，最可怕的一题就是斐波那契数列了（不是新手噩梦动态规划！！！），说这个之前，我们先看个简单的：

阶乘

什么你说太简单了，给把这个人拖出去打死
递归和循环满足的条件数学意义上一定满足类似如下这种形式，数学上一般叫做数学归纳法。

递归关系

即后一项n一定程度上与前一项n-1或者前几项n-1,n-2......有一定逻辑上的递归关系，所以斐波那契数列我们也可以归纳如下的递归关系：

image.png

求问用递归写斐波那契数列的难度降低了多少？不说难度零星继续拖出！递归的难点完全集中在规律的归纳上面，以后有可能看些难的。

#/usr/bin/python
def count_sd(ass):
    if ass > 2:
        return count_sd(ass-1) + count_sd(ass-2)
    else:
        return 1

number = 10
print(count_sd(number))
#55
#[Finished in 0.1s]
#1,1,2,3,5,8,13,21,34,55

说！大胆的说出来，真的！真的好简单！
好！对不起，用递归写斐波那契数列先扣五分。此处备注一条极难考试题，作者也不知道答案：用递归写斐波那契数列算法的空间复杂度(2^n)和时间复杂度(n)。

递归的时间复杂度/空间复杂度
如上图所示，假设我们要算第五个斐波那契数列，我们莫名其妙的算过两次第三个斐波那契数列的值，不得不说这是一种对效能的极大浪费（同时也会去炸运存，因为递归的特殊性。递归的上一层f(n)是被压栈了，要等f(n-1)和f(n-2)运算出来，才会把f(n)占用的内存空间释放出来，如果层数过多，可能会，啧啧啧。打住，顶多报错吗），这两种问题直接给递归打上了劲看不禁用的标签，但是递归的简单还是在只涉及f(n)与f(n-1)关系有着很大的应用。

补充：其实是有优化空间的，而重点就是把原来递归的一化二，改为一化一，并且借助编译器自身的优化能力(教训：python编译器默认没有此类优化)，弥补此上的两种缺陷，那就是尾递归：

#/usr/bin/c#
#c++还没装好。。。连用两个c#
using System;

namespace ConsoleApp1
{
    /*逻辑是啥？第三个数字等于第二个数字加上第一个数字
     *用n来记录循环的次数
     *用另外两个参数记录f(n)和f(n-1)的值
     *此时其实可以发现，计算过程正过来了，不像原来的递归从f(n)开始计算了，而是先retrun Fib(1,2,5),再return Fib(2,3,4),一直递归下去。大多数语言对尾递归的优化也是基于这一点：上一层递归return的值是已知状态，就不需要保存上一层的状态了，释放了堆栈的压力(其实就是变成循环了。。。)。
     *尾递归可以参照如下的优化方式：比如递归sum(n) = f(n) = f(n-1) + value(n) ;而使用尾递归f(n, sum) = f(n-1, sum+value(n));
     */

    class Program
    {
        static void Main(string[] args)
        {
            int n = 6;
            long ret = Fib(1, 1, n);
            Console.WriteLine("Hello World!"+ ret);
            Console.ReadKey();
        }
        static long Fib(long first, long second, long n)
        {
            if (n < 3)
                return second;
            return Fib(second, second+first,n-1);
        }
    }
}

尾递归函数是指函数的最后一个动作是调用函数本身的递归函数(习题：阶乘转化为尾递归)

可以，既然递归阵亡了，让循环上场吧

#/usr/bin/c#
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 6;
            long ret = Fib(1, 1, n);
            Console.WriteLine("Hello World!"+ ret);
            Console.ReadKey();
        }
        static long Fib(long first, long second, long n)
        {
            long third = 0;
#不解释
            if (n < 3)
                return 1;
    /*逻辑是啥？第三个数字等于第二个数字加上第一个数字
     *所以要算出第三个数字，并把现在的第三个数字存为第二个数字，原第二个数字存为第一个数字
     *这样下一个循环就可以遍历前一句话了
     */
            while (n > 3)
            {
                long temp = second;
                second = first + second;
                first = temp;
                n--;
            }
            third = first + second;
            return third;
        }
    }
}

可怕，只是简单的换为循环就不止要我们去理解原先的公式了，还要去想逻辑，从而保证逻辑链不会断掉。这里我们保证逻辑链不断的方法是将f(n－1)和f(n－2)的状态赋值给f(n)和f(n－1)以维继循环。

第一章就此结束