递归算法及其案例用途

本文主要是介绍递归算法及其案例用途，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

递归(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、定义递归解的结构，也就是递归方程，最后将口头描述转换为代码结构

这篇关于递归算法及其案例用途的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！