什么是递归？

程序 调用自身 的编程技巧成为 递归（recursion）。

递归算法是一种直接或间接调用、定义自身的函数或方法的算法，也就是调用自身。

递归的实质：将原问题不断分解为规模缩小的子问题，然后用递归调用的方法来表示问题的解；

递归，顾名思义就是 递和归的过程：

递：将原问题分解为若干个子问题，这些子问题的解决思路相同；
归：当问题不断递进，需要一个明确结束的递归出口（临界点）；

在这里插入图片描述
递归算法是一种自下而上的思维，难点在于逻辑性；

需要明确以下几点：

明确递归的终止条件（递归出口）；
明确反复执行的递归过程，如何把若干的子问题联系在一起；
给出递归终止时的处理办法；

下面用几个例子来说明：

递归求阶乘

在这里插入图片描述

这里的递归出口为 0！=1 即 n=0 时 ==1；
递归式子为 n ! = n * ( n - 1 )

用Java写一个递归函数：

 public static int recursion(int n){if(n==0){  //递归终止的条件return 1;}return n*recursion(n-1); //递归过程
}

public class Demo01 {public static void main(String[] args) {int rec;//递归int num;//普通rec=recursion(5);num=fun(5);System.out.println("用递归算法得到："+rec);System.out.println("常规循环得到"+num);}//递归实现static int recursion(int n){if(n==0){  //递归终止的条件return 1;}return n*recursion(n-1); //递归过程}//非递归实现static int fun(int n){int result=1;while(n>1){result *= n;n--;}return result;}
}

在这里插入图片描述

递归求解斐波那契数列

斐波那契数列：又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13…
在数学上，斐波那契数列有如下以递归形式定义：
$F_0=0 ,F_1=1$
$\qquad(n>=2,n\in N* )$
$F_n=\begin{cases} 0 & n=0 \\ 1 & n=1 \\ F_{n-1}+F_{n-2} & n=2,3,4,5...(n为正整数) \end{cases}$

终止条件（递归出口）为 n-1=1 n-2=0 即 n=1或n=2
递归体即 Fn=F(n-1)+F(n-2)

public static int fibonacci(int n){if(n==1 || n==2){return 1;}return fibonacci(n-1)+fibonacci(n-2);
}

或：

终止条件为 n=0 或 n=1 （因为给出了F0和F1的值）;
递归体仍为 Fn=F(n-1)+F(n-2)

public static int fibonacci(int n){if(n==0){return 0;}else if(n==1){return 1;}return fibonacci(n-1)+fibonacci(n-2);
}

猴子吃桃问题

在这里插入图片描述

/*  猴子吃桃问题：小猴子摘了一堆桃子。第一天吃掉一半又多吃了1个，第二天吃了剩下的一半又多吃1个，以后每天都吃掉剩下的一半多一个。第10天发现只剩一个桃子了。问第一天摘了多少桃子？第二天还有多少桃子？第三天……
编写方法peach(int day)，计算第day天的桃子数。
在main()方法中输入day（1~10），即你想知道第day天小猴子有多少桃子，调用peach()方法求该天的桃子数。
*/
import java.util.Scanner;
public class Peach {public static void main(String[] args) {System.out.println("你想知道小猴子第几天的桃子数？请输入（1~10）");Scanner sc = new Scanner(System.in);int day;day = sc.nextInt();System.out.printf("第%d天的桃子数是%d\n",day,peach(day));sc.close();}//计算第day天的桃子数static int peach(int day) {int n;   //n表示第day天的桃子数if(day==10){return 1;}return 2*(peach(day+1)+1); }
}