Finite and Infinite Recursion with Examples in Java

递归是函数直接或间接调用自身的过程，与之关联的函数称为递归函数。递归使解决某些难题变得容易。汉诺塔（TOH）、中序/前序/后序遍历、DFS 等问题都可以使用递归来解决。

递归的类型

根据终止时间的不同，可以区分两种不同的递归。

1. 有限递归
2. 无限递归

有限递归

递归需要有限次数的递归调用才能结束，这就是有限递归。当满足基本条件时，递归就会结束。它确保函数在完成任务后终止。

实施

文件名: FiniteRecursionExample.java

输出

 
5 
4 
3 
2 
1  

复杂度分析

时间复杂度为 O(N)，上述代码的空间复杂度为 O(N)

无限递归

当递归在有限次数的递归调用后继续进行时，称为无限递归。由于基本条件永远不会得到满足，递归将无限期地继续下去。然后程序将一直进行递归调用，直到出现 StackOverflowError 错误为止。

实施

文件名: InFiniteRecursionExample.java

输出

 
5 
5 
5 
5 
5 
5 
5 
5 
5 
5 
5 
5 
5 
5 
5   

复杂度分析

由于递归将永远不会结束，因此时间复杂度是非有限的，并且上述代码的空间复杂度是非有限的。