递归思想——关于递归的多个例子详解
发布时间
阅读量：
阅读量
阶乘
举例说明为了说明如何计算阶乘n!（其中n为正整数），我们可以列举具体的步骤：
其中函数 fact(n)定义为：
fact(n) = n! = \prod_{k=1}^{n} k
由此可见，
fact(n) = (n-1)! \times n
即
fact(n) = fact(n-1) \times n
于是，fact(n)用递归的方式写出来就是：
def fact(n):
if n==1:
return 1
return n * fact(n - 1)如果我们计算fact(5)，可以根据函数定义看到计算过程如下
汉诺塔问题
我们将柱子编号设定为a、b、c，并考虑如何实现将所有圆盘从源柱子移动至目标柱子的过程。具体来说：当源柱子上仅放置了一个圆盘时，则可以直接完成转移操作；而当源柱子上有N个不同尺寸的圆盘时，则可视为由一个底盘支撑的（即底座）加上（N-1）层塔块。对于这种情况的操作步骤如下：首先需要将这（N-1）层塔块从源柱移至备用塔座；接着将源塔的最后一层塔块移至目标塔座；最后再将备用塔座上的（N-1）层塔块转移至目标塔座。基于以上分析，请编写一个递归函数move(n,a,b,c)，用于生成并输出具体的移动指令序列。例如，在调用move(2,'A','B','C')时会得到以下输出：
A --> B
A --> C
B --> C
def move(n,a,b,c):
if n==1:
#这其实是只有一个圆盘需要从A到C的情况。所有递归，最终都是走到这一步。
print (a,'-->',c)
#这是结束递归，省略了None。没有这句的话，递归没办法结束。
return
#将A柱的n-1个盘移到B柱，这里毫无争议。注意形参顺序变化了。
move(n-1,a,c,b)
#这句话才是第一个柱子的第n个圆盘移动到目标柱子。
print a,'-->',c
#过渡柱子B上（n-1）个圆盘B递归移动到目标柱子C
move(n-1,b,a,c))move(4,‘A’,‘B’,‘C’)
二分查找法
//用递归的方式写二分查找法
template<typename T>
int _binarySearch2(T arr[],int l,int r,T target)
{
if(l>r) //递归结束条件
return -1;
int mid= l+(r-l)/2;
if(arr[mid]==target)
return mid;
else if (target<arr[mid])
return _binarySearch2(arr,l,mid-1,target);
else
return _binarySearch2(arr,mid+1,r,target);
}
}也可以使用非递归方式实现二分查找法
//二分查找法，在有序数组arr中，查找target
//如果找到target，返回相应的索引index
//如果没有找到target，返回-1
template<typename T>
int binarySearch(T arr[],int n,T target)
{
//在arr[l...r]中查找target
int l=0,r=n-1;
while(l<=r){
//int mid =(l+r)/2;
int mid = l+(r-l)/2;//避免溢出
if(arr[mid]==target)
return mid;
if(target<arr[mid])
//在arr[l....mid-1]中查找target
r=mid-1;
else
//在arr[mid+1...r]中查找target
l=mid+1;
}
return -1;
}递归实现通常思维起来更容易，但在性能上会有略差。
二分搜索树插入新节点
// 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
// 返回插入新节点后的二分搜索树的根
Node* insert(Node *node, Key key, Value value){
if( node == NULL ){
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
};文本逆序复制
/* * 把一个文本文件逐行按逆序复制到另一个文件中
* 在命令行中给出这两个文件名，源文件名在前，目的文件名在后。
*/
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
FILE *fs,*fd;
//revcopy以递归的方式逐个字符实现一行文本的逆序复制
void revcopy(void)// 逆序复制一行
{
char achar;
if((feof(fs)==NULL)&&((achar=fgetc(fs))!='\n'))
//源文件未到结尾且从源文件读取的字符不等于换行字符
{
revcopy();
fputc(achar,fd);//把字符写入目的文件
}
}
int main(int argc,char *argv[])
{
//char ach;
if(argc<3){ //命令行中的字符串个数小于3
cout<<"missing parameters\n";
exit(0);
}
if((fs=fopen(argv[1],"r"))==NULL){//以只读的方式打开源文件。argv[1]是指向源文件名的指针
cout<<"can not open source file\n";
exit(0);
}
if((fd=fopen(argv[2],"w"))==NULL){
cout<<"can not open destination file\n";
exit(0);
}
while(feof(fs)==NULL){
//如果源文件未结束为真
revcopy();
fputc('\n',fd);//逆序复制一行，并在该行结尾加上换行符\m
}
fclose(fs);
fclose(fd);//关闭源文件和目的文件
return 0;
}您需要具体说明如何实现对每行文本进行逆序复制这一操作流程吗？请参考以下方法：采用递归方法来完成这一任务。通过查看相关代码可以更好地理解其工作原理。当当前读取到的字符不是换行符时，并且源文件尚未全部读取完毕时，则继续调用自身递归地读取下一个字符直至遇到换行符为止才完成返回过程。即从该行最后一个字符的位置开始向目标文件进行写入操作。
//revcopy以递归的方式逐个字符实现一行文本的逆序复制
void revcopy(void)// 逆序复制一行
{
char achar;
if((feof(fs)==NULL)&&((achar=fgetc(fs))!='\n'))
//源文件未到结尾且从源文件读取的字符不等于换行字符
{
revcopy();
fputc(achar,fd);//把字符写入目的文件
}
}两两交换链表中的节点
/** * Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}全部评论 (0)
还没有任何评论哟~