递归

作者: Conn606 | 来源:发表于2020-10-09 19:58 被阅读0次

什么是递归

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

举个栗子(求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


相关文章

  • 二叉树遍历

    先序遍历——[递归、非递归] 中序遍历——[递归、非递归] 后序遍历——[递归、非递归] 层次遍历——[递归、非递归]

  • 二叉树的遍历

    先序递归: 非递归: 中序递归: 非递归: 后序递归: 非递归 层次遍历

  • 二叉树的前序、中序、后序遍历(递归、非递归)

    二叉树 前序 递归: 非递归: 中序 递归: 非递归: 层序 递归: 非递归:

  • 树的遍历,golang实现

    先序,递归 中序,递归 后序,递归 先序,非递归 中序,非递归 后序,非递归 层序遍历

  • 3 递归(19)(方法层面的高级循环)

    递归 树的递归 其它递归

  • 递归,递归,递归

    在我告诉你什么是递归之前,你应该读一下这篇文章:递归,递归,递归。 如果你没有这么做,那么表扬一下自己。如果你那么...

  • 数据结构-树的遍历

    1. 先序遍历 递归实现 非递归实现 2. 中序遍历 递归实现 非递归实现 3. 后序遍历 递归实现 非递归实现 ...

  • 树的遍历

    节点结构: 先序遍历 递归 非递归 后序遍历 递归 非递归 中序遍历 递归 非递归 层序遍历 类库 有了上述遍历算...

  • 算法图解系列之递归[03]

    3 递归 3.1 递归<函数> 3.2 基线条件和递归条件 3.3 递归调用栈

  • 三十八、递归

    一、递归的概述 递归,指在当前方法内调用自己的这种现象。 递归分为两种,直接递归和间接递归。 直接递归称为方法自身...

网友评论

      本文标题:递归

      本文链接:https://www.haomeiwen.com/subject/xaeouktx.html