递归算法及其案例用途

递归(recursive)算法是一种循环调用自身来解决问题的思想,这是一中比较神奇的方法,你只要能口述循环调用过程,然后设定好基础情况(什么时候开始、什么时候结束),基本根据描述就可以将思路转换成代码,递归算法有以下条件组成:

1、递归开始和结束的基本条件(base case)

2、每次执行需要循环调用自己(也就是找出递归方程),每次调用自己时,执行内容都要向基本条件靠拢,直至满足并跳出基本条件

所以递归定义很重要的一点就是要定义好跳出递归的基本条件,否则极易引起死循环,进去后就出不来,拿一个最简单的故事作为例子来说:

从前有个庙,庙里有个老和尚和一个小和尚,老和尚对小和尚说:从前有个庙,庙里有个老和尚和一个小和尚,老和尚对小和尚说......

这个故事也是一个递归,但是是一个死的递归,因为没有结束的基本条件,故事开始后老和尚会一直重复将这个故事,结果可想而知,如果是

人的话,则老和尚会被累死故事才能结束,如果是计算机,则程序爆掉了执行才能结束,但是如果有结束条件的话就可以避免这种情况发生,比如老和尚

事先对小和尚说好,这个故事只能讲两遍,那当老和尚讲完第二遍后自动结束讲述,程序也就至此结束了。递归算法案例分析: 

1、求解斐波那契数(Fibonacci number) 

斐波那契数就是斐波那契数列中的数,斐波那契数的定义是:f(n)=f(n-1)+f(n-2),基本条件是f(n)=n (n<=1) 

根据描述,可以定义函数: 

def fibonacci(n):

    if(n<=1) return n; // 定义结束条件,这时候不能再调用自己了 

         return fibonacci(n-1)+fibonacci(n-2); // 递归方程,调用自己

 方法定义完毕,可以求解fibonacci(n),当n=1时,fibonacci(1)=1,递归带入,可以求出fibonacci(3)=2,fibonacci(10)=55

2、移动汉诺塔

汉诺塔是有三根柱子,假定是a,b,c,其中a柱子上有n个圆盘,下层的盘要比上一层的大,需要将这n个盘从a通过b柱子移动到c。

递归算法及其案例用途

 

 

根据上面的需求, 对题解进行递归描述:

  a、将a柱上的n-1个圆盘借助c柱移动到b柱上面

  b、将第n个圆盘移动到c柱上面

  c、将b柱上的n-1个圆盘借助a柱移动到c柱上面

所以定义功能如下:

def hanoi(n,a,b,c):

   if(n==1) move(a,c);

  else{

    hanoi(n-1,a,c,b);

    move(a,c);

    hanoi(n-1,b,a,c);

  }

def move( a,c):

     System.out.println("move from "+ a+ " to "+c);

 

3、数据结构的递归定义

这类大部分是树的遍历及相关计算,树的先序、中序、后序遍历可以用以下函数定义:

a、先序遍历

def preOrder(Tree t):

  print(t.value);

  preOrder(t.left);  

  preOrder(t.right);

b、中序遍历

def preOrder(Tree t):

  preOrder(t.left);  

  print(t.value);

  preOrder(t.right);

c、后序遍历

def preOrder(Tree t):

  preOrder(t.right);

  preOrder(t.left);  

  print(t.value);

根据以上模板可以进行一些其他属性的计算,例如求解树的深度,树的深度可以描述为:

  • 基本条件:如果树为null,直接返回0
  • 遍历求解:
    • 求解T.left 的深度 leftDep
    • 求解T.right的深度 rightDep
    • 如果leftDep>rightDep,返回leftDep+1,反之返回rightDep+1

 所以求解树的深度可以定义为:

def TreeDep(Tree t):

   if(t==null) return 0;

   int leftDep=TreeDep(t.left);

   int rightDep=TreeDep(t.right);

   return leftDep>rightDep?leftDep+1:rightDep+1;

 

综上,满足递归调用的两个基本特征有:

a、寻找递归结束的基本条件

b、定义递归解的结构,也就是递归方程,最后将口头描述转换为代码结构

 

 

 

 

上一篇:Docker网络


下一篇:顺序存储二叉树