递归算法

什么是递归算法

在过程或者函数里调用自身的算法；

递归算法（recursion algorithm），通过重复将问题分解为同类的子问题而解决问题的方法，

Java中函数可以通过调用自身来进行递归，大多数编程语句皆是如此；

递归的作用可以完全取代循环。

递归阶乘

package com.sin.demo.recursive;/*** @author sin* @date 2022/11/2* @apiNote*/
public class RecursiveDemo {public static void main(String[] args) {int a = factorialTest(5);System.out.println(a);}/*** 递归阶乘* @param a 阶乘参数* @return*/public static int factorialTest(int a) {if (a == 0)return 1;elsereturn a * factorialTest(a - 1);}}

结果

循环阶乘

public static void main(String[] args) {int a = factorialTest1(5);System.out.println(a);}/*** 循环阶乘* @param a 阶乘数* @return*/public static int factorialTest1(int a){int sum = 1;for (int i = 1 ;i<=a;i++)sum *=i;return sum;}

结果

分析递归

通过栈角度来理解递归方法的调用过程

栈（后进先出）（先进后出）原则

第一步

在 factorialTest（）方法第一次被调用的时候，参数 a 为 5，走else代码块，执行 a * factorialTest(a - 1)，相当于a * factorialTest(3)时栈的状态

第二步

返回值存储器时没有返回值的，在调用factorialTest（4）后，栈的状态

第三步

返回值存储器时没有返回值的，在调用factorialTest（3）后，栈的状态

第四步

返回值存储器时没有返回值的，在调用factorialTest（2）后，栈的状态

第五步

返回值存储器时没有返回值的，在调用factorialTest（1）后，栈的状态

第六步

返回值存储器时没有返回值的，在调用factorialTest（0）后，栈的状态

最后符合符合if条件，有返回值

栈的后进先出原则，进行阶乘

递归代码虽然只用一份，单执行的过程中，每调用一次就会入栈一次，生成不同的参数，局部变量即返回地址；