方法的递归调用

什么是递归

递归的定义

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

例题：求n的阶乘

n的阶乘有两种定义方法：

n!=1×2×3×...×(n-1)×n。
阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n

非递归解法：

 
       public static int factorial(int n) {
		int s=1;
		for(int i=1;i<n;i++) {
			s *=i;
		}
		return s;
	}

递归解法：注意到 5! = 5* 4! 4!=4*3! 3!=3*2! 2!=2*1! 1!=1

 
   
        public static int factorial(int n) {
               if (n ==1||n==0){//终止条件
                    return 1;
               }else {
                    int sum;
                    sum = n*factorial(n-1);//相同重复逻辑
                    return sum;
               }
       }

递归的注意事项

在写递归函数时需要注意三个事项：

1、明确递归终止条件；

2、给出递归终止时的处理办法；

3、提取重复的逻辑，缩小问题规模。

生活中的例子：

市政府 -> 房管局 -> 维修处 -> 维修科 ->小王上门去修理

终止条件：维修科小王

终止时处理办法：上门去修理

提供重复的逻辑：缩小问题规模：

call 市政府 -> call 房管局 -> call 维修处 -> call 维修科 ->call 小王 上门去修理

练一练：斐波那契数列

什么是斐波那契数列，1,1,2,3,5,8,13...所有的数列的值都是前一项和前一项的前一项的加和，也就是f(n) = f(n-1) + f(n-2)这样一个数列就是斐波那契数

实践：斐波那契数列非递归解法

		int a=1,b=1;

		while(a<1000 && b<1000) {

			System.out.print(a+" "+b+" ");

			a=a+b;//新的a 等于旧a + 旧b

			b=a+b;//新的b 等于旧a + 旧b

		}

实践：斐波那契数列递归解法

import java.util.Scanner;

public class demo {
	public static void main(String[] args) {
		System.out.println("请输入月数：");
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = run(n-1) + run(n-2);	//递推公式
		System.out.println("第"+ n + "个月有" + m + "对兔子");
		scanner.close();
	}
	
	public static int run(int n) {		//递归方法
		if(n==1||n==2)
			return 1;
		else
			return run(n-1)+run(n-2);	//递归调用
	}
}

递归的优缺点

递归的优点：

1. 代码简洁；

2. 在树的前序，中序，后序的遍历算法中，递归的实现比循环简单很多。

递归的缺点：

1. 时间和空间的消耗比较大。

   每一个线程都会有一个私有的栈mixed stack，存储java方法的桢栈和native方法的桢栈。每一次方法的调用都涉及到一个桢栈的入栈到出栈。同时，会涉及到分配内存空间，保存参数，返回地址和临时变量，而且往栈里压入数据和弹出都需要时间。

2. 递归会出现重复计算。

   递归的本质是把一个问题分解为多个问题，如果多个问题存在重复计算，有时候这个情况会随着n成指数增长。比如斐波那契的递归就是一个例子。

3. 递归还有栈溢出的问题，每个线程的栈容量多少有限的。

参考文档：https://blog.csdn.net/YY_worhol/java/article/details/83617109