Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

算法---递归及尾递归

白露非霜 2020-04-09 22:09:00 阅读数:18 评论数:0 点赞数:0 收藏数:0

什么叫递归?举个例子,我们排队,想知道自己排在第几个,那么我们可以问前面的那个人,前面的人继续问前面,直到问到第一个人,这就是传递的过程。然后再从第一个人回来,这就是归(回溯)的过程。传递过去再回归回来,这就是递归。第一个人就是我们所说的递归出口,也就是说到哪个点应该回归了,如果没有出口,那么就会死循环了栈溢出。

 

在代码中简单来说就是自己调用自己。拿到自己的结果再作为入参调用自己。

比如我们求阶乘:

5的阶乘: 5*4*3*2*1

我们用递归来写,那么出口就是n=1的时候:代码如下

 /**
* 阶乘
* @param n
* @return
*/
public static int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}

调用过程如下:

 

 走到1的时候最后再一次回来计算结果,最后返回。这就是递归。

 

再来看一个比较经典的例子,裴波那契数列,1,1,2,3,5,8,13,21....后一项永远是前两项之和,

 

用递归来实现:

 

 /**
* 裴波那契数列 递归
* @param n
* @return
*/
public static int recursion(int n) {
if (n <= 2) {
return n == 0 ? 0 : 1;
}
return recursion(n - 1) + recursion(n - 2);
}

 

是不是感觉递归写起来代码很少。看起来也干净。但是当执行上面裴波那契数列的代码,比如设置一个45,你会发现很久都计算不出来,为什么呢?

递归一个递和一个归的过程无疑是增加了时间复杂度的,阶乘那个的时间复杂度还好O2n)也就是On),但是裴波那契数列就是O2^n因为每个值进去都有两个分支,就像12,24,48这种了,所以是2^n。就像这样:

 

 从这个图里面还看出来几乎所有的值都会被多次计算,在每一个分支都去计算多次。

所以我们需要来优化我们上面的代码:

1.非递归实现,按理来说,每一个递归都可以用非递归来实现

裴波那契数列非递归实现,时间复杂度O(n)

 /**
* 裴波那契数列循环实现
* @param n
* @return
*/
public static int cycle(int n) {
if (n <= 2) {
return n <= 0 ? 0 : 1;
}
int f1 = 1; //n-1
int f2 = 1; //n-2
int fn = 0; // n
for (int i =3; i<=n;i++) {
fn = f1 + f2;
f2 = f1;
f1 = fn ;
}
return fn ;
}

 

2.保存中间结果,刚才也说到了,裴波那契数列那个递归的实现,会让很多值多次计算,声明一个数组做缓存,把中间结果放入数组中存起来,计算的时候先去数组中取,如果有就不计算了

 public static int cache(int n) {
int data[] = new int[n]; // 用数组来做缓存
return fac(n, data);
}
public static int fac(int n, int[] data) {
if (n <= 2)
return 1; //递归的终止条件
if (data[n-1] > 0) { //数组中有值就直接取出来返回,不用再去计算
return data[n-1];
}
int res = fac(n - 1, data) + fac(n - 2, data);
data[n-1] = res; //算出来值放到数组中
return res;
}

 

3.尾递归为什么有些递归会栈溢出,因为每个方法调用都会创建新的栈。如果没有控制好递归的深度,肯定是会栈溢出的。

尾递归就是,函数调用在末尾,且末尾只能有函数调用,不能有其他操作。这样编译器在编译代码的时候如果发现末尾只有函数调用,不会创建新的栈。也就说最后我们的方法返回就是返回的我们的最终结果。如何才能做到这样呢,其实就需要将前面的计算结果传递到最后,递归出口即是结束,没有回溯的过程。

阶乘的尾递归实现:

 

 /**
* 阶乘尾递归
* @param n
* @return
*/
public static int taiFactorial(int n, int result) {
if (n <= 1) {
return result; //最后返回的即是最终结果
 }
return taiFactorial(n - 1, n * result);//结果往下传
}

 

 裴波那契数列尾递归:

 /**
* 尾递归 裴波那契
* @param pre 上上一次运算出来的结果
* @param result 上一次运算出来结果
* @param n
* @return
*/
public static int tailRecursion(int pre, int result, int n) {
if (n <= 2) {
return result;
}
//对于下一次调用来说 前一次结果 pre + result 前前一次result
return tailRecursion(result, pre + result, n - 1);
}

 

测试下裴波那契数列普通递归和尾递归执行效率:

 public static void main(String[] args){
System.out.println("---裴波那契数列普通递归---");
long time1 = System.currentTimeMillis();
int result = recursion(45);
System.out.println(result);
long time2 = System.currentTimeMillis();
System.out.println(time2-time1);
System.out.println("---裴波那契数列尾递归---");
result = tailRecursion(1,1,45);
System.out.println(result);
long time3 = System.currentTimeMillis();
System.out.println(time3-time2);
}

 

 

所以我们对于递归的使用一定要慎重!!!

 

版权声明
本文为[白露非霜]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/nijunyang/p/12669989.html