4.2.2递归调用

递归是程序语言中的一个很基础的应用,学习递归对理清程序编码的思路

非常有帮助
所以在本章中把递归也作为学习的一部分内容。希望读者了解并掌握它的相关用法
我们在中学时期都学过数学归纳法,例如求n的阶乘
比如要求5!,必须先求出4!,而要求4!,必须先求3!,要求3!,

就必须先求2!,要求2！，必须求1！，要求1！，必须求0！ 而0！=1，所以1！=0！*1=1，再进而求2！，3！分别表示

image.png

读者可以从上面观察到，除计算1！子程序外，其他的子程序基本相似，可以设计这个子程序

 int factorial(int i){
     
     int res=0;
             res=factorial(i-1)*i;
             return  res;
 }

读者是否已明白?如果一个方法调用了其本身，那么这个方法就是递归，在这行
程序语句res= factorial5时,就会执行 factorial(5),但执行 factorial5时,又会调用factorial(4)这时要注意,factorial(5)和factorial(4)虽然是同一个代码段，但在内存中，它的数据区是两份，而执行factorial(4)时又会调用factorial(3)，执行factorial(3)又会调用factorial(2)，每调用一次 factorial函数,就会在内存中新增一个数据区,那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解
但上面这个函数有点问题 在执行factorial(0)，它又会调用 factorial(-1)……,造成死循环，也就是说，在factorial函数中，需要在适当的时候保证不再调用该函数，也就是不执行 res=factorial(i-1)*i这条调用语句

把上例补充完整 结果如下所示

public class fgfgfdgdg{
    public static void main(String[] args) {
       int i=5;
       int b=shule(i);
        System.out.println(b);
    public  static  int shule(int n){
        if (n<=0)
        {
         return new IllegalArgumentException();

        }
        if (n<=1){

            return 1;

        }
        return shule(n-1)*n;


    }

裴波纳契数列一个比较定点的数学推理题，这个数列的第一位和第二位均为1，其他位数的值均为前面两位的和,如图4.14所示

image.png

图4.14装波纳契数列分析
我们试用递归算法求出第20位上的数值
递归调用在明白原理的情况下,操作起来比较容易。用递归来解决装波纳契数列问题的代码如下所示

public class fgfgfdgdg{
    public static void main(String[] args) {
        int  i =20;
        System.out.println(shule(i));

  public  static  int shule(int n){

        if(n==1||n==2){
            return 1;

        }else {
            return shule(n-2)+shule(n-1);
        }

    }

输出结果

image.png

对于把十进制数转换成二进制数的过程,读者可以试着用递归的方式来实现,这将有助于理解递归的用法