递推算法

介绍

递推算法通常用于解决那些可以分解为相似子问题的问题。递推算法的核心思想是利用已经计算出的结果来推导新的结果，从而避免重复计算，提高效率。

递推算法可以分为顺推和逆推两种

• 顺推法：从已知条件出发，逐步推算出要解决的问题的方法。它通常用于求解序列的下一项或达到某个特定状态所需的步骤。

• 逆推法：从已知问题的结果出发，用迭代表达式逐步推算出问题的初始条件。它是顺推法的逆过程，通常用于求解逆向问题或回溯问题。

递推算法的设计步骤

• 确定数据项

• 找到递推关系式

• 设计递推程序

• 输出结果

相关题目

• 猴子吃桃子

• 统计每个月兔子的总数

• 数数木块

• Pell数列

• 上台阶

• 蜜蜂路线

• 骨牌方格

• 小明放骨牌

• 平面切割问题

• 母牛的故事

• 插方块的故事

递归算法

介绍

递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

如果在定义某个事物的时候，有直接或间接地引用了这个事物的本身，就称之为递归定义。

例如，将 N 的阶乘定义为 n-1 的阶乘乘以n,就是一个递归的定义

int sum(int n) {
    if (n <= 1) {
        return 1;
    }
    return sum(n - 1) + n;
}

递归的特点

实际上，递归有两个显著的特征,终止条件和自身调用:

自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，即都是调用自身的同一个函数。

终止条件：递归必须有一个终止的条件，即不能无限循环地调用本身。

递归函数

如果在定义一个函数时，又直接或间接地调用了这个函数自身，就称之为递归函数

相关题目

• 求n的阶乘

• 顺序打印 i 到 j ( i <= j , 包含j)

• 倒序打印 i 到 j ( i <= j , 包含j)

• 对数组 arr 所有元素进行求和

• 给定一个字符串,将其翻转

• 求第n 个斐波那契数列元素

• 求解最大公约数

• 插入排序的递归形式

• 汉诺塔问题

• 青蛙上楼梯

• 旋转数组的最小数字

• 设计一个高效的求a的n次方幂的算法