概况

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

n!问题

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

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,…

int fun(int month)
{
    if(month == 1 || month == 2)
        return 1;
    else
        return fun(month - 1) + fun(month -2);
}

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

跳台阶问题

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

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也分别有两种方法,即可得到规律,也同样是用了上述算法
再来看一个骨牌问题
骨牌问题
骨牌问题

有2*n个方格,现有大小为2*1的骨牌,用骨牌填满方格,如将2*3的方格填满,有多少种填法 可行的方法和不可行的有
方法
方法

可得1,2,3,5…

机器人走方格问题

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

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。

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

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.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成递归往往是好的。