当前位置：首页 > article >正文

java的递归详细讲解

article 2025/8/30 7:44:25

在数据结构算法设计中，或者一个方法的具体实现的时候，有一种方法叫做“递归”，这种方法在思想上并不是特别难，但是实现起来还是有一些需要注意的。虽然对于很多递归算法都可以由相应的循环迭代来代替，但是对于一些比较抽象复杂的算法不用递归很难理解与实现。
递归分为直接递归和间接递归，就简单分享一下两个小的直接递归。

对于递归的概念，其实你可以简单的理解为自己定义自己，记得小时候看过一部电视剧《狼毒花》，里面主角叫做“常发”，但是个文盲，老师问他叫什么，他说“常发”。“哪个常？”“常发的常啊！”“哪个发？”“常发的发啊！”结果第二节课老师就让一群小朋友一起喊“常发的常，常发的发，傻瓜的傻，傻瓜的瓜”。言归正传，显然在多数情况下递归是解释一个想法或者定义的一种合理方法。在思想上递归类似于数学中曾经学过的数学归纳法。

递归的实现：
递归的实现要注意有两点：一个递归的选项和一个非递归的选项，后者成为基础情形（base case）。基础情形是递归的终结情形，没有基础情形或者处理不好都会导致无穷递归，这是我们不想要的结果。递归实现起来最关键的是处理好基础情形。结合具体事例在说一下递归回溯的过程。

其实A方法调用B方法，我们很容易理解!

◆递归就是: A方法调用A方法!就是自己调用自己

◆利用递归可以用简单的程序来解决一些复杂的问题。它通常把一个大型复杂的问题层层转化为-个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

◆递归结构包括两个部分:

    ◆递归头:什么时候不调用自身方法。如果没有头，将陷入死循环。◆递归体:什么时候需要调用自身方法。

Demo:

1、爬楼梯算法：已知一个楼梯有n个台阶，每次可以选择迈上一个或者两个台阶，求走完一共有多少种不同的走法。

package leetcode;public class ClimbStairs {
//	************************************************
//递归public int climbStairs(int n) {int i=1;if(n<=0)return 0;if(n==1){return i;}if(n==2){i++;return i;}elsereturn climbStairs(n-1)+climbStairs(n-2);}
//**********************************************public static void main(String []args){ClimbStairs cs=new ClimbStairs();int a =cs.climbStairs(4);System.out.println(a);}}

递归函数有返回值的比没有返回值的麻烦一点，因为一个函数只有一个返回值，但是递归还要求有基础情形的存在，所以还必须有if判断来终止递归。所以在每一个if或者else后边都有一个return，这样保证函数在任何一种情况下都有且仅有一个返回值。
分析一下这个算法：
A：如果有0个台阶，那么有0种走法，这个不用多说；
B：如果有1个台阶，那么有1种走法；
C：如果有2个台阶，那么有2种走法（一次走1个，走两次；一次走两个）；
以上的B和C就是基础情形。
D：接下来就是递归了，如果台阶数目多于2个，那么首先第一步就有两种选择：第一次走1个，或者第一次走两个。这样除了第一次后边的走法就有了两种情形：climbStairs(n-1)和climbStairs(n-2)。这样一直递归下去，直到出现到了基础情形（即n=1或n=2的情形），递归到这个地方（基础情形），然后开始回溯，这就是所说的和递归密切相关的“回溯”了。回溯，顾名思义就是从结果倒着回去，找到整个过程，进而分析这个路径或者说是实现的过程。

需要注意的是，这个算法实现思路上简单，但是复杂度并没有降低，还牵扯回溯保存堆栈问题(其实递归的设计尽量避免这种嵌套两个的递归方式（climb（n）中包含climb（n-1）和climb（n-2）），这种操作会使得堆栈开辟空间随着n的增大以指数型增长，最终程序很容易崩溃），而且在台阶数目多到一定数量的时候会越界（走法次数会超出int的范围），所以递归程序很大程度上就是思想实现设计上简单理解一些。

public class hello{public static void main(String[] args){int n=5;System.out.println("第"+n+"个月的兔子总数是"+funs(n));}private static int funs(int n){ if(n==1||n==2) 		return 1;else				return funs(n-1)+funs(n-2);								}}


public class hell {public static void main(String[] args){int n=6;System.out.println("第"+n+"个月的兔子总数是"+funs(n,"入口"));}private static int funs(int n,String s){ System.out.println("初始化的n的值="+n);System.out.println("n值来源="+s);if(n==1||n==2) {	return 1;}else {int i=funs(n-1,"第一次计算");int i1=funs(n-2,"第二二二次计算");System.out.println("///*************///");System.out.println("n-1结果="+i);System.out.println("///*************///");System.out.println("n-2结果="+i1);return i+i1;	}}}

初始化的n的值=6
n值来源=入口
初始化的n的值=5
n值来源=第一次计算
初始化的n的值=4
n值来源=第一次计算
初始化的n的值=3
n值来源=第一次计算
初始化的n的值=2
n值来源=第一次计算
初始化的n的值=1
n值来源=第二二二次计算
///*************///
n-1结果=1
///*************///
n-2结果=1
初始化的n的值=2
n值来源=第二二二次计算
///*************///
n-1结果=2
///*************///
n-2结果=1
初始化的n的值=3
n值来源=第二二二次计算
初始化的n的值=2
n值来源=第一次计算
初始化的n的值=1
n值来源=第二二二次计算
///*************///
n-1结果=1
///*************///
n-2结果=1
///*************///
n-1结果=3
///*************///
n-2结果=2
初始化的n的值=4
n值来源=第二二二次计算
初始化的n的值=3
n值来源=第一次计算
初始化的n的值=2
n值来源=第一次计算
初始化的n的值=1
n值来源=第二二二次计算
///*************///
n-1结果=1
///*************///
n-2结果=1
初始化的n的值=2
n值来源=第二二二次计算
///*************///
n-1结果=2
///*************///
n-2结果=1
///*************///
n-1结果=5
///*************///
n-2结果=3
第6个月的兔子总数是8