写点什么

递归算法的三个定律是什么?

作者:InfoQ IT百科
  • 2022 年 4 月 24 日
  • 本文字数:533 字

    阅读完需:约 2 分钟

  1. 递归算法必须具有基本情况。

  2. 递归算法必须改变其状态并向基本情况靠近。

  3. 递归算法必须以递归方式调用自身。


递归算法必须服从三个重要的定律:


1.递归算法必须具有基本情况。

2.递归算法必须改变其状态并向基本情况靠近。

3.递归算法必须以递归方式调用自身。让我们更详细地看看每一个定律,看看它如何在 listsum 算法中使用。首先,基本情况是算法停止递归的条件。基本情况通常是足够小以直接求解的问题。在 listsum 算法中,基本情况是长度为 1 的列表。


为了遵守第二定律,我们必须将算法向基本情况的状态改变。状态的改变意味着该算法正在使用的一些数据被修改。通常,表示问题的数据在某种程度上变小。在 listsum 算法中,我们的主要数据结构是一个列表,因此我们必须将我们的状态转换工作集中在列表上。因为基本情况是长度 1 的列表,所以朝向基本情况的自然进展是缩短列表。 


最后的法则是算法必须调用自身。这是递归的定义。递归对于许多新手程序员来说是一个混乱的概念。作为一个新手程序员,你已经知道函数是有益的,因为你可以将一个大问题分解成较小的问题。较小的问题可以通过编写一个函数来解决。我们用一个函数解决问题,但该函数通过调用自己解决问题!该逻辑不是循环;递归的逻辑是通过将问题分解成更小和更容易的问题来解决的优雅表达。

用户头像

还未添加个人签名 2021.04.12 加入

还未添加个人简介

评论

发布
暂无评论
递归算法的三个定律是什么?_InfoQ IT百科_InfoQ写作社区