算法基本思想(三)——递归算法思想

移动UI设计

  递归算法(recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。使用递归算法可以简化代码,提高程序的可读性,但是不合理的递归可能会导致程序的执行效率变低。

  递归算法思想

  递归算法就是在程序运行当中不断地调用自身来达到求解问题的方法,不断调用自身就需要待求解的问题能够分成相同问题的一个子问题,这样通过多次调用就可以达到求解的目的。

  递归调用是一个函数在他的函数体内调用自身的函数的方式,这种函数也称为“递归函数”。在递归函数中,主函数又是被调函数。执行递归函数反复调用自身,每调用依次就进入新的一层。

  递归可以分为两种情况:

  直接调用:在函数中调用函数本身间接调用:间接地调用一个函数,比如fun_a调用fun_b,fun_b调用fun_a。一般用得不多。编写递归函数必须要用到if语句,在未执行递归调用前返回。否则,在函数调用递归后他将陷入死循环,这是最容易犯的错误。

  递归的三要素

  明确递归终止条件给出递归终止时的处理办法 提取具有相同问题的子问题,减小问题的规模优点:代码清晰简洁,可读性好

  缺点:大部分递归并没有明显减小代码模块和节省内存空间,递归方式往往要比非递归运行速度慢一些。

  大部分能够使用递归完成的程序都可以使用非递归的方式完成。

  示例

  最简单的一个使用递归的问题就是阶乘的计算,阶乘利用公式可以描述为

  将问题分解成相同问题的子问题,如果表示的阶乘,那么阶乘可以表示为

  程序同样可以利用递归和非递归两种方式编写。

  from time import *#非递归方式def nofact(n): ans = 1 for i in range(n): if i==0: ans = 1 else: ans = ans*(i+1) return ans#递归方式def fact(n): if n<=1: return 1 else: ans = n*fact(n-1) return ansif __name__ == '__main__': n = int(input('请输入要求阶乘的一个整数:')) begintime = time() fa = nofact(n) time = time() print('非递归计算结果为:{fa}'.format(fa = fa)) print('非递归耗时:{ti}'.format(ti=time - begintime)) begintime = time() fa = fact(n) time = time() print('递归计算结果为:{fa}'.format(fa=fa)) print('递归耗时:{ti}'.format(ti=time - begintime))程序运行结果为

  只有在足够大的时候才可以区分出时间的差异。

标签: 移动UI设计