Java使用递归解决算法问题的实例讲解

解释：程序调用自身的编程技巧叫做递归。
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

递归的三个条件：
1.边界条件
2.递归前进段
3.递归返回段

当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

下面通过两个示例程序来说明：
1.使用Java代码求5的阶乘。（5的阶乘=5*4*3*2*1）

package org.wxp.recursion;
/**
 * 计算5的阶乘(result = 5*4*3*2*1)
 * @author Champion.Wong
 */
public class Test01 {
 public static void main(String[] args) {
  System.out.println(f(5));
 } 

 public static int f(int n) {
  if (1 == n)
   return 1;
  else
   return n*(n-1);
 }
}

此题中，按照递归的三个条件来分析：
(1)边界条件：阶乘，乘到最后一个数，即1的时候，返回1，程序执行到底；
(2)递归前进段：当前的参数不等于1的时候，继续调用自身；
(3)递归返回段：从最大的数开始乘，如果当前参数是5，那么就是5*4，即5*(5-1)，即n*(n-1)

2.使用Java代码求数列：1，1，2，3，5，8......第40位的数

package org.wxp.recursion;
/**
 * 求数列：1，1，2，3，5，8......第40位的数
 */
public class Test_02_Fibonacci {
  public static void main(String[] args) {
    System.out.println(f(6));
  } 

  public static int f(int n ) {
    if (1== n || 2 == n)
      return 1;
    else
      return f(n-1) + f(n-2);
  }
}

3.问题描述：求解Fibonacci数列的第10个位置的值？ （斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*））
程序清单：

/**
 *<p>Title:Java递归算法实例</p>
 *<p>Description:利用递归算法求解Fibonacci数列第5个数的值</p>
 *<p>Filename:Fibonacci.java</p>
 */
public class Fibonacci
{
 /**
 *方法描述：求解Fibonacci数列的递归算法
 *输入参数：int n
 *返回类型：int
 */
 public static int fun(int n)
 {
  if(1==n || 2==n)
  {
  return 1;
  }
  else
  {
  return (fun(n-1) + fun(n-2));
  }
 } 

 /**
 *方法描述：主方法
 *输入参数：String[] args
 *返回类型：void
 */
 public static void main(String[] args)
 {
 System.out.println(fun(10));
 }
}

运行结果如下所示：

代码如下:

55

赞 (0)

相关推荐

  • Java数据结构及算法实例：汉诺塔问题 Hanoi

    /** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱

  • java实现fibonacci数列学习示例分享(斐波那契数列)

    输出:1  1  2  3  5 复制代码 代码如下: public class FibonaciTest { public static void main(String[] args) {  Fibonaci(5); } public static void Fibonaci (int count) { int[] num = new int[count];  num[0] = num[1] = 1; for (int i = 2; i < count; i++) {   num[i] =

  • java编程经典案例之基于斐波那契数列解决兔子问题实例

    java编程经典案例之基于斐波那契数列解决兔子问题实例

    本文实例讲述了java基于斐波那契数列解决兔子问题.分享给大家供大家参考,具体如下: 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? package com.java.recursion; /** * @描述 三种方法实现斐波那契数列 * @项目名称 Java_DataStruct * @包名 com.java.recursion * @类名 Fibonacci * @author chenli

  • 浅谈java实现背包算法(0-1背包问题)

    0-1背包的问题 背包问题(Knapsack problem)是一种组合优化的NP完全问题.问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高.问题的名称来源于如何选择最合适的物品放置于给定背包中. 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放. 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是: f[i][v]=max{ f[i-1][v], f

  • java基于递归算法实现汉诺塔问题实例

    本文实例讲述了java基于递归算法实现汉诺塔问题.分享给大家供大家参考,具体如下: package test; import java.util.List; import java.util.ArrayList; import java.util.Scanner; import sun.net.www.content.audio.x_aiff; /** * @author 年浩 * */ public class test { public static void move(char x,cha

  • java实现斐波那契数列的3种方法

    先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案.去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧,提前做好准备还是很重要滴),面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了,悲催!!),面试快结束的时候面试官问的我问题就是关于费波那西数列,当时头脑完全浆糊,只知道要设置三个变量或者用List先初始化,当写到for循环的

  • java数学归纳法非递归求斐波那契数列的方法

    本文实例讲述了java数学归纳法非递归求斐波那契数列的方法.分享给大家供大家参考.具体如下: Integer能表示的最大值为 2147483647 大概是21.4亿,这里没有考虑溢出情况(当size为983时就会溢出)! import java.util.List; import java.util.ArrayList; /** * @author jxqlovejava * 斐波那契数列 */ public class Fibonacci { public static List<Intege

  • Java递归算法经典实例（经典兔子问题）

    Java递归算法经典实例（经典兔子问题）

    题目:古典问题:3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 分析:首先我们要明白题目的意思指的是每个月的兔子总对数:假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子, 那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1.0.0,第二个月分别为0.1.0, 第三个月分别为1.0.1,第四个月分别为,1.1.1,第五个月分别为2.1.2,第六个月分别为3.2.3,第

  • Java基于循环递归回溯实现八皇后问题算法示例

    Java基于循环递归回溯实现八皇后问题算法示例

    本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

  • java多线程解决生产者消费者问题

    本文实例讲述了java多线程解决生产者消费者问题的方法.分享给大家供大家参考.具体分析如下: 题目是这样的: 采用Java 多线程技术,设计实现一个符合生产者和消费者问题的程序.对一个对象(枪膛)进行操作,其最大容量是12颗子弹.生产者线程是一个压入线程,它不断向枪膛中压入子弹:消费者线程是一个射出线程,它不断从枪膛中射出子弹. 要求: (1)给出分析过程说明. (2)程序输出,要模拟体现对枪膛的压入和射出操作: (2)设计程序时应考虑到两个线程的同步问题. 这个和著名的生产者消费者问题几乎是一

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

随机推荐