Java中的递归函数使用实例讲解

发布时间：2023-06-03 10:58:06

Java是一种面向对象的编程语言，其基于对象的编程特性很适合使用递归函数，这也是Java中递归函数使用的非常普遍的一个原因。递归函数在计算机编程中用来解决重复问题的方法，即每次将传递给函数的输入参数进行计算，并且将结果传递给自己的函数，这个过程一直持续到达到某种结束条件。

递归函数的使用既有优点也有缺点，其中优点是递归函数使得代码更清晰，可读性更强，也让许多算法更容易实现和应用，另一个重要的优点是...

接下来我们就通过一个实例来学习Java中递归函数的使用方式。这个例子是一个气球爆炸的问题。题目如下：一堆气球排成一排，每个气球都标记有不同数量的硬币。玩家们通过猜测打爆了一些气球，每次击破一个气球可以获得指定数量的硬币。但是，一旦气球被打破，与之相邻的两个气球的价值就会改变。编写一个程序来求玩家最多可以获得多少硬币。

首先我们可以给一些气球一个初始值：

public void maxCoins(int[] nums) {

//假设气球前后都是1，将气球数加一

int n = nums.length+2;

//新建数组将填充气球

int[] new_nums = new int[n];

for(int i=0;i<n-2;i++)

new_nums[i+1] = nums[i];

new_nums[0] = new_nums[n-1] = 1;

int[][] dp = new int[n][n];

//计算气球价值

for(int len = 3;len<=n;len++){

for(int start=0;start<=n-len;start++){

int end = start+len-1;

for(int k=start+1;k<end;k++){

dp[start][end] = Math.max(dp[start][end], new_nums[start]*new_nums[k]*new_nums[end]+dp[start][k]+dp[k][end]);

}

System.out.println(dp[0][n-1]);

}

在这个函数中，我们假设每个气球前后都是1，并创建一个新的数组来存储气球，再根据这个新数组的长度创建一个n维的数组dp。

接下来，我们将定一个递归函数来实现动态规划，这个递归函数用两个参数表示气球的起始和结束点：

private int maxCoins(int[] nums, int start, int end, int[][] dp){

if(start+1==end) return 0;

if(dp[start][end]>0) return dp[start][end];

for(int i=start+1;i<end;i++){

dp[start][end] = Math.max(dp[start][end], nums[start]*nums[i]*nums[end]+maxCoins(nums,start,i,dp)+maxCoins(nums,i,end,dp));

}

return dp[start][end];

}

为了避免重复计算，我们使用一个 n x n 的dp数组存储气球的计算结果，如果dp[start][end]>0，表示该结果已经被计算过，直接返回。

最后我们输出收益最大的值即可：

System.out.println(maxCoins(new_nums,0,new_nums.length-1,new int[new_nums.length][new_nums.length]));

最终代码如下：

public class Balloon {

public static void main(String[] args) {

int[] nums = {3,1,5,8};

maxCoins(nums);

}

public static void maxCoins(int[] nums) {