递归---算法

1、概念

        在数学与计算机科学中,是指在方法的定义中使用方法自身。递归算法是一种直接或者间接调用自身方法的算法,即在定义自身的同时又出现自身的直接或间接调用。

特点:

  1. 递归就是方法里调用自身。
  2. 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
  3. 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
  4. 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

注意:递归必须要有一个退出条件

//n的阶乘    
    public void digui(int n){
        if(n == 1){
            return 1;
        }
        return n*digui(n-1);
    }




递归方法名(参数){
    if(判断是否到达出口){
        return;//结束递归
    }
    调用自身(参数);//递归逻辑
    return;
}

总结:

  1. 找到一种划分的方法
  2. 找到递推公式或者等价转换,这些都是父问题转化为求解子问题
  3. 找变化的量:变化的通常要作为参数找出口

例题---斐波那契数列

        斐波那契数列的定义为F(n)=F(n-1)+F(n-2),同时F1=1,F2=1。请你输出数列的第n个数的对1e9+7取模的值。

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(f(n));
    }
    public static long f(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        long res = f(n-1) + f(n-2);
        res %= (long)1e9+7;
        return res;
    }

例题---数的计算

        输入一个自然数n(n<=1000),我们对此自然数按照如下方法进行处理:

  1. 不做任何处理;
  2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
  3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止。

输入描述:输入一个正整数n

输出描述:输出一个整数,表示答案。

示例:6

           6

import java.util.Scanner;


public class Main {
   static int ans = 1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        f(n);
        System.out.println(ans);
    }
    public static void f(int n){
        if(n == 1){
            return;
        }
        for (int i = 1; i <= n/2; i++) {
            f(i);
            ans++;
        }
    }
}

相关推荐

  1. ---算法

    2024-04-02 14:14:05       51 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-02 14:14:05       171 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-02 14:14:05       189 阅读
  3. 在Django里面运行非项目文件

    2024-04-02 14:14:05       157 阅读
  4. Python语言-面向对象

    2024-04-02 14:14:05       170 阅读

热门阅读

  1. 2024最新华为OD机试试题库全 -【符号运算】- C卷

    2024-04-02 14:14:05       41 阅读
  2. ES6中的Map与Set

    2024-04-02 14:14:05       49 阅读
  3. C语言中向函数中传递函数指针的方法

    2024-04-02 14:14:05       48 阅读
  4. 简单设计模式讲解

    2024-04-02 14:14:05       51 阅读
  5. C++命名空间详解

    2024-04-02 14:14:05       54 阅读
  6. 【Ubuntu】可配置环境变量位置

    2024-04-02 14:14:05       48 阅读