递归----基础训练

递归的一些基础使用我都写在代码注释了,直接上代码吧。。。

public class Test {

    public static void main(String[] args) {

    }

    /**
     * 递归写法
     * @param i
     */
    static void f(int i){
        f(i-1);
    }

    /**
     * 递归两种解法:1、找到一种划分方法  2、递推公式 等价转换
     * f(n)求n的阶乘  ---> f(n-1) 求n-1的阶乘
     * 找重复  n*(n-1)的阶乘  求n-1的阶乘是原问题的重复(规模重复) ---子问题
     * 找变化:变化的量应该作为参数
     * 找边界:出口
     * @param i
     */
    static int f1(int n){
        if (n==1) {
            return 1;
        }
        return n*f1(n-1);
    }

    /**
     * 打印i到j
     */
    static void f2(int i,int j){
        if (i>j) {
            return ;
        }
        System.out.println(i);
        f2(i+1, j);
    }

    /**
     * 数组求和
     * 难点就是加参数
     * @param arr
     * @param begin
     * @return
     */
    static int f3(int []arr,int begin){
        if (begin==arr.length-1) {
            return arr[begin];
        }
        return arr[begin]+f3(arr, begin+1);
    }

    /**
     * 难点就是加参数
     * 翻转字符串
     */
    static String reverse(String src,int end){
        if (end == 0) {
            return ""+src.charAt(0);
        }
        return src.charAt(end)+reverse(src,end-1);
    }

    /**
     * 多分支递归  斐波那契数列
     * 递归分解为:直接量+小规模子问题  或者 多个小规模子问题
     *  递归基本都可以写出递推公式
     *  递归本质:递推公式
     */
    static int fib(int n){
        if (n==1 || n==2) {
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }

    /**
     * 巧用递推公式解最大公约数
     * 递推公式 等价转换
     */
    static int gcd(int m,int n){
        if (n==0) {
            return m;
        }
        return gcd(n, m%n);
    }

    /**
     * 别有洞天:递归形式进行插入排序
     */
    static void insertSort(int []arr,int k){

        if (k==0) {
            return ;
        }

        // 划分两个部分  第一个部分 对前k-1个元素排序
        insertSort(arr, k-1);

        // 第二个部分  把位置k的元素插入到前面的部分
        int x = arr[k];
        int index = k - 1;
        while(index>-1&&x<arr[index]){
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = x;
    }    

}

原文地址:https://www.cnblogs.com/xiaoyh/p/10257656.html

时间: 01-11

递归----基础训练的相关文章

PHP_递归实现无限级分类

<?php /** * 递归方法实现无限级别分类 * @param array $list 要生成树形列表的数组[该数组中必须要有主键id 和 父级pid] * @param int $pid=0 父级id * @param int $level=0 缩进次数[用于指定分类名称要缩进的数量] */ function getTree($list,$pid=0,$level=0 ) { // static 表示声明一个静态变量, 静态变量在函数中会一直保存它的值 static $tree = arr

3.sql中的向上递归和向下递归

1.向下递归 select * from table_name where 条件 connect by prior bmbm(本级关联条件)=sjbmbm(上级关联条件) start with bmbm(本级关联条件)='610000000000'(本级编码)--包含本级 select * from table_name where 条件 connect by prior bmbm(本级关联条件)=sjbmbm(上级关联条件) start with sjbmbm(本级关联条件)='6100000

斐波那契数列的递归和非递归解法

//递归解法 function fib(n){ if(n < 1){ throw new Error('invalid arguments'); } if(n == 1 || n == 2){ return 1; } return fib(n - 1) + fib(n - 2); } //非递归解法 function fib(n){ if(n < 1){ throw new Error('invalid arguments'); } if(n == 1 || n == 2){ return 1

python3 递归

递归调用: 在调用一个函数的过程中,直接或者简介调用了该函数本身 必须有一个明确的结束条件 l = [1,[2,3,[4,5,[6,7,[8,9,[10,11,[12,13]]]]]]] def func(l): for i in l: if isinstance(i,list): func(i) else: print(i) func(l) 应用场景:不知道应该循环多少次,只知道什么时候应该结束

day05匿名函数,内置函数,二分法,递归,模块

yield作为表达式来使用的方式 #grep -rl 'python /root """ 查找root下文件中含有python的文件 """ import os def init(func): def wrapper(*args,**kwargs): g=func(*args,**kwargs) next(g) return g return wrapper @init def search(target): while True: search

浅谈递归调用的个人领悟

从大一开始学c,就不是挺理解递归的,最近突然有所体会: 递归调用中递归调用的函数可以把它想象成为一个树的结点,在函数中调用自身就是一个分支,直到出口条件时就是这棵树的叶子结点.叶子的值便是出口返回的值.最后从叶子结点按照你所调用的方法向上返回值,最终结束递归调用.

用递归和非递归的方法输出斐波那契数列的第n个元素(C语言实现)

费波那契数列(意大利语:Successione di Fibonacci),又译为费波拿契数.斐波那契数列.费氏数列.黄金分割数列. 在数学上,费波那契数列是以递归的方法来定义: {\displaystyle F_{0}=0} {\displaystyle F_{1}=1} {\displaystyle F_{n}=F_{n-1}+F_{n-2}}(n≧2) 用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出.首几个费波那契系数是: 0, 1, 1, 2, 3

Java递归流程

递归二字顾名思义就是:递过去,归回来.所以我索性叫它做有借有还吧. 下面的例子由c而来: public class Main {                                public static void main(String[] args) {                                      fun(1);                                }                                publ

从汉诺塔问题来看“递归”本质

汉诺塔问题 大二上数据结构课,老师在讲解"栈与递归的实现"时,引入了汉诺塔的问题,使用递归来解决n个盘在(x,y,z)轴上移动. 例如下面的动图(图片出自于汉诺塔算法详解之C++): 三个盘的情况: 四个盘的情况: 如果是5个.6个.7个....,该如何移动呢? 于是,老师给了一段经典的递归代码: void hanoi(int n,char x,char y,char z){ if(n == 1) move(x,1,z); else{ hanoi(n-1,x,z,y); move(x,

Atitit 表达式原理 语法分析&#160;原理与实践 解析java的dsl &#160;递归下降是现阶段主流的语法分析方法

Atitit 表达式原理 语法分析 原理与实践 解析java的dsl  递归下降是现阶段主流的语法分析方法 于是我们可以把上面的语法改写成如下形式:1 合并前缀1 语法分析有自上而下和自下而上两种分析方法2 递归下降是现阶段主流的语法分析方法,2 于是我们可以把上面的语法改写成如下形式: 1)       Operator="+" | "-" | "*" | "/" 2)       Expression=<数字>