java递归算法经典实例-不念博客

一、引言

递归是一种在编程中常见的解决问题的方法，它涉及到函数直接或间接调用自身。

递归可以将复杂的问题分解为更简单的子问题，直到子问题可以简单地直接解决。

在本文中，不念将会通过两个经典实例：斐波那契数列和汉诺塔问题，深入探索Java中的递归算法。

二、斐波那契数列

斐波那契数列是一个经典的递归问题，它是一个数列：0、1、1、2、3、5、8、13、21、34……从第3项开始，每一项都等于前两项之和。

在Java中，我们可以通过递归函数来实现斐波那契数列的生成。

public class Fibonacci {

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

    public static void main(String[] args) {
        System.out.println(fib(10));
    }
}

三、汉诺塔问题

汉诺塔问题是另一个经典的递归问题。它描述的是一个有三根柱子和n个不同大小的盘子的问题，盘子可以滑入任何一根柱子。

一开始，所有盘子都在一根柱子上按大小顺序叠放（最大的在底部，最小的在顶部）。

目标是把所有盘子移到另一根柱子上，但在移动过程中不能出现大盘子在小盘子上的情况。

public class Hanoi {
    public static void move(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("Move disk 1 from rod " + from + " to rod " + to);
            return;
        }
        move(n - 1, from, aux, to);
        System.out.println("Move disk " + n + " from rod " + from + " to rod " + to);
        move(n - 1, aux, to, from);
    }

    public static void main(String args[]) {
        int n = 4; // Number of disks
        move(n, 'A', 'C', 'B');  // A, B and C are names of rods
    }
}