java递归算法面试题及答案

1. 递归算法简介

递归是编程中的一种非常重要的思想。

简单地说，如果一个函数在其内部调用自己，那么这个函数就是递归函数。

在Java中，递归算法广泛应用于解决一些复杂的问题，如树的遍历、求解阶乘等。

2. 面试题一：计算斐波那契数列

题目：编写一个Java函数，使用递归算法计算斐波那契数列的第n项。

解答：

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

3. 面试题二：计算阶乘

题目：编写一个Java函数，使用递归算法计算n的阶乘。

解答：

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

4. 面试题三：反转字符串

题目：编写一个Java函数，使用递归算法反转一个字符串。

解答：

public String reverseString(String str) {
    if (str.isEmpty())
        return str;
    else
        return reverseString(str.substring(1)) + str.charAt(0);
}
public String reverseString(String str) {
    if (str.isEmpty())
        return str;
    else
        return reverseString(str.substring(1)) + str.charAt(0);
}
public String reverseString(String str) {
    if (str.isEmpty())
        return str;
    else
        return reverseString(str.substring(1)) + str.charAt(0);
}

5. 注意递归算法的缺陷

在使用递归算法时，需要注意的一点是，对于大量数据的处理，递归可能会导致堆栈溢出。

因此，适当的情况下，我们应该考虑使用迭代等其他算法替代。