java递归算法面试题真题

说到java中的递归算法这个话题，java程序员肯定不陌生，是一种基础性的编写代码的方式。Java递归算法是一种直接或者间接地调用自身算法的过程，在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解，因此在java面试中，往往会考察到这方面的内容，这篇文章汇总了几道java递归算法面试题，都是在互联网公司出现过的面试题，大家可以做个学习参考。

1、java递归算法的特点是什么？

答：递归算法解决问题的特点有

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

2、使用递归需要满足什么条件？

答：（1）有反复执行的过程（调用自身）

    （2）有跳出反复执行过程的条件（递归出口）

3、请使用递归算法计算n！

答：

package com.bjsxt;
import java.io.File;
public class $ {
public static void main(String[] args) {
        String path = "D:/301SXT";
        test(path);
    }
    private static void test(String path) {
        File f = new File(path);
        File[] fs = f.listFiles();
        if (fs == null) {
            return;
        }
        for (File file : fs) {
            if (file.isFile()) {
                System.out.println(file.getPath());
            } else {
                test(file.getPath());
            }
        }
}

4、使用递归算法输出某个目录下所有文件和子目录列表

答：

package com.bjsxt;
import java.io.File;
public class $ {
public static void main(String[] args) {
        String path = "D:/301SXT";
        test(path);
    }
    private static void test(String path) {
        File f = new File(path);
        File[] fs = f.listFiles();
        if (fs == null) {
            return;
        }
        for (File file : fs) {
            if (file.isFile()) {
                System.out.println(file.getPath());
            } else {
                test(file.getPath());
            }
        }
}

5、用递归实现买汽水：一个人买汽水，一块钱一瓶汽水，三个瓶盖可以换一瓶汽水，两个空瓶可以换一瓶汽水，问20块钱可以买多少汽水？

答：首先分析：一瓶汽水:1soda = 1cap +1bottle；两个空瓶:2bottle = 1soda；三个瓶盖:3cap = 1soda;

那么递归退出条件就是: cup<3&&bottle<2 &&soda<1

因为在这个过程中，三个元素soda、cup、bottle都有连续的变化，所以递归调用时要将三个参数都传进去。

方法体如下:

private int  Total(int soda,int cap,int bottle){

}

1

2

完整代码如下:

public class DiGui02 {
	public static void main(String[] args) {
		int total = Total(20, 0, 0);
		System.out.println(total);
	}
	public static int Total(int Total,int caps,int bottles){
        caps%=3;  bottles%=2;
        caps+=Total;  bottles+=Total;
        if(caps<3&&bottles<2){
            return Total;
        }
        else{
            return Total(caps/3+bottles/2,caps,bottles)+Total;
        }
    }
}

6、java递归算法的二叉树的反转的应用

答：

public static Node invertTree(Node root) {
    	Node tmpNode=new Node(0);
		if(root==null){
			return null;
		}else{
			tmpNode=root.leftChild;
			root.leftChild=root.rightChild;
			root.rightChild=tmpNode;
			invertTree(root.leftChild);
			invertTree(root.rightChild);
		}
		
		return root;  
    }

7、java递归算法的链表的反转应用代码？

答：

public static Node Reverse1(Node head) {
		// head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
		if (head == null || head.getNextNode() == null) {
			return head;// 若为空链或者当前结点在尾结点，则直接还回
		}
		Node reHead = Reverse1(head.getNextNode());// 先反转后续节点head.getNext()
		head.getNextNode().setNextNode(head);// 将当前结点的指针域指向前一结点
		head.setNextNode(null);// 前一结点的指针域令为null;
		count++;
		return reHead;// 反转后新链表的头结点
	}

8、我们都知道6的二进制是110,那么程序是怎么执行的呢？

答：代码示例

public static void main(String[] args) {
        toBin(6);
    }
    private static void toBin(int num) {
        if (num>0){
            //取余
            System.out.println(num%2);
            toBin(num/2);
        }
}

以上的8道题就是java递归算法面试题了，因为算法是需要在具体的代码中显示出来的，所以基本上java面试中对递归算法方面知识的考察都是直接写代码。Java技术又是一门实操性的专业，所以需要各位程序员包括java零基础的朋友多多在实践中练习java递归算法方面的知识，才能达到融会贯通，写代码时能游刃有余。