Python递归函数定义与用法示例

本文实例讲述了Python递归函数定义与用法。分享给大家供大家参考，具体如下：

递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

举个例子，我们来计算阶乘 n! = 1 * 2 * 3 * ... * n，用函数 fact(n)表示，可以看出：

fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n

所以，fact(n)可以表示为 n * fact(n-1)，只有n=1时需要特殊处理。
于是，fact(n)用递归的方式写出来就是：

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

上面就是一个递归函数。可以试试：

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

如果我们计算fact(5)，可以根据函数定义看到计算过程如下：

===> 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

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。可以试试计算 fact(10000)。

def digui(n):
  sum = 0
  if n<=0:
    return 1
  else:
    return n*digui(n-1)
print(digui(5))

更多关于Python相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python中你应该知道的一些内置函数

    Python中你应该知道的一些内置函数

    前言 python内置了一些非常巧妙而且强大的内置函数,对初学者来说,一般不怎么用到,我也是用了一段时间python之后才发现,哇还有这么好的函数,这个函数都是经典的而且经过严格测试的,可以一下子省了你原来很多事情,代码不仅简洁易读了很多,而且不用自己去闭门造车.既方便了自己又减少了bug. 一.sorted() 1)对于一个列表排序 sorted([100, 98, 102, 1, 40]) >>>[1, 40, 98, 100, 102] 2)通过key参数/函数 比如一个长列表里面

  • 详谈Python基础之内置函数和递归

    详谈Python基础之内置函数和递归

    一.内置函数 下面简单介绍几个: 1.abs() 求绝对值 2.all() 如果 iterable 的所有元素都为真(或者如果可迭代为空),则返回 True 3.any() 如果 iterable 的任何元素为真,则返回 True.如果iterable为空,则返回 False 4.callable() 如果 object 参数出现可调,则返回 True,否则返回 False 5.divmod() 以两个(非复数)数字作为参数,并在使用整数除法时返回由商和余数组成的一对数字.对于混合操作数类型,二

  • Python基础之函数用法实例详解

    本文以实例形式较为详细的讲述了Python函数的用法,对于初学Python的朋友有不错的借鉴价值.分享给大家供大家参考之用.具体分析如下: 通常来说,Python的函数是由一个新的语句编写,即def,def是可执行的语句--函数并不存在,直到Python运行了def后才存在. 函数是通过赋值传递的,参数通过赋值传递给函数 def语句将创建一个函数对象并将其赋值给一个变量名,def语句的一般格式如下: def <name>(arg1,arg2,arg3,--,argN): <stateme

  • 深入理解python函数递归和生成器

    一.什么是递归 如果函数包含了对其自身的调用,该函数就是递归的.递归做为一种算法在程序设计语言中广泛应用,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.例如,要计算1-9的9位数字的乘积,直观的算法是1*2*3*4*5*6*7*8*9,如果要计算1-10000的乘积,直观的算法就难于实现出,而递归就可以很简单的实现.请看示例: def fact(n):#计算给定数字到一的乘积 i

  • Python入门及进阶笔记 Python 内置函数小结

    内置函数 常用函数 1.数学相关 •abs(x) abs()返回一个数字的绝对值.如果给出复数,返回值就是该复数的模. 复制代码 代码如下: >>>print abs(-100) 100 >>>print abs(1+2j) 2.2360679775 •divmod(x,y) divmod(x,y)函数完成除法运算,返回商和余数. 复制代码 代码如下: >>> divmod(10,3) (3, 1) >>> divmod(9,3) (

  • Python内置函数Type()函数一个有趣的用法

    今天在网上看到type的一段代码 ,然后查了一下文档,才知道type还有三个参数的用法. http://docs.python.org/2/library/functions.html#type 以前只是知道type可以检测对象类型.然后发现了一个有趣的用法. 复制代码 代码如下: def println(self): a = 1 + 1 print "%s,%s" % (self.aa, a) A = type('A',(),{'aa':'print a', 'println': p

  • Python 递归函数详解及实例

    Python 递归函数详解及实例

    Python 递归函数 如果一个函数体直接或者间接调用自己,那么这个函数就称为递归函数．也就是说,递归函数体的执行过程中可能会返回去再次调用该函数．在python里,递归函数不需要任何特殊的语法,但是它需要付出一定的努力去理解和创建． 我们会以一个简单的例子开始:写一个函数求一个自然数中所有数字的和．在设计递归函数的时候,我们会寻找能把问题分解成简单的问题的方法．在这道题中,运算符%和//可以用来把一个数分成两部分:最低位和不包含最低位数字两部分． 18117的数字和为:1+8+1+1+7＝18

  • Python递归函数定义与用法示例

    本文实例讲述了Python递归函数定义与用法.分享给大家供大家参考,具体如下: 递归函数 在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘 n! = 1 * 2 * 3 * ... * n,用函数 fact(n)表示,可以看出: fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n 所以,fact(n)可以表示为 n * fact(n-1),只有

  • javascript递归函数定义和用法示例分析

    递归函数:是指函数直接或间接调用函数本身,则称该函数为递归函数. 这句话理解起来并不难,从概念上出发,给出以下的例子: function foo(){ console.log("函数 foo 是递归函数."); foo(); } 这个例子的 foo 函数就是一个递归函数. 当你把这个函数拿到浏览器上运行的时候,你会发现内存溢出了,为什么呢?因为这个递归函数没有停止处理或运算的出口,因此这个递归函数就演变为一个死循环. 那如何使用递归呢? 使用递归函数必须要符合两个条件: 1. 在每一次

  • python中hashlib模块用法示例

    我们以前介绍过一篇Python加密的文章:Python 加密的实例详解.今天我们看看python中hashlib模块用法示例,具体如下. hashlib hashlib主要提供字符加密功能,将md5和sha模块整合到了一起,支持md5,sha1, sha224, sha256, sha384, sha512等算法 具体应用 #!/usr/bin/env python # -*- coding: UTF-8 -*- #pyversion:python3.5 #owner:fuzj import h

  • Android编程图片操作类定义与用法示例【拍照，相册选图及裁剪】

    本文实例讲述了Android编程图片操作类定义与用法.分享给大家供大家参考,具体如下: 主界面类:拍照及选择相册图片 import android.app.Activity; import android.content.Intent; import android.graphics.Bitmap; import android.net.Uri; import android.os.Bundle; import android.provider.MediaStore; import androi

  • JavaScript递归函数定义与用法实例分析

    本文实例讲述了JavaScript递归函数定义与用法.分享给大家供大家参考,具体如下: 递归函数是一个函数通过名字调用自身的情况下形成的,比如经典的递归阶乘函数: function factorial(num) { if (num <= 1) { return 1; } else { return num * factorial(num - 1); } } 上面的这种写法,可能会造成问题: var anotherFactorial = factorial; factorial = null; c

  • Python排序算法之选择排序定义与用法示例

    Python排序算法之选择排序定义与用法示例

    本文实例讲述了Python排序算法之选择排序定义与用法.分享给大家供大家参考,具体如下: 选择排序 选择排序比较好理解,好像是在一堆大小不一的球中进行选择(以从小到大,先选最小球为例): 1. 选择一个基准球 2. 将基准球和余下的球进行一一比较,如果比基准球小,则进行交换 3. 第一轮过后获得最小的球 4. 在挑一个基准球,执行相同的动作得到次小的球 5. 继续执行4,直到排序好 时间复杂度:O(n^2).  需要进行的比较次数为第一轮 n-1,n-2....1, 总的比较次数为 n*(n-1

  • Python抽象和自定义类定义与用法示例

    本文实例讲述了Python抽象和自定义类定义与用法.分享给大家供大家参考,具体如下: 抽象方法 class Person(): def say(self): pass class Student(Person): def say(self): print("i am student") 抽象类: 包含抽象方法的类 抽象类可以包含非抽象方法 抽象类可以有方法和属性 抽象类不能进行实例化 必须继承才能使用,且继承的子类必须实现所有抽象方法 import abc class Person(m

  • Python迭代器和生成器定义与用法示例

    本文实例讲述了Python迭代器和生成器定义与用法.分享给大家供大家参考,具体如下: 迭代器 iter() 迭代器是访问集合中元素的一种方式,迭代器 object 从集合中的第一个元素开始访问,直到所有的元素被访问完成. 所以迭代器的特点是:只能往前,不能后退 迭代器的优点:不需要提前准备整个迭代器中的所有元素,仅仅迭代到某个元素时才计算该元素,而之前或者之后,元素可以不存在或者销毁.因为这个特点,迭代器特别适合遍历文件比较大或者无限的集合. 总结下迭代器 iter()的特点吧: 1.访问者不需

  • Django自定义过滤器定义与用法示例

    本文实例讲述了Django自定义过滤器定义与用法.分享给大家供大家参考,具体如下: 一.自定义过滤器的介绍 前面我们就介绍过过滤器其实就是一个函数,把要过来的字段传递到一个函数内,进行加工处理,返回一个新的值展现在页面中,在实际开发中系统自带的过滤器有时候不能满足我们的需求的时候就要自定义 二.Django中自定义过滤器有两种方式 1.在组件(App)中的templatetags创建一个单独的py文件 2.单独创建一个组件(App)用来存放项目中所有的自定义过滤器 三.在项目中的组件中创建自定义

  • Python pluggy模块的用法示例演示

    目录 1 pluggy 简介 2 安装 3 使用初体验 4 详解解释 5 HookspeckMarker装饰器支持传入一些特定的参数 6 HookImplMarker装饰器也支持传入一些特定的参数 1 pluggy 简介 pluggy 作用:提供了一个简易便捷的插件系统,可以做到插件与主题功能松耦合 pluggy 是pytest,tox,devpi的核心框架 2 安装 执行如下命令即可 pip install pluggy 3 使用初体验 import pluggy # HookspecMark

随机推荐