递归基础知识

时间:2024-03-03 10:15:29

递归是程序设计中的一种算法。一个过程或函数直接调用自己本身或通过其他的过程或
函数调用语句间接地调用自己的过程或函数,称为递归过程或函数。递归是计算机语言中的
一种很有用的工具,很多数学公式用到递归定义,例如N!:当n>0时,f(n)=n×f(n–1)。
有些数据结构(如二叉树),其结构本身就有递归的性质。有些问题本身没有明显的递
归结构,但用递归求解更简单。
递归是较难理解的算法之一。简单地说,递归就是编写这样一个特殊的过程,该过程体
中有一个语句用于调用过程自身(称为递归调用)。递归过程由于实现了自我的嵌套执行,
使这种过程的执行变得复杂起来,其执行的流程如下图所示。

递归过程的执行总是一个过程体未执行完,就带着本次执行的结果又进入另一轮过程体
的执行,……,如此反复,不断深入,直到某次过程的执行时终止递归调用的条件成立,则
不再深入,而执行本次的过程体余下的部分,然后又返回到上一次调用的过程体中,执行余
下的部分,……,如此反复,直到回到起始位置上,才最终结束整个递归过程的执行,得到
相应的执行结果。递归过程程序设计的核心就是参照这种执行流程,设计出一种适合“逐步
深入,而后又逐步返回”的递归调用模型,以解决实际问题。
递归算法应该包括递归情况和基底情况两种情况。递归情况演变到最后必须达到一个基
底。
在程序设计面试中,一个能够完成任务的解决方案是最重要的,解决方案的执行效率要
放在第二位考虑。因此,除非试题另有要求,应该从最先想到的解决方案入手。如果它是一
个递归性的方案,不妨向面试官说明一下递归算法天生的低效率问题——表示你知道这些事
情。有时候同时想到两个解决方案:递归的和循环的,并且实现方式差不多,可以把两个都
向考官介绍一下。比如N!问题,利用循环语句解释就是:

不过,如果用循环语句做的改进算法实现起来要比递归复杂得多的话——大幅度增加了
复杂度而在执行效率上得不到满意的回报,我们建议还是优先选择递归来解决问题。
面试例题1:递归函数mystrlen(char *buf, int N)是用来实现统计字符串中第一个空字符前面字
符长度。举例来说:

字符串buf,当输入N=10或者20,期待输出结果是6;当输入N=3或5,期待输出结果是3
或5。

What are all the possible mistakes in the code?(代码中可能的错误是哪个/些)
A.There are no mistakes in the code(没错)
B.There is no termination of recursion(没有递归退出条件)
C.Recursion cannot be used to calculate this function(递归是不能实现这个函数的功能)
D.The use of N/2 in the recursion is incorrect(对N/2的使用是错误的)
解析:递归函数关注以下几个因素:退出条件,参数有哪些?返回值是什么?局部变量
有哪些?全局变量有哪些?何时输出?会不会导致堆栈溢出?本题中递归函数显然没有退出
条件。
答案:B

扩展知识:下面是该递归函数的正确实现方法

 

-----------------------------------------------------------------------------------------------------------------------------------------------

典型递归问题

If we define F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2), what is the result of
F(1025) mod 5?[美国著名操作系统软件企业M公司2013年面试题]
A.0
B.1
C.2
D.3
E.4
解析:这里是对递归函数取余,所以我们最好先做一下拆项:

所以F(1025)mod 5=3 * F(1020)mod 5;
依次类推:

F(5)为5,mod后值为0。所以F(1025)mod 5=0;
答案:A

----------------------------------------------------------------------------------------------------------------------------------------

请给出此题的非递归算法:

解析:本题类似于杨辉三角形,其实就是计算一个对角线值,用list保存一个对角线元
素即可。除了横边和纵边按顺序递增外,其余每一个数是它左边和上边数字之和。

如上所示,假如想求m为3、n为4的f(m, n)值,就是25。
答案:代码如下: