您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

深入理解递归算法,被误解的递归

时间:2019-09-16 10:37:54  来源:  作者:

递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对它持怀疑态度,但是这不影响递归是算法中最强大的想法。

让我们来看看经典的递归阶乘:

factorial.c

  •  
#include <stdio.h>
int factorial(int n)
{
 int previous = 0xdeadbeef;
 if (n == 0 || n == 1) {
 return 1;
 }
 previous = factorial(n-1);
 return n * previous;
}
int main(int argc)
{
 int answer = factorial(5);
 printf("%dn", answer);
}
 

一个函数调用自身的想法起初非常神秘。为了解释整个过程,下图展示了factorial(5)被调用到n == 1 栈上结构。

 

 

深入理解递归算法,被误解的递归

 

 

每次调用factorial都会生成一个新的栈帧。这些栈帧的创建和销毁使得递归因子比其迭代部分慢。在调用开始和返回之前的这些栈帧累积是可能耗尽栈空间并使程序崩溃。

但是这些担忧通常是理论上的。例如,栈帧 factorial每个占用16个字节(这可以根据栈对齐和其他因素而变化)。如果您在计算机上运行现代x86 linux内核,通常默认有8兆字节的堆栈空间,因此factorial n最多可以处理512,000。这是一个巨大数,需要8,971,833位来表示这个数,所以栈空间是我们问题中最少的:一个微弱的整数 - 甚至是64位 - 在我们用完栈空间之前会溢出数万次

我们稍后会看一下CPU的使用情况,但是现在让我们从位和字节中退一步,看看递归作为一种通用技术。我们的阶乘算法归结为将整数N,N-1,... 1推入堆栈,然后以相反的顺序将它们相乘。我们使用程序的调用堆栈执行此操作的前提是:我们可以在堆上分配堆栈并使用它。虽然调用堆栈确实具有特殊属性,但它只是您可以使用的另一种数据结构。

一旦你看到调用堆栈作为一个数据结构,其他东西就变得豁然开朗了:将本身之前所有这些整数累加起来再乘以自身这显然不是明智的选择。 使用迭代过程计算阶乘更为明智。

有一个传统的面试问题,在迷宫中放一只老鼠,你帮助老鼠找奶酪,假设老鼠可以在迷宫中向左或向右转。你会如何建模并解决这个问题?

像生活中的大多数问题一样,你可以将这种啮齿动物的任务抽象到一个图形,特别是一个二叉树,其中节点代表迷宫中的位置。然后你可以尽可能地让鼠标左转,当它到达死胡同时回溯然后右转。下图就是老鼠路径 :

 

深入理解递归算法,被误解的递归

 

 

每条边(线)都可以左转或右转,老鼠可以选择。如果任一转弯被阻止,则相应的边缘不存在。无论您使用调用堆栈还是其他数据结构,此过程本质上都是递归的。但使用调用栈非常简单

Maze.c

  •  
#include <stdio.h>
#include "maze.h"
int explore(maze_t *node)
{
 int found = 0;
 if (node == NULL) {
 return 0;
 }
 if (node->hasCheese) {
 return 1; // found cheese
 }
 found = explore(node->left) || explore(node->right);
 return found;
}
int main(int argc)
{
 int found = explore(&maze);
}

在maze.c:13中找到奶酪,下图是堆栈。

 

深入理解递归算法,被误解的递归

 

 

 

虽然这里很难摆脱递归,但这并不意味着它必须通过调用栈来完成。例如,你可以使用一个字符串 RRLL来跟踪转弯,并依靠字符串来决定鼠标的下一步行动。或者你可以分配其他变量来记录奶酪寻找的状态。你仍然在实现递归过程,但滚动你自己的数据结构。

这可能会更复杂,因为调用堆栈就像手套一样。每个堆栈帧不仅记录当前节点,还记录该节点中的计算状态(在这种情况下,我们是仅采用左侧还是已经尝试右侧)。然而,我们有时会因为害怕溢出而放弃了美好的东西。在我看来是非常愚蠢的。

正如我们所看到的,栈很大,并且在栈空间之前经常会遇到其他约束。还可以检查问题的大小并确保可以安全地处理。CPU担心主要是由两个广泛的病理学例子灌输:愚蠢的因子和可靠的O(2 n) 递归Fibonacci没有记忆。这些并不表示理智的堆栈递归算法。

现实情况是栈操作很快。数据的偏移是准确的,栈在缓存中,不需要冷启动,并且有专门的指令来完成工作。同时,使用您自己的堆分配数据结构会产生大量开销。会看到其他人编写的东西比调用堆栈递归更复杂,性能更差

现代CPU 非常优秀了,通常不是瓶颈。简单往往和性能等同。



Tags:递归算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准...【详细内容】
2020-06-21  Tags: 递归算法  点击:(117)  评论:(0)  加入收藏
对于很多人来说,都知道递归,也能看的懂递归,但在实际项目过程中,却不知道如何使用递归,这里给递归做个总结。递归的定义在数学与计算机科学中,递归(Recursion)是指在函数的定义中...【详细内容】
2019-10-14  Tags: 递归算法  点击:(139)  评论:(0)  加入收藏
递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对...【详细内容】
2019-09-17  Tags: 递归算法  点击:(188)  评论:(0)  加入收藏
递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对...【详细内容】
2019-09-16  Tags: 递归算法  点击:(148)  评论:(0)  加入收藏
最近在实际工作中遇到一个需求,需要检测一个大文件夹下所有文件的更新状态,这个大文件夹下面包含了很多文件和文件夹,文件夹中又包含了很多文件和文件夹...... 类似下面这张图...【详细内容】
2019-08-16  Tags: 递归算法  点击:(235)  评论:(0)  加入收藏
递归(recursion):程序调用自身的编程技巧。递归满足2个条件:1)有反复执行的过程(调用自身)2)有跳出反复执行过程的条件(递归出口)我这边自己的理解就是反复调用自己本身以前有写过简单...【详细内容】
2019-05-16  Tags: 递归算法  点击:(403)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条