递归面试题目总结

   【摘要】  递归具有很多的优点,它可以将一个大的问题划分为小的子问题,然后再逐步细分,达到解决问题的目的。递归的实现借用了栈桢的建立和销毁,所以它是很方便的。但是递归也有一些缺点,比如说,如果递归调用太深,栈桢消耗过大,就会出现栈溢出的问题,因此,在我们使用递归之前,应该仔细考虑适不适合使用递归来解决这个问题。同时,递归深度太深,也会使得运算时间大大增加,所以递归的结论一般都是在理论的基础上的。这篇文章整理了我最近做过的关于递归的一些经典问题,希望对你们会有所帮助。
 

1 吃苹果问题

每天吃三分之一再加一个,到最后一天只有一个。

public static void main(String[] args) {
        System.out.println(getNum(3));
    }
    static int dp = 0;

    public static int getNum(int n) {
        if (n == 1) {
            return 1;
        }
        dp = 1 + getNum(n - (n / 3 + 1));
        return dp;
    }

2 数组中最大值

static int res = Integer.MIN_VALUE;

    public static int getMax(int[] nums, int n) {
        if (n == 0) {
            return res;
        }
        res = Math.max(nums[n], getMax(nums, n - 1));
        return res;
    }

3 用递归调用的方法求n!

public class Test23 {
    public static void main(String[] args) {
        System.out.println(fo(5));
    }
    public static int fo(int n){
        if(n<2){
            return 1;
        }else{
            return n*fo(n-1);
        }
    }
}

4 //用递归法求和1+2+3+4......+n

public class Test23 {
    public static void main(String[] args) {
        System.out.println(add(5));
    }
    public static int add(int m){
        if(m < 2){
            return 1;
        }else{
            return m+add(m-1);
        }
    }
}

5 一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少, 用递归算法实现。

public class Test23 {
    public static void main(String[] args) {
        System.out.println(find(7));
    }
    public static int find(int n){
        if (n <= 0){
            return 0;
        } else if(n > 0 && n <= 2){
            return  1;
        }
        return find(n-1)+find(n-2);
    }
}

6  将一整数逆序后放入一数组中(要求递归实现) Ex : 1234 变为 {4,3,2,1}

public class Test23 {
    public static void main(String[] args) {
        int[] res = new int[4];
        revert(res,0,1234);
        System.out.println(Arrays.toString(res));
    }
    static int revert(int rs[], int i, int number) {
        if (i < rs.length) {
             rs[i] = number % 10;
             number = (number - number % 10) / 10;
            return revert(rs, i + 1, number);
        } else {
            return 0;
        }

    }
}

7 递归实现回文判断(如:abcdedbca就是回文,判断一个面试者对递归理解的简单程序)

public class Test23 {
    public static void main(String[] args) {
        int[] res = new int[4];
        String str = "abcba";
        //"abcdedbca"
        System.out.println(loopWord(str,0));
    }
    static boolean loopWord(String str, int i) {
        if (str.charAt(i) == str.charAt(str.length() - 1 - i)) {
            if (i == (str.length() + 1) / 2) {
                return true;
            }
            return loopWord(str, i + 1);
        } else {
            return false;
        }
    }
}

8 分解成质因数(如435234=251*17*17*3*2  华为笔试题)

public class Test23 {
    public static void main(String[] args) {
        int[] res = new int[4];
        String str = "abcba";
        //"abcdedbca"
        dividePrimeToFactors(435234, 2);
    }
    static int dividePrimeToFactors(int num, int factor) {
        while ((factor < num) && (num % factor != 0)) {
            factor++;
        }
        System.out.print(factor + " ");
        num = num / factor;
        if (factor >= num) {
            return factor;
        }
        return dividePrimeToFactors(num, factor + 1);
    }
}

9  喝啤酒问题

public class Test23 {
    public static void main(String[] args) {
        System.out.println(help(8));
    }

    public static int sum = 0;
    public static int help(int money){
        int count = (int) Math.floor(money/2);
        //喝几瓶
        int curPing = count;
        //空瓶数
        int curGai = count;
        //瓶盖数
        helper(count,curPing,curGai);
        return sum;
    }
    public static void helper(int count,int curPing,int curGai){
        if(curPing<2&&curGai<4){
            //递归终结条件
            sum = count;
            return;
        }
        if(curGai>=4){
            int curAdd1 = (int) Math.floor(curGai/4);
            count+=curAdd1;
            //增加的瓶子数
            curGai=curAdd1+curGai%4;
            //增加的瓶数+剩余于的瓶盖;
            curPing+=curAdd1;
        }
        if(curPing>=2){
            int curAdd2 = (int) Math.floor(curPing/2);
            count+=curAdd2;
            curPing=curAdd2+curPing%2;
            //增加的瓶数+剩余于空瓶;
            curGai+=curAdd2;
        }
        helper(count,curPing,curGai);
    }
}

图例讲解

一.递归法求斐波那契数列

在这里我先要说的是,递归法求菲波那切数列并不是一个很好的解决办法,如果你要问我为什么,其实前面也提到了,如果求第10个或者第20数的值,还好,但是如果要求第100个呢?这样做消耗的栈桢将会是很大的,我先拿一张图来大概表示一下栈桢的消耗过程

并且,随着递归次数越多,时间复杂度也会越高,综合这两点,我觉得用循环来代替递归是很明智的选择。当然我也不是就说递归不好了,有时候用递归解决问题还是相当给力的。

菲波那切数列求值,思想就是每一个值都是前面两个数的和,因此放到递归里面就可以分解为子问题,求前两个数字的结果,就这样一直往前走,直到遇到1就返回,然后再把值一个个相加,得到最后的结果。
 

int fabonaci(int i)
{
	if(i<=0)
		return 0;
	else if(i==1 ||i==2)
		return 1;
	else
		return(fabonaci(i-1)+fabonaci(i-2));
}

二.递归计算n的k次方

递归一般都是逆序思想,要求n的k次方,那就先求n的k-1次方,而要求n的k-1次方,就要求k-2次方,就这样一直给前走,直到求n的0次方为终止条件。而n的k次方就是k个n相乘,所以,只需要每次返回时乘上n就可以得到最终的结果

int sqrt(int n,int k)
{
	if(k==0)
       return 1;
	else
	   return n*sqrt(n ,k-1);
}

三.递归计算一个数字每一位相加的结果

要想得到一个数字的每一位,最简单的办法就是%10 /10,如此反复几次,直到i==0为止,而要让每一位都相加,那就在 return 后面返回一个范围缩小的值 加上%10的值,当函数得到第一位数字时就开始返回结果,这个递归问题是线性的,所以栈桢消耗并不会很大。

public class Test23 {
    public static void main(String[] args) {
        System.out.println(DigitSum(9878));
    }
    public static int DigitSum(int i)
    {
        if(i==0){
            return 0 ;
        } else {
            if((i/10)>0)
            {
                System.out.println(i%10);
            }else{
                System.out.println(i%10);
            }
            return (i%10+DigitSum(i/10));
        }
    }

}

四 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:

输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
class Solution {
    public void reverseString(char[] s) {
        help(0,s);
        System.out.print(s);
    }
    public void help(int index,char[] s){
        if(s==null||index>s.length/2-1){
            return;
        }
        help(index+1,s);
        char a=s[index];
        s[index]=s[s.length-index-1];
        s[s.length-index-1]=a;
    }
}

五 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return Math.max(left,right)+1;
    }
}

六 平衡二叉树

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

public class Solution {
   public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if(Math.abs(left -right)>1){
            return false;
        }
        return true;
    }
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

 

参考文献

相信下面3个网址足够解决了递归函数时间复杂度的分析了

1.https://www.cnblogs.com/aademeng/articles/7044312.html

2.https://www.cnblogs.com/carazk/p/5860334.html

3.https://blog.csdn.net/so_geili/article/details/53444816#3.3