什么是递归？
程序 调用自身 的编程技巧成为 递归（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
F_0=0 ,F_1=1
F0=0,F1=1
F
n
=
F
(
n
−
1
)
+
F
(
n
−
2
)
(
n
>
=
2
,
n
∈
N
∗
)
Fn=F(n-1)+F(n-2) \qquad(n>=2,n\in N* )
Fn=F(n−1)+F(n−2)(n>=2,n∈N∗)
F
n
=
{
0
n
=
0
1
n
=
1
F
n
−
1
+
F
n
−
2
n
=
2
,
3
,
4
,
5...
(
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}
Fn=⎩
⎨
⎧01Fn−1+Fn−2n=0n=1n=2,3,4,5...(n为正整数)
- 终止条件（递归出口）为 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);
}
猴子吃桃问题
文章来源：https://www.toymoban.com/news/detail-544385.html
文章来源地址https://www.toymoban.com/news/detail-544385.html
/* 猴子吃桃问题：小猴子摘了一堆桃子。第一天吃掉一半又多吃了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);
}
}
到了这里，关于【Java】递归算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
