Java中的递归函数及应用案例

递归是一种在函数中调用自身的编程技巧，常用于对数据结构（如树、列表、图等）的处理。Java中的递归函数具有以下特点：

1. 在递归函数中，存在一种递归基，它表示当达到某个条件时，递归函数不再调用自身，从而终止递归。

2. 在递归函数中，每次递归调用时传入的参数不同，因此可以完成不同的操作，从而避免了代码的重复。

Java中的递归函数有许多应用案例，以下是其中的几个：

1. 求阶乘

阶乘是一个自然数的阶乘等于它与前面自然数的乘积。例如，5! = 5 × 4 × 3 × 2 × 1 = 120。利用递归函数计算阶乘可以写成如下代码：

public int fac(int n) {

    if (n == 0) {

        return 1;

    } else {

        return n * fac(n - 1);

    }

}

在该代码中，当n等于0时，返回1，从而完成递归，否则返回n与fac(n-1)的乘积。

2. 汉诺塔

汉诺塔是一种经典的递归问题，它的规则是将一个塔从A柱子上全部移动到C柱子上，其中还有B柱子，初始时A柱子上有n个盘子，盘子大小依次递增。移动时必须满足以下规则：

1）每次只能移动一个盘子。

2）移动时必须保证大盘子在下面，小盘子在上面。

3）任何一时刻，大盘子都不能放在小盘子上面。

需要用递归实现汉诺塔的代码如下：

public void hanoi(int n, char a, char b, char c) {

    if (n == 1) {

        System.out.println("第" + n + "个盘子从" + a + "移动到" + c);

    } else {

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

        System.out.println("第" + n + "个盘子从" + a + "移动到" + c);

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

    }

}

在该代码中，当n等于1时，直接将第一个盘子从A柱子上移到C柱子，否则将前n-1个盘子从A柱子利用C柱子移到B柱子，将第n个盘子从A柱子移到C柱子，最后将前n-1个盘子从B柱子利用A柱子移到C柱子，从而完成汉诺塔递归。

3. 深度优先遍历

深度优先遍历是图的一种遍历方法，具体做法是从一个顶点开始，沿着一条路走到底，再依次回溯到前面的结点，直到所有结点都被访问过。使用递归的方式实现深度优先遍历的代码如下：

public void dfs(int[][] graph, int[] vis, int u) {

    vis[u] = 1;

    System.out.print(u + " ");

    for (int v = 0; v < graph.length; v++) {

        if (graph[u][v] == 1 && vis[v] == 0) {

            dfs(graph, vis, v);

        }

    }

}

在该代码中，vis数组表示节点是否被访问过，初始化为0。u表示访问的起始节点，graph表示图的邻接矩阵，当graph[u][v]等于1时，说明节点u与节点v之间有一条边。在递归时，将vis[u]置为1，代表节点u已经被访问过。然后遍历节点u的所有邻接节点v，如果v未被访问过，则递归遍历节点v。

Java的递归函数应用十分广泛，重要性不言而喻。学习递归函数首先需要明确递归函数的递归基与递归调用之间的递归关系，并且了解常见的递归应用案例，才能更好地运用递归函数进行编程。