真正的数据结构和算法【6】

递归介绍及递归的特征

实例:Java代码使用递归计算三角数字

递归:自己调用自己(函数/方法)的编程技术是程序设计中的数学归纳法。

特征:

  1. 调用自身
  2. 当调用自身的时候,这样做是为了解决更小的问题。
  3. 存在某个足够简单的问题的层次在这层算法中不需要调用自己就可以直接解答,且返回一个结果。

1 3 6 10 15 21
2 3 4 5 6

比较像数列的思路

6+5+4+3+2+1

(n^2+n)/2

三角数字计算
基值情况(终止递归条件)

递归的效率高不高
入栈
循环的效率比递归的效率更高。

递归在概念上简化了设计。

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package recursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author Zen
 * @version 1.0: Triangle.java, v 0.1 2019/05/19 10:22 Zen Exp $
 */
public class Triangle {
    public static void main(String[] args) throws IOException {
        int num = getInt();
        System.out.println("您输出的数字为:"+ num);
        int result = triangleCaculate(num);
        System.out.println("返回结果为:"+result);
    }
    public static int triangleCaculate(int num){
        if(num == 1){
            return 1;
        }else{
            return num+triangleCaculate(num -1);
        }
    }

    public static String getString() throws IOException {
        InputStreamReader isr =new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }

    public static int getInt() throws IOException{
        String s = getString();
        int theNum = Integer.parseInt(s);
        return theNum;
    }
}

递归_阶乘和变位字

65432*1

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package recursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author Zen
 * @version 1.0: Factorial.java, v 0.1 2019/05/19 10:37 Zen Exp $
 */
public class Factorial {
    public static void main(String[] args) throws IOException{
        int num = getInt();
        System.out.println("您输入的数字为:"+num);
        int result = factorialCaculate(num);
        System.out.println("返回结果为:"+result);
    }
    public static int factorialCaculate(int num){
        if(num == 1){
            return 1;
        }else{
            return num * factorialCaculate(num -1);
        }
    }
    public static String getString() throws IOException {
        InputStreamReader isr =new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }

    public static int getInt() throws IOException{
        String s = getString();
        int theNum = Integer.parseInt(s);
        return theNum;
    }
}

变位字

cat:按顺序重新排序后会产生6种变位字

变位字这个好像有点难度

递归_二分查找

前提:有序数组

此问题已经解决

递归_汉诺塔问题

本文链接:

https://heyzen.club/index.php/Coder/308.html
1 + 5 =
快来做第一个评论的人吧~