初级程序员面试不靠谱指南(五)

四、递归的第一次亲密接触

    我经常会想,如果给没有学过计算机或者数学的人说递归这个词他们脑中会怎样理解这个词的意思。递归这个概念在面试中出现的概率大于85%，而他和数据结构、算法那一块的结合更是经常作为考察的重点，所以在还没有写到那里的时候，只能说目前只是第一次的接触。

1.吊丝思维的转换。对于递归，我觉得最精辟的一句话是“这是一种新的思维方式，把一个大问题分解成为很多小问题，并且你要相信，只要规则制定的是正确的，这些小问题就能自然的不断得出正确的结果，从而得到最终大问题的正确结果。”我忘了是在哪本书上看到，可能和原文有些不一样，但是很能表达我的感受。就像我第一次看到汉诺塔问题的解法的时候，我就觉得这样就可以解决了吗？感觉看上去也没有做什么啊，所以说这是一种新的思维方式，你要相信小问题能够自然的被解决，只要你分析的解决问题的规则都是一样且正确的。

在正式讨论递归之前，我觉得我应该再来说一下这种思维方式，因为这也是我花了好大的功夫才解决的一个问题，如果不能有这种思维方式，就会导致一个现象，看递归的代码都可以看懂，但是要自己写的话就写不出来了。一般正常人解决问题的方法肯定是按照某一种顺序一步一步的来，而且都是从底层一步一步的完成向上解决，毕竟大家一般都是吊丝嘛。但是设想一下如果你站在一个宏观的方面，你也许就不会这样解决问题，比如你是一个黑社会老大，要收点保护费啥的，你会不会自己一个一个去收？除非你有特殊的癖好，不然你应该是吩咐你下一层的高管人员去哪里收，怎么收，然后这些人员再一级一级的吩咐下去，规则都不变，直到最底层的罗罗们。这些底层的罗罗们收好钞票之后再一层层的上缴（不管他按什么规则上缴），最后汇总到你这儿。在这个过程中，你需要相信下层人员会按照你制定的规则去收集这些费用，但是不用去考虑细节，这才是有高层风度的做法。所以，在处理递归问题的时候，你要把自己当作一个规则制定者，而不是执行者，相信自己的规则是没有错误的，然后，所有子问题按照自己的规则有序的执行，最终汇总，就能解决自己的问题。

2.C语言的实现方式。C语言中函数实现递归的方法是通过堆栈，而一个线程分配的栈大小往往都是有限的，默认情况下是1MB，这是一个很小的空间，所以说，使用递归所要考虑的重要问题之一就是要保证栈空间不会被全部的消耗。下面这段小程序是为了简单的展示递归是怎样进行的，可以执行一下查看结果。

int MyFunc(int counter) {
    
    if(counter == 0) {
        printf("counter->before:%d,address:%x\r\n", counter,&counter);
        return counter;
    }
    else {
        printf("counter->before:%d,address:%x\r\n", counter,&counter);
        int valueToPrint = MyFunc(counter - 1);
       
		printf("counter->after:%d,address:%x\r\n", counter,&counter);
        printf("valueToPrint->after:%d,address:%x\r\n", valueToPrint,&valueToPrint);

        return counter;
    }
	
}

      其执行结果如下所示：

       可以看到，首先，在每次调用自己之前，函数将四个数依次保存到四个地址之中（堆栈），接着，直到遇到conuter=0,然后函数返回一个值，也就是0，这时候继续执行调用自己后面的语句，从图中的counter的值可以获知是哪一次的继续执行调用后的语句，从valueToPrint也可以获知是哪一次的调用返回。可以看到整个过程大致就是执行---调用 ---执行，所以有人把递归的过程总结为以下的式子 递归 算法=(预处理步骤)(子问题解决调用)(后续处理步骤)，每一个步骤执行结束才能进入下一个步骤。

3.细谈递归步骤。怎么样去用递归的思想解决一个问题呢?我想从一个实际的例子来说明比较容易理解，比如，判断一个字符串是不是回文字符串，回文字符串就是类似”abcba”这种正着看反着看都一样的字符串。如果用常规思想解决，无非就是从第一个字符出发，一直到中间的一个字符，依次判断是否都是相同的，或者类似的解法。这是从微观的方式看待这个问题，而递归就像前面描述的那样，需要你从宏观的方面看待这个问题。如果从两侧开始，每一个子字符串都是回文字符串，那么这个字符串一定就是回文字符串，但是这种关系应该有个终止点，也就是到什么情况下，停止这种判断。如果按照上面的思路，从最长的字符串开始，每判断一次便剥离两侧的字符，那么结束的条件应该是，最后没有字符可以剥离，或者只剩一个字符，很明显，如果能进行到这一步,说明前面的判断都通过了（如果中间某处判断不是回文字符串，那么直接可以以false返回了）。所以，递归的第一步就是：

• 定义递归的终止条件。比如在这个例子中，就是if(strlen(testString)==0|| strlen(testString)==1) IsPalindrome=true.

     在这之后，就需要仔细思考你需要怎么递归了，所以说，第二步就是：

• 仔细的思考和制定解决子问题的规则。首先，你需要能够把原始问题准确的划分为采用同样方法解决的小问题，这些小问题具有的特点就是比原始的大问题更加简单，但是解决方法是一样的。比如上面的回文字符问题，你可能会思考如何划分子字符串，按照这个问题本身的描述方法，明显不能按照类似每次减少字符长度的方法取得字符串。所以，这里也是一个难点，但是也是有一定方法可以遵循的，比如这个问题的逻辑思考方式和第一步就是依次对比头尾字符，那么应该遵循着这个思路，子问题的解决方法也应该是对比头尾字符，这样思考以后，明显，这里的子问题明显就是去掉头尾字符的子字符串判断是否是回文，如果是，程序继续进行下一轮的判断，如果不是，那么返回false。

按照上面的思路，我们可以写出伪代码：

Int IsPalindrome(char * testString)

{

       If 字符串长度为0或1

           返回true.

       Else

           If  字符串头尾字符相同

              IsPalindrome(去掉头尾字符的新子串)

          Else

             返回 false.

}

   按照上面的伪代码，你可以写出如下的代码，你可以测试一下。

int IsPalindrome(char * testString)
{
   if(strlen(testString)==0||strlen(testString)==1) return 1;
   else 
    {
       if(testString[0]==testString[strlen(testString)-1]) 
       {
	 char *tmp=(char*)malloc((strlen(testString))*sizeof(char));
	 int i=1;
	 for(;i<strlen(testString)-1;i++) tmp[i-1]=testString[i];
	 tmp[strlen(testString)-2]='\0';
	 IsPalindrome(tmp);
       }
       else
	return 0;
   }
}

  还有一点这里可以顺便提一下，c语言标准类型里其实没有bool类型。关于递归的题目实在太多了，所以不是说看每一个题目的解法就行了，重要的是能够按照这个思想去理解递归，不然到面试被问到新问题的时候往往会手足无措，这是我的切身体会。

4.递归和循环。从递归的执行方式上看，和循环总有那么一种说不明白的关系，所以对于递归和循环也是经常会被问到的一个问题，这其中最最常见的就是，什么时候使用递归，什么时候使用循环？

      首先，说明使用递归的情况，第一点就是，如果这个问题很复杂但是去可以分解成为一些递归解决的小问题的时候就适合用递归，比如汉诺塔问题。第二，算法本身 就是用递归的方式描述的，比如说，树的遍历，在问题算法的描述上，就是以递归的形势，这一点在数据结构很多算法中有突出的体现。

      接着，什么时候使用循环比较好呢？第一点就是，问题本身就很简单，如果一个简单的问题用复杂的解法去解答，除非你有特殊的目的，不然的话那就说明你确实有 着不同常人的癖好。第二点就是，算法不能用拆解成子问题并且以递归的方式描述，这种就没有必要用递归了，因为这样只会徒增写代码的工作量。第三，就像前面 说的，递归要耗费栈空间，而在现代语言中，栈空间的大小大大小于堆中的空间，所以用循环可以节省很大的空间。

5.不同寻常的尾递归。尾递归就是一个函数中所有递归形式的调用都出现在函数的末尾，通俗点说就是，当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一 部分时，这个递归调用就是尾递归。比如下面这种就是尾递归：

int F(int n, int acc)
{
    if (n == 0) return acc;
    return F(n - 1, acc * n);
}

    尾递归函数的特点是在回归往上的过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。比如上面的内容就可以被优化成为：

int FOptimized(int n, int acc)
{
    while (true)
    {
        if (n == 0) return acc;
        acc *= n;
        n--;
    }
}

     关于递归还有很多内容，这里在还没有涉及到数据结构之前，先来个预热，在后面至少还有两次还会深入的了解一下递归，我个人体会，理解递归对面试的帮助真的是巨大的。