递归算法分析

算法总结之递推与递归

递推算法

递归算法⼤致包括两⽅⾯的内容：1）递归起点 ； 2）递归关系

递推起点

递归起点⼀般由题⽬或者实际情况确定，不由递归关系推出。如果⽆法确定递归起点，那么递归算法就⽆法实现。可见，递归起点是递归算

法中的重要⼀笔。

递推关系递归关系是递归算法的核⼼。常见的递归关系有以下⼏项：

1）⼀阶递推；

2）多阶递推；

3）间接递推；

4）逆向递推；

5）多维递推。

下⾯通过栗⼦来详细介绍⼀下上述类别的递推关系。

1. ⼀阶递推

在计算f(i)时，只⽤到前⾯项中的⼀项，如等差数列。公差为3的等差数列，其递推关系为：

f(i)=f(i-1)+3

eg. 平⾯上10条直线最多能把平⾯分成⼏部分？

分析：以直线数⽬为递推变量，假定i条直线把平⾯最多分成f(i)部分，则f(i-1)表⽰i-1条直线把平⾯分成的最多部分。在i-1条直线的平⾯上增

加直线i，易得i与平⾯上已经存在了的i-1条直线最多各有⼀个交点，即直线i最多被分成i段，⽽这i段将会依次将平⾯⼀分为⼆，即直线i将最

多使平⾯多增加i部分。所以，递推关系可表⽰为：f(i)=f(i-1)+i

易得当0条直线时，平⾯为1部分。所以f(0)=1为递推起点。

上述分析可⽤下⾯代码表⽰（c++）：

#define MAX 100

int f[MAX] //存放f（i）

int lines(int n){

//输⼊n为直线数⽬

//输出最多部分数

int i;

f(0)=1;

for(i=1;i<=n;i++){

f[i]=f[i-1]+3;

}

return f[i];

}

2. 多阶递推

在计算f(i)时，要⽤到前⾯计算过的多项，如Fibonacci数列。

eg.求Fibonacci的第10项。

分析：总所周知，Fibonacci数列中的第n项等于第n-1项加上n-2项。所以递推关系为

f(i)=f(i-1)+f(i-2);且f[0]=f[1]=1。

C++代码如下：

#define MAX 100

算法分析与设计

实

验

报

告

专业班级：

姓 名：

学 号：

指导老师：

实验一 递归算法的设计与实现

• 计算整数的非负整数次幂

(1)设计思路

对于34按步骤可以分析：

34=32*32

32=31*31

31=31*1

对于33按步骤可以分析：

33=32*31；

32=31*31；

31=31*1；

分析可以得到：

当xn中n为奇数时，xn=x*(xn/2)2

当xn中n为偶数的，xn=（xn/2）2；

当n/2=0;return 1；

一步步进行递归返回计算，如果n位奇数，在进行一部乘以x

否则返回运算结果

(2)源程序代码

#include

using namespace std;

int power(int x,int n)

{

int y;

if(n==0)

{

y=1;

}

else

{

y=power(x,n/2);

y=y*y;

if(n%2==1)

{

y=y*x;

} }

return y;

}

void main()

{

cout<<"请输入一个底数X：";

int x;

cin>>x;

cout<<"请输入一个指数Y: ";

int y;

cin>>y;

if(y<0)

{

cout<<"你的输入有误：请重新输入:"<

cin>>y;

}

int c;

c=power(x,y);

cout<

}

(3)代码运行结果

(4)时间复杂度

令n=2k，则可以得到：f(n)=g(k)=k+1=logn+1=O(logn)

2.基于递归算法的插入排序

(1)设计思路

通过主函数传来一个数组的首地址和数组的长度，然后利用递归的原理，当n=0；程序返回，执行入栈的递归程序，依次比较2个数的大小，3个数的大小等，根据比较的结果将第n个数插入适当的位置。

计算机算法设计五⼤常⽤算法的分析及实例

摘要

算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。

其中最常见的五中基本算法是递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法。本⽂通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识

关键词：算法，递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法Abstract

Algorithm is the description to the problem solving scheme ,a set of clear instructions to solve the problem and represents thedescribe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirmimport，the Algorithm will find result In a limited time。If an algorithm is defective or is not suitable for a certain job, it isinvalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.

There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedyalgorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, makereaders know more about algorithm , and understand the five algorithms more deeply.

编写人：杨玉建

1 |

算法分析(第二章)：递归与分治法

一、递归的概念

知识再现：等比数列求和公式：

1、定义： 直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2、与分治法的关系：

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供

了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而

其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归

过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算

法。

3、递推方程：

(1)定义：设序列

01,....

naaa

简记为{

na

}，把

na

与某些个()

iain

联系起来的

等式叫做关于该序列的递推方程。

(2)求解：给定关于序列{

na

}的递推方程和若干初值，计算

na。

4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序

5、优缺点：

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，

因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空

间都比非递归算法要多。

二、递归算法改进：

1、迭代法：

(1)不断用递推方程的右部替代左部

(2)每一次替换，随着n的降低在和式中多出一项

(3)直到出现初值以后停止迭代

(4)将初值代入并对和式求和

(5)可用数学归纳法验证解的正确性

2、举例：

-----------Hanoi塔算法----------- ---------------插入排序算法-----------

()2(1)1

(1)1TnTn

T=−+

= ()(1)1WnWnn

W=−+−

（1）=0

编写人：杨玉建

2

|

2

1n-23()2(1)1

2[2(2)1]1

2(2)21

...

2++2...1

21nn

nTnTn

Tn

Tn

T−−=−+

=−++

=−++

=

=++

=−（1）2

()(1)1