递归---算法

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++;
        }
    }
}