java编程之递归算法总结

时间:2022-02-28 06:55:04

1.何为递归

个人理解就是自己调用自己,直到满足一个条件结束自己调用自己的过程,这个就是递归。举一个通俗的点的例子:
假设你在一个电影院,你想知道自己坐在哪一排,但是前面人很多,你懒得去数了,于是你问前一排的人「你坐在哪一排?」,这样前面的人 (代号 A) 回答你以后,你就知道自己在哪一排了——只要把 A 的答案加一,就是自己所在的排了,不料 A 比你还懒,他也不想数,于是他也问他前面的人 B「你坐在哪一排?」,这样 A 可以用和你一模一样的步骤知道自己所在的排。然后 B 也如法炮制,直到他们这一串人问到了最前面的一排(或者说问到了知道自己是哪一排的人,预示着调用结束),第一排的人告诉问问题的人「我在第一排」,最后大家就都知道自己在哪一排了

2.递归算法设计的基本思想是:

对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解。

关键要抓住的是:

(1)递归出口
(2)地推逐步向出口逼近

3.常见递归算法

(1)最常见的就是阶乘,比如求5的阶乘,数学公式就是:5*4*3*2*1,代码:

java" id="highlighter_160034">
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package suanfa;
/**
 * Created by tl on 2016/4/10.
 */
public class Digui {
  public static int digui(int n){
    if(n==1||n==0){
      return n;
    }else{
      System.out.println("执行第" + n + "次");
      return n*digui(n-1);
    }
  }
public static void main (String[] args){
  System.out.print(digui(5));
}

(2)求1+2+3+4+5+6+7……+1000的和

?
1
2
3
4
5
6
7
8
9
10
11
12
13
  static int count(int n){
    if(n>0){
      return n+count(n-1);
    }else{
      return 0;
    }
  }
  public static void main(String args[])
  {
    int sum=count(1000);
    System.out.println(sum);
  }
}

(3)1,1,2,3,5,8,13,21,34...,求用递归算第30个数

?
1
2
3
4
5
6
7
8
9
10
11
static int count(int n){
  if(n==1||n==2) {
    return 1;
  }
   return count(n-1)+count(n-2);
}
public static void main(String args[])
{
  int sum=count(30);
  System.out.println(sum);
}

用递归方式实现 99乘法表

代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package test.ms;
public class MultiTable {
 public static void main(String args[]) {
  m(9);
 }
 /**
  * 打印出九九乘法表
  * @param i
  */
 public static void m(int i) {
  if (i == 1) {
   System.out.println("1*1=1 ");
  } else {
   m(i - 1);
   for (int j = 1; j <= i; j++) {
    System.out.print(j + "*" + i + "=" + j * i + " ");
   }
   System.out.println();
  }
 }
}

用Java打印九九除法表代码分析

递归的效率问题及递归与循环比较

1.所谓的递归慢到底是什么原因呢?

大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括:局部变量、形参、调用函数地址、返回值。那么,如果递归调用N次,就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。

2.用循环效率会比递归效率高吗?

递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高,递归和循环是两码事,递归带有栈操作,循环则不一定,两个概念不是一个层次,不同场景做不同的尝试。

2.1递归算法:

优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的话,否则你更晕)

缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。

2.2循环算法:

优点:速度快,结构简单。

缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

2.3递归算法和循环算法总结:

1.一般递归调用可以处理的算法,也通过循环去解决常需要额外的低效处理。

2.现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。

3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成递归往往是好的。(例如:求阶乘的递归实现与循环实现。)

3.那么递归使用的栈是什么样的一个栈呢?

首先,看一下系统栈和用户栈的用途。

3.1系统栈(也叫核心栈、内核栈)是内存中属于操作系统空间的一块区域,其主要用途为:(1)保存中断现场,对于嵌套中断,被中断程序的现场信息依次压入系统栈,中断返回时逆序弹出;(2)保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。

3.2用户栈是用户进程空间中的一块区域,用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。

我们编写的递归程序属于用户程序,因此使用的是用户栈。

总结

以上就是本文关于java编程之递归算法总结的全部内容,希望对大家有所帮助。有什么问题可以随时留言,小编会及时回复大家的。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/tomcat_2014/article/details/51113740