前言
最近被函数递归困恼许久,今天就带领大家一起探秘递归。
什么是递归
程序调用自身的编程技巧称为递归( recursion)。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接 调用自身的 一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解, 递归策略 只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
递归的主要思考方式在于:把大事化小。(这个想法很重要)
递归的两个必要条件
1 存在限制条件,当满足这个限制条件的时候,递归便不再继续。
2 每次递归调用之后越来越接近这个限制条件
为了更好的理解递归我将为大家分享几到题目。
题解递归
在解题之前,我想刚刚接触递归的小伙伴都会面临,我知道递归是什么,但就是不会写他或者说不理解怎么实现。为此大家可以参考我的解题三步骤。
步骤一:明确你的函数要实现什么功能。
在我看来,要想求解一个递归你肯定要知道你要实现一个什么功能,写出一大概的函数出来。
//求n的阶乘 int demand_factorial(int n) { }
在这个代码中,我们明确了这个函数要求的是n的阶乘,求阶乘所所需要的参数。
步骤二:寻找递归结束的条件
递归就是在函数在不断的调用自己,要想停下来,肯定是要有条件能让他停下来,不然会一直调用自己而陷入死递归。就是说我们要找到一个参数为啥时,递归结束,之后直接把结果返回。请注意这个参数值我们必须明白,参数为何值的时候,函数的结果是什么。
对于上面那个例子,我们肯定明白n = 1时函数的结果为1。那么我们便可以这么写。
//求n的阶乘 int demand_factorial(int n) { if (n == 1) { return 1; } }
为什么说当我们明确知道,n = 1时函数结果我们也知道了,n = 1会为递归结束的条件呢。大家可以想我们这个递归是要干什么的,不就是求n的阶乘吗,既然我们都知道到n=1的阶乘为1了,那么到这里就要结束函数递归了。所以说,递归结束的条件:可以理解为我们所知道的函数结果的那个参数值,也就是n是一个很小的值。
步骤三:找出函数的等价条件
就是我们要不断遵循把大事化小的思路,把参数范围不断缩小,我们可以通过一些辅助的变量或者操作,使得原函数的结果不变。
例如,demand_factorial(n)这个范围比较大,我们可以变为demand_factorial(n)=n*
demand_factorial(n-1),注意n的范围就变成n-1了,为了让原函数不变,我们需要让demand_factorial(n-1)*n.其实,我们就是在为原函数寻找一个等价式。
这一步骤也是最难的大家可以细细体会,下面我们继续完善代码。
//求n的阶乘 int demand_factorial(int n) { if (n == 1) { return 1; } else { return demand_factorial(n - 1) * n; } }
大家看完上面的思路可能还是不怎么理解,没关系,我会带这个思路继续为大家分享几道题目。
- 题目1 strlen的模拟(递归实现)
大家继续按照上面的思路来求解这道题目
1 明确你函数要实现的功能。
假设my_strlen(str)是实现求字符串的长度,代码如下:
//用递归模拟strlen //str为数组名 int my_strlen(char* str) { }
2 找出递归结束的条件
我们明白在一个字符串中他的结束标志是'