- 递归的三种表现形式
-
定义是递归的：
例：阶乘函数的定义——
n! = 1；n = 0时
n! = n * (n-1)! (n为>=0的整数) -
结构是递归的：
链表：链表中的每一个节点中都有一个指针域指向下一个节点
-
算法是递归的：
实现阶乘算法可以用递归来实现
-
一些问题的递归算法实现
- 阶乘函数：
阶乘函数的定义如上。
代码：
int fac(int n){ if(n == 0){ return 1; } return n*fac(n-1); }
- 斐波那契函数：
定义：
f(n) = 1 (n = 1,2)
f(n) = f(n-1) + f(n-2) (n>2)
代码:
int fibonacci(int n){
if(n <= 0)
return -1;// 非法输入处理
if(n == 1||n == 2){
return 1;
}
else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
像阶乘函数和斐波那契函数这样有明确递归定义的函数一般可以直接“翻译“成代码。
-
汉诺塔问题
问题描述：
三个柱子(A,B,C)，起初有若干个按大小关系顺序安放的圆盘，需要全部从A移动到C柱子。移动规则：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
分析：对于这样一个问题，我们不难发现它可以用递归求解——
考虑最简单的情况 —— 只有一个圆盘的时候，我们会直接把圆盘从柱A挪到柱C。
普遍的情况 —— 存在n个圆盘的时候，我们把A柱最大圆盘上面的n-1个圆盘借助C柱先挪动到B柱，把最大的圆盘移动从A移动到C，再把n-1个圆盘借助B柱移动到C柱。n 为 1的时候，递归停止。
通过分析，我们可以写出代码：
void hanoi(char a, char b, char c,int n){
if(n == 1){
//只有一个圆盘的时候，我们会直接把圆盘从柱A挪到柱C
cout << a << " -> " << c << endl;
}
else {
//把A柱最大圆盘上面的n-1个圆盘借助C柱先挪动到B柱
hanoi(a,c,b,n-1);
//把最大的圆盘移动从A移动到C
cout << a << " -> " << c << endl;
//再把n-1个圆盘借助B柱移动到C柱
hanoi(b,a,c,n-1);
}
}
-
用递归实现栈的元素倒序排列
分析：
最简单的情况 ——— 栈内只有一个元素的时候，把这个元素取出来(pop)，再push进去(嗯相当于啥也没干。。所以就不用考虑了)
复杂(多个元素)：取出第一个元素，将剩下的栈实现元素倒序，将第一个元素放到栈底，当这个栈为空的时候，递归停止。代码：
void reverseStack(Stack<T> s){
if(!s.empty()){
Data top = s.top();
s.pop();
reverseStack(s);
addAtLast(s, top);
}
}
而明显addAtLast(Stack s, Data d)需要我们自己实现，而这个函数也可以用递归实现：
最简单的情况：———— 栈内没有元素，直接把这个元素入栈
复杂(多个元素) ———— 取出栈顶元素top，把d元素放到剩下的这个栈的底部，
把top元素入栈
void addAtLast(Stack s,Data d){
if(s.empty){
s.push(d);
}
else {
Data top = s.top();
s.pop();
addAtLast(top, s);
s.push(top);
}
}
- 个人总结觉得，递归的算法有一类共性，这些能被递归解决的问题我们往往能通过一些操作将问题的规模缩小，而问题规模缩小到一定程度时，解决这个问题的算法是显而易见的/
最后，留作一个思考题：在n个元素的集合setN中，找出所有m个排列组合的情况
网友评论