所谓基例就是不需要递归就能求解的,一般来说是问题的最小规模下的解。
创新互联建站是一家专注于网站设计、网站制作与策划设计,邱县网站建设哪家好?创新互联建站做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:邱县等地区。邱县做网站价格咨询:18980820575
例如:斐波那契数列递归,f(n) = f(n-1) + f(n-2),基例是1和2,f(1)和f(2)结果都是1
再比如:汉诺塔递归,基例就是1个盘子的情况,只需移动一次,无需递归
递归必须有基例,否则就是无法退出的递归,不能求解。
递归的思想主要是能够重复某些动作,比如简单的阶乘,次方,回溯中的八皇后,数独,还有汉诺塔,分形。
由于堆栈的机制,一般的递归可以保留某些变量在历史状态中,比如你提到的return x * power..., 但是某些或许庞大的问题或者是深度过大的问题就需要尽量避免递归,因为可能会栈溢出。还有一个问题是~python不支持尾递归优化!!!!所以~还是尽量避免递归的出现。
def power(x, n)
if n 0:
return 1
return x * power(x, n - 1)
power(3, 3)
3 * power(3, 2)
3 * (3 * power(3, 1))
3 * (3 * (3 * power(3, 0)))
3 * (3 * (3 * 1)) 这里n = 0, return 1
3 * (3 * 3)
3 * 9
27
当函数形参n=0的时候,开始回退~直到第一次调用power结束。
递归函数的特点:函数定义中直接或间接地调用了本函数,必定存在可使递归调用终止的条件,否则导致出现无限递归。
函数定义中所具有的这些特点是判断函数是否为递归函数的基本要素。
绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。
扩展资料:
数据类型可以通过递归来进行定义,比如一个简单的递归定义为自然数的定义:“一个自然数或等于0,或等于另一个自然数加上1”。Haskell中可以定义链表为:
data ListOfStrings = EmptyList | Cons String ListOfStrings
这一定义相当于宣告“一个链表或是空串列,或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。
参考资料来源:百度百科——递归算法
一、函数的定义
函数是指将一组语句的集合通过一个名字(函数名)封装起来,想要执行这个函数,只需要调用函数名即可
特性:
减少重复代码
使程序变得可扩展
使程序变得易维护
二、函数的参数
2.1、形参和实参数
形参,调用时才会存在的值
实惨,实际存在的值
2.2、默认参数
定义:当不输入参数值会有一个默认的值,默认参数要放到最后
2.3、 关键参数
定义: 正常情况下,给函数传参数要安装顺序,不想按顺序可以用关键参数,只需要指定参数名即可,(指定了参数名的就叫关键参数),但是要求是关键参数必须放在位置参数(以位置顺序确定对应的参数)之后
2.4、非固定参数
定义: 如你的函数在传入参数时不确定需要传入多少个参数,就可以使用非固定参数
# 通过元组形式传递
# 通过列表形式传递
# 字典形式(通过k,value的方式传递)
# 通过变量的方式传递
三、函数的返回值
作用:
返回函数执行结果,如果没有设置,默认返回None
终止函数运行,函数遇到return终止函数
四、变量的作用域
全局变量和局部变量
在函数中定义的变量叫局部变量,在程序中一开始定义的变量叫全局变量
全局变量作用域整个程序,局部变量作用域是定义该变量的函数
当全局变量与局部变量同名是,在定义局部变量的函数内,局部变量起作用,其他地方全局变量起作用
同级的局部变量不能互相调用
想要函数里边的变量设置成全局变量,可用global进行设置
五、特殊函数
5.1、嵌套函数
定义: 嵌套函数顾名思义就是在函数里边再嵌套一层函数
提示 在嵌套函数里边调用变量是从里往外依次调用,意思就是如果需要调用的变量在当前层没有就会去外层去调用,依次内推
匿名函数
基于Lambda定义的函数格式为: lambda 参数:函数体
参数,支持任意参数。
匿名函数适用于简单的业务处理,可以快速并简单的创建函数。
# 与三元运算结合
5.3、高阶函数
定义:变量可以指向函数,函数的参数可以接收变量,那么一个函数就可以接收另一个函数作为参数,这种函数称之为高阶函数 只需要满足一下任意一个条件,即是高阶函数
接收一个或多个函数作为输入
return返回另一个函数
5.4、递归函数
定义:一个函数可以调用其他函数,如果一个函数调用自己本身,这个函数就称为递归函数
在默认情况下Python最多能递归1000次,(这样设计师是为了防止被内存被撑死)可以通过sys.setrecursionlimit(1500)进行修改
递归实现过程是先一层一层的进,然后在一层一层的出来
必须有一个明确的条件结束,要不然就是一个死循环了
每次进入更深层次,问题规模都应该有所减少
递归执行效率不高,递归层次过多会导致站溢出
# 计算4的阶乘 4x3x2x1
# 打印数字从1-100
5.5、闭包现象
定义:内层函数调用外层函数的变量,并且内存函数被返回到外边去了
闭包的意义:返回的函数对象,不仅仅是一个函数对象,在该函数外还包裹了一层作用域,这使得,该函数无论在何处调用,优先使用自己外层包裹的作用域