递归

什么是递归

程序调用自身的编程技巧称为递归 ,说白了，递归和普通的函数调用一样

举个栗子(求n的阶乘)：

public class factorial {

    public static void main(String[] args) {
        int t;
        int result;
        Scanner s = new Scanner(System.in);
        t = s.nextInt();
        result =  fact(n);  //这里我们调用fac方法
        System.out.println(t);
    }
    public static int fact(int n) {
        if(n==1)
            return 1;
        return n*fact(n-1); //因为 n != 1 ,所以这里有调用了fac方法
    }

}

通过这个简单的例子我们知道，递归其实就是方法的调用，不用想太复杂

这个例子加入我们输入数字4，那这个程序的执行过程如下

用递归完成递推

• 把关注点放在要求解的目标上
• 找到第n次与第n-1次执行之间的关系
• 确定第1次的返回结果

例子1：切饼问题

一块月饼，切上1刀，可分成2块，切上2刀，可分成4块，切上3刀，可分成7块……，那么切n刀，最多可分成多少块？分析可知，切第n刀可分成n-1刀的块数加n，n=0时是1块，所以可写成递归如下

public class Cut {
    public static void main(String[] args) {
        
        Scanner s = new Scanner(System.in);
        System.out.println("times:");
        int number = s.nextInt();
        int result = Cut.c(number);
        System.out.printf("pieces of cookie:%d",result);
    }
    public static int c(int n){
        
            if(n==0) {
                return 1;
            }
                
            else
                return (n+c(n-1));
    }
}   

例子2：斐波那契数列

斐波那契数列指的是这样一个数列：

[图片上传失败...(image-e100c8-1602244676138)]

这个数列从第3项开始，每一项都等于前两项之和。即：F(0)=0，F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

public class Fibonacci {

    public static void main(String[] args) {
        Scanner s;
        s = new Scanner(System.in);
        int i = s.nextInt();
        int result = fibonacci(i);
        System.out.println(result);
    }
    public static int fibonacci(int n){
        if(n==1)
            return 0;
        if(n==2)
            return 1;
        return (fibonacci(n-1)+fibonacci(n-2));
    }
}

模拟连续发生的动作

• 搞清楚 连续发生的动作是什么
• 搞清楚 不同次动作之间的关系
• 搞清楚 边界条件是什么

例子1：十进制整数转换二进制

十进制整数转换为二进制整数采用"除2取余，逆序排列"法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

public class convert {
    public static void main(String[] args) {
        int i;
        Scanner s = new Scanner(System.in);
        i = s.nextInt();
        con(i);

    }
    public static void con(int i) {
        if(i/2 != 0) {
            con(i/2);
            System.out.print(i%2);
        }
        else
            System.out.print(i);
    }
}

例子2：汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

汉诺塔问题图示 汉诺塔问题图示

import java.util.*;
public class hanoi {
    static int i=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        move(n,'A','B','C');
    }
    public static void move(int n,char a,char b,char c) {
        //用a,b,c三个变量表示三个柱子
        if(n==1) {
            //如果只有1个盘子，那就把盘子从a柱子移动到c柱子
            i++;
            System.out.printf("第%d步：",i);
            System.out.println("把一个盘子从: " +a+" 移到: "+c);
        }
        else {
            //把n-1个盘子从a柱子经过c柱子移动到b柱子
            move(n-1,a,c,b);
            i++;
            System.out.printf("第%d步：",i);
            System.out.println("把一个盘子从: "+a+" 移到: "+c);
            //再把n-1个盘子从b柱子经过a柱子移动到c柱子
            move(n-1,b,a,c);
        }
    }
}

进行“自动的分析”

• 先假设有一个函数能给出答案

• 在利用这个函数的前提下，分析如何解决问题

• 搞清楚最简单的情况下答案是什么

例子1：逆波兰表达式

逆波兰表达式是一种把运算符前置的算术表达式。

如2 + 3的逆波兰表达式为+ 2 3

如（2 +3）*4 的逆波兰表达式为 x + 2 3 4

编写程序求解任一包含+ - * /四个运算符的逆波兰表达式的值

• 输入：x + 11.0 12.0 + 24.0 35.0

• 输出：1357.0