有关递归的一些简单经典的算法问题

发表于 | | 阅读次数:

概况

递归是有用的算法思想，他可以把大规模的问题转化成同样性质的小规模问题，只保留问题的源思想，把计算的工作都交给了计算机。
解决递归问题首先要分析问题并确定递归的出口，也就是递归的最后结果，问题的边界值，如果没有这个出口，递归就会无止尽的进行下去，也就没有意义了。

n!问题

体现递归思想最简单的问题就是n!了，

1
2
3
4
5
6
7
8
int fun(int n){
    if(n<0)
      return 0;
    if(n<2)
      return 1;
    else
      return n*fun(n-1);
}

很容易确定递归的出口是n<2的情况,也很容易得到规律

兔子问题

还有一个经典的兔子问题，即Fibonacci数列型
有一对小兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律，假设没有兔子死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？
分析题目可以得到1，1，2，3，5，8，13，… 

1
2
3
4
5
6
7
int fun(int month)
{
    if(month == 1 || month == 2)
        return 1;
    else
        return fun(month - 1) + fun(month -2);
}

可以看到规律从第三个月开始，也就很容易确定边界条件。规律也很简明

跳台阶问题

同样，跳台阶也是个很经典的问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1
2
3
4
5
6
7
8
int fun(int a){
        if (a<2){
            return 1;
        }
        else {
            return fun(a-1)+fun(a-2);
        }
}

很容易确定边界值，当他在第n个台阶上时，他的前一步有两种可能，一种是他跳了两个台阶到达第n个台阶，一种是他跳了一个台阶到达n阶，在这两种情况下的每一种情况又都有相同的两个情况，那么就可以找到这个问题的规律了
变态跳台阶

蜂巢问题

同样的问题还有蜂巢问题，
蜜蜂只从小到大，并从相邻的到达，问到达第五个有多少种方法
蜂巢图片
同样的，到达5有两种方法，到达3和4，而到达3和4也分别有两种方法，即可得到规律，也同样是用了上述算法
再来看一个骨牌问题
骨牌问题
有2n个方格，现有大小为21的骨牌，用骨牌填满方格，如将2*3的方格填满，有多少种填法
可行的方法和不可行的有
方法
可得1,2,3,5…

机器人走方格问题

最后再来看一个走方格的题
有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。
给定两个正整数int x,int y，请返回机器人的走法数目。保证x＋y小于等于12。

1
2
3
4
5
6
7
8
int countWays(int x, int y) {
        // write code here
        if(x <= 0 || y <= 0 || x+ y > 12)
            return 0;
        if(x == 1 || y == 1)
            return 1;
        return countWays(x-1,y)+countWays(x,y-1);
    }

其他

1、编写一个方法用于验证指定的字符串是否为反转字符，返回true和false。请用递归算法实现。（反转字符串样式为”abcdedcba”）。

2、一列数的规则如下: 1、12、123、1234、12345、123456……,求第n个数的递归算法（n<=9）。

3、将一整数逆序，如987654321变为123456789。

要求，当然是不能变成字符串处理，必须使用递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Test{
    public static boolean f1(char[] str,int from ,int to){
        if(from >= to) return true;
        if(str[from++]!=str[to--]) return false;
        return f1(str,from,to);
    }
    public static int f2(int n){
        return (n<=1?1:f2(n-1)*10+n);
    }
    public static int f3(int m, int n){
        return (m<10?m:f3(m/10,n-1)+(m%10)*(int)(Math.pow(10, n-1)));
    }	
    public static void main(String[] args) { 
        String aa="abcddcba";
        char[] bb=aa.toCharArray();
        System.out.println(Test.f1(bb,0,bb.length-1));
        System.out.println(Test.f2(9));
        System.out.println(Test.f3(123456789,9));
    } 
}

总结

1.虽然很方便，但是递归会很占用存储空间，也很耗时，一般递归调用可以处理的算法，通过循环去解决常需要额外的低效处理。

2.现在的编译器在优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的。