递归的定义

If the last-executed statement of a function is a recursive call to the function itself, then this call can be eliminated by reassigning the calling parameters to the values specified in the recursive call, and then repeating the whole function.(可以用循环来完成,修改参数值)
基本的部分(基例)不需要递归)
②A general method that reduces a particular case to one or
more of the smaller cases, thereby making progress toward
eventually reducing the problem all the way to the base case.
Tail Recursion
Hanoi Without Tail Recursion
void move(int count, int start, int finish, int temp) { int swap; // temporary storage to swap towers while (count > 0) { // Replace the if statement with a loop. move(count - 1, start, temp, finish); // first recursive call cout << "Move disk " << count << " from " << start << " to " << finish << "." << endl; count--; // Change parameters to mimic the second recursive call. swap = start; start = temp; temp = swap; } }

递归算法
1
递归算法
什么是递归 递归调用的实现原理 递归经典例题
递归定义


在定义一个过程或函数时出现调用本过 程或本函数的成分,称之为递归。 若调用自身,称之为直接递归。 若过程或函数p调用过程或函数q,而q又调 用p,称之为间接递归。
何时用到递归 以下三种情况常常用到递归方法。
1 定义是递归的 2 数据结构是递归的 3 问题的解法是递归的
int main() { int a[1000]; f(6,a,0); return 0; }
经典问题：整数划分
要求：如果对上一个题改一下要求，求解一共多少种划分方 法，如果不用上一种思路，请再尝试另一种递归解决方案
经典问题：整数划分






整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在 讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成 如下形式： n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n） ，则{m1,m2,...,mi}为n的一个划分。 如果{m1,m2,...,mi}中的最大值不超过m，即 max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记 n的m划分的个数为f(n,m); 例如但n=4时，他有5个划分， {4},{3,1},{2,2},{2,1,1},{1,1,1,1}; 注意4=1+3 和 4=3+1被认为是同一个划分。 该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m) 的方法; 1.递归法：
15
f (int a[], int begin, int n) if (begin==n) return 0; else return a[begin]+f(a,begin+1,n);

else { Hanoi ( n-1, A, C, B ); cout << " move " << A << " to " << C << endl; Hanoi ( n-1, B, A, C );
} }
递归过程与递归工作栈
递归过程在实现时，需要自己调用自己。 层层向下递归，退出时的次序正好相反：
}
递归找含x值的结点
f
x

fff
问题的解法是递归的
例如，汉诺塔(Tower of Hanoi)问题的解法： 如果 n = 1，则将这一个盘子直接从 A 柱移到
C 柱上。否则，执行以下三步： ① 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移 到 B 柱上： ② 将 A 柱上最后一个盘子直接移到 C 柱上； ③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移 到 C 柱上。
递归调用
n! (n-1)! (n-2)!
1! 0!=1
返回次序
主程序第一次调用递归过程为外部调用；
递归过程每次递归调用自己为内部调用。
它们返回调用它的过程的地址不同。
递归工作栈
每一次递归调用时，需要为过程中使用的 参数、局部变量等另外分配存储空间。
每层递归调用需分配的空间形成递归工作 记录，按后进先出的栈组织。
while ( n >= 0 ) { cout << "value " << A[n] << endl;
n--;
} }
递归与回溯 常用于搜索过程
n皇后问题 在 n 行 n 列的国际象棋棋盘上，

• (2)式给出了fun(n)的值与fun(n-1)的值之间的关系， 称为递归体。
9
递归求n！
int fun(int n) {
if (n==1)
/*语句1*/
return 1; /*语句2*/
分解过程
else
/*语句3*/
return fun(n-1)*n; /*语句4*/
n=3
n=2
} n=1
fuc(3) ﹕
s
s为空串
f(s)=
•
Concat(f(SubStr(s,2,StrLength(s)-1)),SubStr(s,1,1)) 其他
15
SqString invert(SqString &s) {
SqString s1,s2; if(StrLength(s)>0) { s1=invert(SubStr(s,2,StrLength(s)-1));
• 体现了分而治之的算法思想
3
6.1.2 何时使用递归
• 在以下3种情况下,常常要用到递归的方法。
• 1. 定义是递归的 • 2. 数据结构是递归的
求n!和Fibonacci数列
例如，单链表就是一种递归的数据结构，其结
点类型定义如下：
typedef struct LNode
{
ElemType data;
else return(head->data+Sum(head->next));
}
5
3. 问题的求解方法是递归的
• 汉诺塔问题是印度的一个古老的传说。 • 在世界中心贝拿勒斯（在印度北部）的圣庙里， 一块黄铜板上插着三根宝石针。印度教的主神梵天在 创造世界的时候，在其中一根针上从下到上地穿好了 由大到小的64片金片，这就是所谓的汉诺塔。 • 不论白天黑夜，总有一个僧侣在按照下面的法则 移动这些金片：一次只移动一片，不管在哪根针上， 小片必须在大片上面。 • 僧侣们预言，当所有的金片都从梵天穿好的那根 针上移到另外一根针上时，世界就将在一声霹雳中消 灭，而梵塔、庙宇和众生也都将同归于尽。