专栏首页烟草的香味递归函数两种方式的区别

递归函数两种方式的区别

概述

递归函数都不陌生,比如计算n的阶乘:

function f($n){
    if($n <= 1) return 1;
    return $n * f($n-1);
}

当然,有人可能会这么写:

function f($n, $result){
    if($n <= 1) return $result;
    return f($n-1, $n*$result);
}

上面两种方式看着好像没什么区别,但是在cpu眼中,可就不一样了。

分析

函数在调用的时候会开辟一块函数栈,用来保存函数的局部变量、参数、上一个栈的指针、返回值等信息,当函数调用结束后会销毁。递归函数会一直递归下去,上层的函数栈一直不会销毁,知道递归结束,全部退出。

举个栗子,当调用f(3)的时候,对于上面的第一种情况,函数栈大概长这样(仅保留参数和返回值,忽略其他内容):

文字描述就是:

f(1)=1 f(2)=2*f(1)=2*1=2 f(3)=3*f(2)=3*2=6 f(4)=4*f(3)=4*6=24

也就是每一次调用,都会保存本次的变量n以及递归调用的返回值,这就会导致如果递归的太深,就会开辟太多的内存。

如果使用第二种写法,会有什么不同么?

套用刚才的分析,先用文字描述一下:

f(4, 1)=f(3, 4*1)=f(2, 3*4)=f(1, 2*12)=24

有没有发现区别,区别就是,前一种写法要保存一个局部变量n,而后一种写法,都写到下一个方法的参数中了。也就是说,第二种方式,可以直接返回下层方法,不需要退回去了。当然,cpu发现这种情况,会复用函数栈,也就是说,函数栈大概是这么个情况:

看着好像也没啥区别,但是!因为可以直接返回,上图的四个栈使用的都是同一个栈。完美优化。


当递归返回的是递归调用,并且讲调用直接返回,没有参与运算等,就会被这样优化,复用栈。

本文分享自微信公众号 - 烟草的香味(hujing-bc)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何写出让同事好维护的代码?

    写出整洁的代码,是每个程序员的追求。《clean code》指出,要想写出好的代码,首先得知道什么是肮脏代码、什么是整洁代码;然后通过大量的刻意练习,才能真正写...

    Java技术栈
  • 数据结构【第五篇】栈 (stack) 的实现与讲解

    ① 举一个生活中的例子:我在一个储物箱中,堆了一堆衣服,我的一件球衣在最下面,而我要拿这件衣服,就意味着我必须将上面的衣服全部拿出来才可以,但是由于箱子只有一个...

    BWH_Steven
  • 【Python 第75课】可迭代对象和迭代器

    for 循环是我们在 Python 里非常常用的一个语法,但你有没有思考过 for 循环是怎样实现的?

    Crossin先生
  • 一个 Java 对象到底有多大?

    编写Java代码的时候,大多数情况下,我们很少关注一个Java对象究竟有多大(占据多少内存),更多的是关注业务与逻辑。但是殊不知,在我们不经意间,大量的内存被无...

    芋道源码
  • Redis 到底是怎么实现“附近的人”这个功能的呢?

    针对“附近的人”这一位置服务领域的应用场景,常见的可使用PG、MySQL和MongoDB等多种DB的空间索引进行实现。而Redis另辟蹊径,结合其有序队列zse...

    Nealyang
  • 面试再问ThreadLocal,别说你不会

    以前面试的时候问到ThreadLocal总是一脸懵逼,只知道有这个哥们,不了解他是用来做什么的,更不清楚他的原理了。表面上看他是和多线程,线程同步有关的一个工具...

    业余草
  • 如何实现 Go Module 依赖关系的可视化

    最近,我开发了一个非常简单的小工具,总的代码量 200 行不到。今天,简单介绍下它。这是个什么工具呢?它是一个用于可视化展示 Go Module 依赖关系的工具...

    波罗学
  • VBA实用小程序60: 替换图表SERIES公式中的字符串

    大家知道,Excel图表的每个系列使用的数据都是由SERIES公式来确定的。当我们选取图表中的某个数据系列时,在公式栏中就会显示相应的SERIES公式,但这个公...

    fanjy
  • 【JS】388- 深入了解强大的 ES6 「 ... 」 运算符

    ... 运算符,是 ES6 里一个新引入的运算法,也叫 展开/收集 运算符,我们每天都要和它打交道。

    pingan8787
  • 获顶会最佳论文,天津大学等用强化学习寻找游戏bug

    软件工程领域顶级会议 34th IEEE/ACM International Conference on Automated Software Engineer...

    机器之心

扫码关注云+社区

领取腾讯云代金券