递归与分治策略（一）---算法设计与分析

Love The Way You Lie 2022-08-07 02:51 58阅读 0赞

递归与分治策略（一）

简而言之，递归就是自己调用自己。

递归算法：直接或者间接地调用自身的算法。

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

注意：每个递归函数都必须有非递归定义的初始值，以确保递归函数完成计算。

下面通过两个例子来介绍递归的特点

例1 阶乘函数

阶乘函数递归地定义为：

n!=1 (n=0)

或者

n!=n(n-1)! (n>0)

下面用一段简单的Java代码实现

这里是递归实现：

public static int facterial(int n) {
    		if (n == 0)
    			return 1;
    		else if (n < 0)
    			return -1;//发生异常，退出
    		else
    			return n * facterial(n - 1);
    	}

下面是迭代实现：

public static int f(int n) {
    		if (n == 0)
    			return 1;
    		else if (n < 0)
    			return -1;//发生异常，退出
    		else {
    			for (int i = n - 1; i >= 1; i--) {
    				n *= i;
    			}
    			return n;
    		}
    
    	}

分析比较一下两种实现方法：

递归实现：时间复杂度O(n)；空间复杂度O(n)。

迭代实现：时间复杂度O(n)；空间复杂度O(1)。

比较可知两种实现的时间复杂度等价，空间复杂度递归占用的略大一下，但是代码的结构清晰度递归更清晰一些。

下面进行第二个例子的讲解

例2 Fibonacci数列

Fibonacci数列的递归定义为

F(n)=1 (n=0,1)

或者

F(n)=F(n-1)+F(n-2) (n>1)

下面用一段简单的Java代码实现

这里是递归实现：

public static int fibonacci(int n ){
    		if(n<0)
    			return -1; //发生异常，退出
    		else if(n<=1)
    			return 1;
    		else 
    			return fibonacci(n-1)+fibonacci(n-2);
    	}

下面是迭代实现：

public static int F(int n){
    		if(n<0)
    			return -1; //发生异常，退出
    		else if(n<=1)
    			return 1;
    		else {
    			int f0=1,f1=1,fx=0;
    			for(int i=2;i<=n;i++){
    				fx=f0+f1;
    				f0=f1;
    				f1=fx;
    			}
    			return fx;
    		}
    	}

分析比较一下两种实现方法：

递归实现：时间复杂度O(1.618的n次方)；空间复杂度O(n)。

迭代实现：时间复杂度O(n)；空间复杂度O(1)。

比较可知递归实现的时间复杂度已经非常大了，空间复杂度递归占用的略大一下，但是代码的清晰度递归更清晰一些。而真正使用起来递归实现的代码是无用代码，用n=40这个数测试一下便知，递归实现的耗时太长了，有兴趣的可以测试一下。

下面归纳一下递归算法的特点：

1.简单（结构清晰，可读性强）

2.性能较低（相比较迭代而言）

性能较低的原因有以下两点：

1 需递归调用工作栈支持（无法避免）

2 有可能出现子问题重叠现象（必须尽力避免）

这里递归的主要知识点就讲完了，下面介绍一下文章标题的分治法。

分治法的基本思想：