递归函数两种方式的区别

目录

概述

递归函数都不陌生,比如计算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)的时候,对于上面的第一种情况,函数栈大概长这样(仅保留参数和返回值,忽略其他内容):

img

文字描述就是:

f(1)=1
f(2)=2f(1)=21=2
f(3)=3f(2)=32=6
f(4)=4f(3)=46=24

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

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

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

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

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

img

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

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

------------

原文地址 https://hujingnb.com/archives/276

转载请保留原文连接: 递归函数两种方式的区别 | 烟草的香味

guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x