Java中常用的递归算法

Java中常用的递归算法

• 一、前言
• • 1. 阶乘计算
  • 2. 斐波那契数列
  • 3. 二叉树遍历
  • 4. 汉诺塔问题
  • 5. 组合生成

---

一、前言

Java 中常用的递归算法涵盖了许多领域，从简单的数据结构操作到复杂的算法和问题求解。以下是一些常见的递归算法示例：

1. 阶乘计算

计算一个非负整数的阶乘。例如，n! = n * (n-1) * ... * 1。

public int factorial(int n) {     if (n == 0 || n == 1) {         return 1;     } else {         return n * factorial(n - 1);     } } 

2. 斐波那契数列

返回第 n 个斐波那契数。斐波那契数列的定义是 fib(n) = fib(n-1) + fib(n-2)，其中 fib(0) = 0，fib(1) = 1。

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

3. 二叉树遍历

二叉树的前序、中序和后序遍历都可以用递归实现。

// 二叉树节点定义 class TreeNode {     int val;     TreeNode left;     TreeNode right;     TreeNode(int x) { val = x; } }  // 前序遍历 public void preorderTraversal(TreeNode root) {     if (root != null) {         System.out.print(root.val + " ");         preorderTraversal(root.left);         preorderTraversal(root.right);     } }  // 中序遍历 public void inorderTraversal(TreeNode root) {     if (root != null) {         inorderTraversal(root.left);         System.out.print(root.val + " ");         inorderTraversal(root.right);     } }  // 后序遍历 public void postorderTraversal(TreeNode root) {     if (root != null) {         postorderTraversal(root.left);         postorderTraversal(root.right);         System.out.print(root.val + " ");     } } 

4. 汉诺塔问题

经典的递归问题，将 n 个盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。

public void hanoi(int n, char from, char to, char aux) {     if (n == 1) {         System.out.println("Move disk 1 from " + from + " to " + to);     } else {         hanoi(n - 1, from, aux, to);         System.out.println("Move disk " + n + " from " + from + " to " + to);         hanoi(n - 1, aux, to, from);     } } 

5. 组合生成

生成长度为 k 的从 n 个元素中选取的所有组合。

public void combinations(List<List<Integer>> result, List<Integer> temp, int start, int n, int k) {     if (k == 0) {         result.add(new ArrayList<>(temp));         return;     }      for (int i = start; i <= n - k + 1; i++) {         temp.add(i);         combinations(result, temp, i + 1, n, k - 1);         temp.remove(temp.size() - 1);     } } 

这些例子展示了递归在不同问题中的应用，包括数学运算、数据结构遍历以及组合生成。在实际应用中，递归算法通常需要考虑性能、边界条件和栈溢出等问题。