递归算法大全<一><二>

60 阅读 0 评论 40 点赞

我是靠谱客的博主重要火，最近开发中收集的这篇文章主要介绍递归算法大全<一><二>，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

------来自百度

总结：递归的过程重在分析，先向下寻找找出出口条件，然后依次回退解决当前问题。

三要素参考博客：http://blog.csdn.net/sinat_32547403/article/details/74934897

递归的要素：

一定有一种可以退出程序的情况；！！！（必须存在出口条件）
总是在尝试将一个问题化简到更小的规模（存在一个可以有限次细化的解决问题的公式）
父问题与子问题不能有重叠的部分（如果全部重叠将无法跳出循环递归，导致程序崩溃）

问题抛出：

求1~n这n个数的和，求n的阶乘，斐波拉契数列，猴子吃桃，年龄问题。

汉诺塔，快速排序，八皇后（待更新）

分析问题：第一排问题，仔细分析后发现它们都存在一个解决问题的公式，目前我们就称这类问题为计算类递归。这种问题很容易分析出结论来。

第二排问题存在应用场景，汉诺塔，八皇后是经典的递归，八皇后牵扯到了回朔问题，快速排序需要递归的调用以前的应用场景。这些问题都是将大我分解成了小我最后都是单元素的处理。

<一>

1.求1~n这n个数的和。

这个问题和出口的设定关系极大，因为当他找到它递归的出口时，它便会立刻进行回退。

分析如图：

如果我们将出口改成func（2）=3，他就会提前递归跳出。

所以正确且有效的出口至关重要。

#include<stdio.h>
// N个数求和
//思想:1.出口条件：N=0
//
2.func(c) = c + func(c-1);
//依次累加求和，同类：求阶乘，斐波拉契数列,猴子吃桃。
int func(int i)
{
int n = 0;
if( i == 1 )
{
return 1;
}
if( i >= 1 )
{
return i + func(i-1);
}
}
void main()
{
printf("%d",func(3));
}

2.求n的阶乘

c语言代码实现：

int func(int n)
{
if(n<0)
return -1;
if( n==0 )
return 1;
if( n > 0 )
return n*func(n-1);
}
void main()
{
printf("%d",func(10));
}

3.斐波拉契数列

c语言实现

int func(int n)
{
if( n==1 || n==2 )
return 1;
if( n > 2 )
return func(n-1) + func(n-2);
}
void main()
{
printf("%d",func(5));
}

4.猴子吃桃

int func(int i)
{
if( i == 1 )
return 1;
if( i > 1 )
return 2*(func(i-1) + 1);
}
void main()
{
printf("%d",func(4));
}

5.年龄问题

有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？用递归算法实现。

分析本题也只是将n个数求和的出口改成了最后一个人的年龄10；

求解方法和求和大同小异不做赘述。

<二>

1.汉诺塔

//汉诺塔的实现
//思想：1.出口条件N=1，直接把a移到c
//
2.先将a上前n-1个盘子通过c移到b
//
3.然后把a上的盘子移到c
//
4.最后把b上的n-1个盘子通过a移到c完成跳出
/*void haino(int n ,int a ,int b ,int c)
{
if( n == 1 )
printf("把%d移到%dn",a,c);
if( n > 1 )
{
haino(n-1,a,c,b);
printf("把%d移到%dn",a,c);
haino(n-1,b,a,c);
}
}
void main()
{
int a = 1,b = 2,c = 3;
haino(5,a,b,c);
} */

2.快速排序

//快速排序
/*void swap(int *arr,int i,int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void print(int *arr,int len)
{
int i;
for(i=0;i<len;i++)
{
printf("%d ",arr[i]);
}
}
int quick(int *arr ,int low,int high)
{
int temp = arr[low];
int len = high;
if( low < high )
{
while( low < high )
{
while( ( low<high ) && ( arr[high]>= temp ) )
{
high--;
}
swap(arr,low,high);
while( ( low<high ) && ( arr[low]<= temp ) )
{
low++;
}
swap(arr,low,high);
}
quick(arr,0,low);
quick(arr,low+1,len);
}
return low;
}
void main()
{
int arr[] = {5,7,6,3,1,9,8,4,2,0};
int len = sizeof(arr)/sizeof(*arr);
quick(arr,0,len-1);
print(arr,len);
}

3.八皇后

#include <stdio.h>
//存坐标
int index[8] = {0};
//存次数
int count=0;
//打印函数
void print()
{
int i = 0,j = 0;
printf("n");
for(i=0;i<8;i++)
{
for(j=0;j<index[i];j++)
printf("*");
printf("#");
for(;j<8;j++)
printf("*");
printf("n");
}
printf("-----------------------%d",count++);
}
//检查是否可放
int check(int row,int col)
{
int i = 0;
int local;
for(i=0;i<row;i++)
{
local = index[i];
//同行同列
if(col == local)
return 0;
//纵向重合
if( (local + i) == (row + col) )
return 0;
if( (local - i) == (col - row) )
return 0;
}
return 1;
}
void queue(int row)
{
int i = 0;
for(i=0 ;i<8 ;i++)
{
//位置0-7递增判断是否可放皇后
//如果上一次检查无误
if( check(row,i) ){
//放入皇后位置
index[row] = i;
//判断是否到8行
if( row == 7 )
{
//打印
print();
index[row] = 0;
return ;
}
//没有完成，行数递增
queue(row+1);
index[row] = 0;
}
}
}
int main()
{
queue(0);
print();
return 0;
}