常用的算法-递归

简介:

最近开始复习数据结构和算法的相关知识,以前学习数据结构的时候使用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,如需转载请自行联系原作者

相关文章
|
8月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
3月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
|
8月前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
|
4月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
82 1
|
4月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
73 0
|
6月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔
|
7月前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
108 1
|
6月前
|
算法
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
156 0
|
6月前
|
算法
【算法】递归、搜索与回溯——简介
【算法】递归、搜索与回溯——简介
|
8月前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
171 7

热门文章

最新文章