递归函数优缺点

谁践踏了优雅 2023-02-26 12:23 6阅读 0赞

递归函数的优点是定义简单，逻辑清晰。理论上，所的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。  
使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

解决递归函数缺点的方法：  
解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。  
尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。  
例：

def fact(n):
        if n==1:
            return 1
        return n * fact(n - 1)

===> fact(5)
    =
    ===> 5 * fact(4)
    =
    ===> 5 * (4 * fact(3))
    =
    ===> 5 * (4 * (3 * fact(2)))
    =
    ===> 5 * (4 * (3 * (2 * fact(1))))
    =
    ===> 5 * (4 * (3 * (2 * 1)))
    =
    ===> 5 * (4 * (3 * 2))
    =
    ===> 5 * (4 * 6)
    =
    ===> 5 * 24
    =
    ===> 120

修改后：

def fact_iter(num, product):
        if num == 1:
            return product
        return fact_iter(num - 1, num * product)

===> fact_iter(5, 1)
    =
    ===> fact_iter(4, 5)
    =
    ===> fact_iter(3, 20)
    =
    ===> fact_iter(2, 60)
    =
    ===> fact_iter(1, 120)
    =
    ===> 120

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关 java基础递归算法以及优缺点

什么是递归算法？递归算法就是A方法调用A方法，就是自己调用自己。注意：一定要指明什么时候方法结束，不然会进入死循环，直至计算机资源被耗尽。实例：计算10的阶乘

不念不忘少年蓝@/ 2023年10月18日 16:23/ 0 赞/ 141 阅读

相关递归函数优缺点

递归函数的优点是定义简单，逻辑清晰。理论上，所的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（st

谁践踏了优雅/ 2023年02月26日 12:23/ 0 赞/ 7 阅读

相关递归——递归函数的详细过程

函数递归什么是递归？递归的两个必要条件例子斐波那契数的递归求解 n的阶乘递归求解什么是递归？程序调

港控/mmm°/ 2022年12月26日 09:26/ 0 赞/ 250 阅读

相关递归的优缺点

优点： 1. 简洁 2.在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。缺点： 1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次

桃扇骨/ 2022年07月16日 14:22/ 0 赞/ 135 阅读

相关递归函数调用递归函数

题目如下：问下列代码的打印结果为0吗？ \[cpp\] [view plain][] [copy][view plain] 1. \include <stdlib.h>

柔光的暖阳◎/ 2022年06月13日 10:07/ 0 赞/ 351 阅读

相关递归的函数

递归的函数 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem De

待我称王封你为后i/ 2022年06月09日 01:26/ 0 赞/ 303 阅读

相关递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。举个例子，我们来计算阶乘`n! = 1 x 2 x 3 x ... x n`，用函数`f

骑猪看日落/ 2022年05月18日 04:17/ 0 赞/ 305 阅读

相关函数递归

函数递归函数递归：函数重复地调用自己，这叫递归。 <table> <tbody> <tr> <td>

你的名字/ 2022年01月07日 15:53/ 0 赞/ 312 阅读

相关 python 递归函数

def factoria(n): if n == 1: return 1 else: r

缺乏、安全感/ 2021年11月15日 13:30/ 0 赞/ 398 阅读

相关 python 递归函数

递归函数(了解) 定义：函数内部调用函数本身的函数叫递归函数组成：函数内部调用自己终止条件核心算法

女爷i/ 2021年09月20日 12:44/ 0 赞/ 478 阅读