方法递归调用

SOBER大约 2 分钟

方法递归调用

介绍

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

递归能解决什么问题?

  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个桃子了。问题: 最初共多少个桃子?

演示三:老鼠出迷宫

演示四:汉诺塔

演示五:八皇后