【算法总结】递归

╰半夏微凉° 2021-12-03 14:51 289阅读 0赞

**算法总结-递归**

**定义：**

所谓递归即函数直接或间接地调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归方式。同时，为了不使这样的递归无限的发生，我们必须设定递归的出口，即当函数达到某种条件时停止递归。

问题的求解过程->划分成相同性质的子问题的求解->子问题的求解过程可以很容易地求出->这些子问题的解就构成原问题的解。

**递归和枚举的区别：**

枚举——把一个子问题划分成一组子问题，依次对这些子问题求解。子问题之间是横向的，同类的关系；递归——把一个问题逐级分解成子问题。子问题与原问题之间是纵向的，同类的关系。

**注意：**

使用递归函数务必注意递归的层数。一个程序可以使用的栈空间是有限的，当递归的过深或者每层递归所需的栈空间太大将会造成栈的溢出，使评判系统返回程序运行时异常终止的结果，一旦你的递归程序出现了这种错误，你就要考虑是否是由递归的太深而造成了爆栈。这是使用递归程序一个很重要的注意要点。具体可使用的栈大小，每个评判系统不同而有所差异，需要自行测试后确定。

**套路：**

1.  待求解问题的解->输入变量x的函数f(x)
2.  通过寻找函数g(),使得f(x) = g(f(x-1)
3.  且已知f(0)的值，就可以通过f(0)和g()求出f(x)的值。

推广——扩展到多个输入变量x,y,z等，(x-1)也可以推广为(x-x1)。

**要点：**

递归式：如何将原问题划分成子问题。

递归出口：递归终止的条件，即最小子问题的求解，可以允许多个出口。

界函数：问题规模变化的函数，它保证递归的规模向出口条件靠拢。

**例题-阶乘函数**

#include<cstdio>
    
    int Factorial(int n)
    {
        if (n == 0)return 1;//递归出口
        else return n * Factorial(n - 1);//递归式
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
        int ans = Factorial(n);
        printf("the Factorial of %d is %d", n, ans);
        return 0;
    }

转载于:https://www.cnblogs.com/yun-an/p/11048445.html

发表评论取消回复

表情：

评论列表（有 0 条评论，289人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-递归算法

1、定义：函数（方法）直接或间接调用自身。必须要有一个明确的结束递归的条件 > 递归的退出条件：思考临界值-`拿到参数对它的范围进行判断`

墨蓝/ 2024年04月08日 09:38/ 0 赞/ 126 阅读

相关面试算法大全-递归总结

8.递归 8.1 递归算法总结构成递归需具备的条件: 1 . 子问题须与原始问题为同样的事，且更为简单； 2 . 不能无限制地调用本身，须有个出口，

秒速五厘米/ 2022年10月17日 13:51/ 0 赞/ 198 阅读

相关递归算法

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(

深碍√TFBOYSˉ_/ 2022年07月13日 13:46/ 0 赞/ 238 阅读

相关【算法】递归

前言 Github：[https://github.com/yihonglei/road-of-arch][https_github.com_yihonglei_road

我就是我/ 2022年07月12日 04:48/ 0 赞/ 233 阅读

相关算法-->递归

package 递归算法; import java.util.Scanner; public class digui \{ static long fact(int n

旧城等待，/ 2022年06月12日 00:58/ 0 赞/ 270 阅读

相关算法总结01-递归

枚举：子问题横向同类的递归：逐级分解，纵向分解同类的。直接调用，间接调用。递归三要点：递归式，递归出口，界函数。递推公式递归终止条件注意栈的溢

旧城等待，/ 2022年06月03日 01:10/ 0 赞/ 210 阅读

相关递归算法

今年上半年开展新项目, 每天都很忙但也很充实, 学到了很多东西, 比如如何处理50M以上的Excel, 批量处理10W+的数据，新的设计模式等。。。本次分享的是一个小技

àì夳堔傛蜴生んèń/ 2022年05月17日 06:34/ 0 赞/ 292 阅读

相关递归算法

定义：简单来说，递归算法就是直接或者间接调用自身的函数。把一个大型的复杂问题层层转换为一个与原问题相似的小规模的问题来求解。例子：一列数的规则如下: 1、1、2、3、5、8

绝地灬酷狼/ 2022年05月12日 12:14/ 0 赞/ 282 阅读

相关【算法总结】递归

算法总结-递归定义：所谓递归即函数直接或间接地调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归方式。同时，为了不使这样的递归无限的发生，我们必须设

╰半夏微凉°/ 2021年12月03日 14:51/ 0 赞/ 290 阅读

相关算法--递归

递归：注意两点： 1.边界条件时（有时有return，有时是别的操作）代码里用橘红色标出 2.递归时参数变化（规模变小）代码里用黄色标出递归：你

野性酷女/ 2021年10月09日 03:44/ 0 赞/ 520 阅读