Java中的递归函数及其应用

递归函数是指在函数中调用自身的过程，可以用于解决一些复杂的问题，如树的遍历、排序、组合等。递归函数简单易懂，但是有时容易导致堆栈溢出，因此需要谨慎使用。

例如，我们可以使用递归函数计算斐波那契数列，代码如下：

public int fibonacci(int n) {
    if(n<=0) return 0;
    if(n==1) return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

上述代码中，当n等于0时，返回0；当n等于1时，返回1；当n大于等于2时，返回前两个数的和。由于每次递归都要计算前两个数的和，因此时间复杂度高达O(2^n)。可以通过使用动态规划来优化时间复杂度。

另一个应用递归函数的例子是树的遍历。树是一种重要的数据结构，常见的遍历方式包括先序遍历、中序遍历、后序遍历和层次遍历。以先序遍历为例，代码如下：

public void preOrder(TreeNode root) {
    if(root==null) return;
    System.out.print(root.val+" ");
    preOrder(root.left);
    preOrder(root.right);
}

上述代码中，如果节点为空，则返回；否则，输出当前节点的值，并递归地对左右子树进行先序遍历。

递归函数还可以用于解决一些组合问题。例如，求解n个元素的所有排列，代码如下：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    boolean[] used=new boolean[nums.length];
    backtrace(res,new ArrayList<>(),nums,used);
    return res;
}

public void backtrace(List<List<Integer>> res,List<Integer> tempList,int[] nums,boolean[] used) {
    if(tempList.size()==nums.length) {
        res.add(new ArrayList<>(tempList));
        return;
    }
    for(int i=0;i<nums.length;i++) {
        if(used[i]) continue;
        used[i]=true;
        tempList.add(nums[i]);
        backtrace(res,tempList,nums,used);
        used[i]=false;
        tempList.remove(tempList.size()-1);
    }
}

上述代码中，我们定义了一个backtrace函数，其中res表示结果列表，tempList表示当前路径，nums表示数组，used表示标记数组，如果一个元素已经被使用，则标记为true；否则，标记为false。其中，如果tempList的长度等于nums的长度，则将tempList添加到结果列表中；否则，遍历nums数组，如果某个元素还没有被使用，则将其添加到tempList中，并递归调用backtrace函数；在结束后，需要将tempList的最后一个元素删除，并将used数组标记为false。

以上是递归函数的一些应用，总之，递归函数可以使代码更加简洁，易于理解，但也需要考虑时间复杂度和堆栈溢出等问题。