【数据结构与算法之递归算法】递归算法的基本思想

忘是亡心i 2024-03-25 19:16 219阅读 0赞

#### 【数据结构与算法之递归算法】递归算法的基本思想 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之递归算法】递归算法的基本思想

递归算法是一种直接或间接调用原算法的算法，一个使用函数自身给出定义的函数被称为递归函数。

无论递归算法还是递归函数，总之就是 “自己调用自己”。

递归算法可以将一个规模较大的问题划分为若干规模较小的同类问题，如果一个问题规模庞大，且具有明显的递归特性，则可以考虑使用递归。

【举个栗子】斐波那契数列。

著名的斐波那契数列的规律是：

1,1,2,3,5,8,13,21,24,55…

用递归函数表达式就是：

*  当n = 1时，F(n) = 1
 *  当n = 2时，F(n) = 1
 *  当n ≥ 3时，F(n) = F(n - 1) + F(n - 2)

Java 描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: FibonacciSeries
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 16:06
     */
    
    public class FibonacciSeries {
        
    
        public static int fibonacci(int n) {
        
    
            if (n == 1 || n == 2) {
        
                return 1;
            } else {
        
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        }
    
        public static void main(String[] args) {
        
    
            System.out.println("斐波那契数列的第5项是: " + fibonacci(5));
    
        }
    
    }

运行结果

![在这里插入图片描述][8024f18be521467cbbc2ad9138e492da.png_pic_center]

【注意事项】

设计递归算法时应该注意的点：

1.  每个递归函数都必须有一个非递归定义的初始值作为递归的结束标志。
2.  递归算法解决的问题要具有递归特性
3.  虽然递归算法结构简单，易于理解和实现，但是由于其需要反复调用自身，所以运行效率较低，时间复杂度和空间复杂度较高。

[8024f18be521467cbbc2ad9138e492da.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8b65a704a56b43af89c2cfcc89a2a70a.png