递推与递归
递推与递归
递推和递归是算法设计中的两种重要方法，它们在解决问题时有着不同的思路和应用场景。本文将从概念、区别以及具体例题等多个维度，深入浅出地讲解递推与递归，帮助读者更好地理解这两种算法思想。
一、概念
递推
递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。——百度百科
其实简单来说，递推就是由最开始的已知状态逐步推向未知（即问题所需的答案）的过程叫做递推。
递归
程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。——百度百科
俗话说的好，没有对比就没有伤害，百度百科里面递推与递归的概念的长短明显的说明了递归要比递推好用咳咳，回归正题。其实简单来说就是一个函数函数自己调用自己，多次运算，从未知到已知的这样一个过程叫递归。
二、不同与相同
不同
递推是从已知开始逐渐推向未知的状态，而递归是从问题逐渐推向已知,且递归使用的是函数来完成操作。
相同
递推与递归每一次运算的内容都是一样的，不变的，都是到边界后结束运算。
三、例题
递推
1.Hanoi塔
题目描述
问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。 开始时，这n个圆盘由大到小依次套在a柱上，如图所示。
要求把a柱上n个圆盘按下述规则移到c柱上:
规则:
(1)一次只能移一个圆盘;
(2)圆盘只能在三个柱上存放;
(3)在移动过程中，不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？
输入格式
一个数n（1≤n≤63）
输出格式
一个数，总计需要移动多少个盘次
样例输入
3
样例输出
7
题解
在解释之前，我们先来玩一个小游戏：Hanoi塔
从这个游戏中，我们不难发现Hanoi塔每一层需要多少次移动才能达成目标，如下表：
层数 最少移动次数 比上一个增加多少
1 1 1
2 3 2
3 7 4
4 15 8
5 31 16
6 63 32
7 127 64
8 255 128
… … …
n