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