方法递归调用

介绍

递归就是方法自己调用自己,每次调用时传入不同的变量递归有助于编程者解决 复杂问题,同时可以让代码变得简洁

递归能解决什么问题？

1. 各种数学问题如: 8皇后问题，汉诺塔, 阶乘问题,迷宫问题,球和篮子的问题(google编程大赛)
2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等
3. 将用栈解决的问题-->递归代码比较简洁

递归的重要规则

• 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
• 方法的局部变量是独立的，不会相互影响，
• 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
• 递归必须向退出递归的条件逼近，否则就是无限递归,出现 StackOverflowError，死龟了
• 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

演示

演示一：求斐波那契数

请使用递归的方式求出斐波那契数1,1,2,3,5,8,13...给你一个整数n，求出它的值是多少

• 提示： 斐波那契数就是后面的一个数就是前面两个数的和，例如：

  • 1 + 1 = 2；
  • 1 + 2 = 3；
  • 2 + 3 = 5；
  • 3 + 5 = 8；
  • 5 + 8 = 13；

public class Hello {
    public static void main(String[] args){
        T t1 = new T();
        int n = 0;
        int res = t1.fibonacci(n);
        if(res != -1){
            Sytem.out.println("当 n=" + n + " 对饮的斐波那契数为" + res);
        }
    }
}

class T {
    public fibonacci(int n){
        if(n >= 1){
            if(n == 1 || n == 2){
                return 1;
            } else {
                return fibonacci(n - 1) + fibonacci(n - 2);
            } else {
                System.out.println("要求输入的 n >= 1 的正整数");
                return -1;
            }
        }
    }
}

演示二：猴子吃桃

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个! 以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时 (即还没吃)发现只有1个桃子了。问题: 最初共多少个桃子?

演示三：老鼠出迷宫

演示四：汉诺塔

演示五：八皇后