数据结构笔记总结(4.2)递归基础与递归的宏观语意

递归基础

  • 本质上,就是将原来的问题,转化为更小的同一问题
  • 举例:数组求和

数据结构笔记总结(4.2)递归基础与递归的宏观语意

虽然对数组求和这个问题其实没必要使用递归,但是透彻的理解怎么使用递归的思路来解决数组求和问题是一个非常好的理解递归程序的开始。

并且本身这个任务目标结构清晰,逻辑简单,将其改写为递归算法可以更好的帮助我们理解递归程序。下面就来简单实现一下数组求和的递归算法。

代码演示

public class Sum {

    public static int sum(int[] arr){
        return sum(arr, 0);
    }

    // 计算arr[l...n)这个区间内所有数字的和
    private static int sum(int[] arr, int l){
        if(l == arr.length)
            return 0;
        return arr[l] + sum(arr, l + 1);
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(sum(nums));
    }
}

运行该程序,得出结果

数据结构笔记总结(4.2)递归基础与递归的宏观语意

分析递归函数

下面我们来分析一下这个递归函数,写递归算法有一个基本原则,就是所有的递归算法都是可以分成这样两部分的:

第一部分就是“求解最基本的问题”,递归算法就是把原问题变成更小的问题,更小的问题可以变成更小的问题,依次类推……知道最终原问题变成一个最基本的问题,但是这个最基本的问题是不能自动求解的,需要我们去编写逻辑来求解;

另外一部分其实才是递归算法最核心的一部分,就是“把原问题转化成更小的问题”。

这是因为通常对于我们递归算法来说,最基本的问题都是极其简单的,因为最基本的问题一眼就看出答案了,其实难的是把原问题转化成更小的问题,所谓“转化为更小的问题”不是求一个更小的答案就好了,我们要根据这个更小问题的答案构建原问题的答案。

数据结构笔记总结(4.2)递归基础与递归的宏观语意

  • 注意递归函数的“宏观”语意
  • 递归函数就是一个函数,完成一个功能

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(4.2)递归基础与递归的宏观语意
分享到:
赞(0)

评论抢沙发

评论前必须登录!