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

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

    我经常会想,如果给没有学过计算机或者数学的人说递归这个词他们脑中会怎样理解这个词的意思。递归这个概念在面试中出现的概率大于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--;
    }
}

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏cmazxiaoma的架构师之路

Java小白必须会的一道面试算法题

2K3
来自专栏从流域到海域

Python 函数

Python的函数与其他语言的函数概念上是一致的,只是形式上有所不同。在面向过程的编程语言中(C语言),函数是代码的基本组成形式,是功能的基本模块;在面向...

2127
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

2058
来自专栏编程

Python函数之一切皆对象

今天我们要讲的是 对象 避免误会,常老师先澄清一下,这里面说的对象指的是object,不是你的lover,也不是你的sweetheart…… 有的小伙伴可能会觉...

2017
来自专栏怀英的自我修炼

Java漫谈6

今天这篇想聊聊数组。 在聊数组之前先聊个别的,如果想在Java中实现一个 数字-月份 转换,那我该怎么做呢?就比如数字1代表了一月份,数字2代表了二月份…数字1...

3679
来自专栏黑泽君的专栏

Java语言中:在数据类型的讲解中补充的几个小问题

============================================================================= 1...

841
来自专栏Java成长之路

【天梯 - Wikioi】2235 机票打折

871
来自专栏算法channel

LeetCode实战:子问题分析

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 记...

3589
来自专栏C语言C++游戏编程

世界最强的编程语言:C语言

char:字符型,用来存储小范围的整数(-128~127)和字符(所有的ASCII字符,128个),一个字节。

1522
来自专栏菩提树下的杨过

as3:Function以及call,apply

Function类在as3中是直接从Object继承下来的,通常开发者定义的每一个function,均可以认为是Function类的一个实例。  如果硬要跟c#...

2079

扫码关注云+社区

领取腾讯云代金券