常用的算法-递归

最近开始复习数据结构和算法的相关知识，以前学习数据结构的时候使用C语言实现其中的数据存储结构。已经学习Java有一年多了，总是忙于写代码，学习新知识，思考总是一瞬间的事，然而这样的境遇总是让我在学习Java软件开发的过程中遇到很多问题，为此牺牲了很多时间。

      突然决定启用51Blog来记录每一次尝试，探索，错误的历经。

      递归算法的核心在于：

     方法能够通过自身的调用得到执行，并且总会得到调用结束的出口。

     递归（recursion）：神奇的算法

      递归编程的注意事项：
      递归代码会精彩而且会很短，但却能够完成很复杂的工作；
      大部分代码是用来对负责底层工作的递归方法进行支持。
   

    递归和迭代的区别：

    迭代：一种用循环来描述需要的重复进行的操作的编程方法。
    递归：一种通过调用某个方法来描述需要重复进行的操作的编程方法，该方法的一个基本特  征是：它可以调用自身

1. iteration algorithm：  
2.         public static void writeStar(int n)  
3.         {  
4.             for(int i=1;i<n;i++)  
5.             {  
6.                 System.out.print(" * ");  
7.             }  
8.         System.out.println();  
9.         }  
10.     recursion algorithm:  
11.         public static void writeStar(int n)  
12.         {  
13.             if(n==0)  
14.             {  
15.                 //base case  
16.                 System.out.println();  
17.             }  
18.             else 
19.             {  
20.                 //recursion case  
21.                 System.out.print(" * ");  
22.                 writeStar(n-1);  
23.             }  
24.         } 

 递归结构：
  基本情况(base case) 递归情况(recursion case)
  基本情况：
    一种简单到不需要递归调用就可以直接解决的情况
  递归情况：
   一种需要把整个问题转化成为一个相同种类，比较简单的，而且可以通过递归调用
  来解决问题的情况
  
 函数调用用的是：栈内存
 主函数的运行用的是：堆内存

1. 整数的幂运算：  
2.         public static int pow(int x,int y)  
3.         {  
4.             if(y==0)  
5.             {  
6.                 //base case  
7.                 return 1;  
8.             }  
9.             else 
10.             {  
11.                 //recursion case  
12.                 return x*pow(x,y-1);  
13.             }  
14.         }  
15.         递归解决方法过程：  
16.         pow(3,5)  =  3*pow(3,4)  
17.         |   pow(3,4)  =  3*pow(3,3)  
18.         |   |   pow(3,3)  =  3*pow(3,2)  
19.         |   |   |   pow(3,2)  =  3*pow(3,1)  
20.         |   |   |   |   pow(3,1)  =  3*pow(3,0)  
21.         |   |   |   |   |   pow(3,0)  =  1 
22.         |   |   |   |   pow(3,1)  =  3*1  =  3 
23.         |   |   |   pow(3,2)  =  3*3  =  9 
24.         |   |   pow(3,3)  =  3*9  =  27 
25.         |   pow(3,4)  =  3*27  =  81 
26.         pow(3,5)  =  3*81  =  243 

当然递归对于问题的理解和提炼要求是比较高的。

我们使用递归解决的问题：

1.在数据结构中的非线性存储结构中的树，二叉树的前序遍历，中序遍历，后序遍历等问题的解决中就使用了递归算法，这样使解决问题的编码很方便。

2.遍历指定目录下的所有文件

3.二分法排序等等

本文转自 secondriver 51CTO博客，原文链接：http://blog.51cto.com/aiilive/838542，如需转载请自行联系原作者