189 8069 5689
函数的递归调用
公司主营业务：成都网站建设、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联公司推出赞皇免费做网站回馈大家。
递归问题是一个说简单也简单，说难也有点难理解的问题.我想非常有必要对其做一个总结.
首先理解一下递归的定义，递归就是直接或间接的调用自身.而至于什么时候要用到递归，递归和非递归又有那些区别？又是一个不太容易掌握的问题，更难的是对于递归调用的理解.下面我们就从程序+图形的角度对递归做一个全面的阐述.
我们从常见到的递归问题开始:
1 阶层函数
#include iostream
using namespace std;
int factorial(int n)
{
if (n == 0)
{
return 1;
}
else
{
int result = factorial(n-1);
return n * result;
}
}
int main()
{
int x = factorial(3);
cout x endl;
return 0;
}
这是一个递归求阶层函数的实现。很多朋友只是知道该这么实现的，也清楚它是通过不断的递归调用求出的结果.但他们有些不清楚中间发生了些什么.下面我们用图对此做一个清楚的流程:
根据上面这个图，大家可以很清楚的看出来这个函数的执行流程。我们的阶层函数factorial被调用了4次.并且我们可以看出在调用后面的调用中，前面的调用并不退出。他们同时存在内存中。可见这是一件很浪费资源的事情。我们该次的参数是3.如果我们传递10000呢。那结果就可想而知了.肯定是溢出了.就用int型来接收结果别说10000，100就会产生溢出.即使不溢出我想那肯定也是见很浪费资源的事情.我们可以做一个粗略的估计:每次函数调用就单变量所需的内存为:两个int型变量.n和result.在32位机器上占8B.那么10000就需要10001次函数调用.共需10001*8/1024 = 78KB.这只是变量所需的内存空间.其它的函数调用时函数入口地址等仍也需要占用内存空间。可见递归调用产生了一个不小的开销.
2 斐波那契数列
int Fib(int n)
{
if (n = 1)
{
return n;
}
else
{
return Fib(n-1) + Fib(n-2);
}
}
这个函数递归与上面的那个有些不同.每次调用函数都会引起另外两次的调用.最后将结果逐级返回.
我们可以看出这个递归函数同样在调用后买的函数时，前面的不退出而是在等待后面的结果，最后求出总结果。这就是递归.
3
#include iostream
using namespace std;
void recursiveFunction1(int num)
{
if (num 5)
{
cout num endl;
recursiveFunction1(num+1);
}
}
void recursiveFunction2(int num)
{
if (num 5)
{
recursiveFunction2(num+1);
cout num endl;
}
}
int main()
{
recursiveFunction1(0);
recursiveFunction2(0);
return 0;
}
运行结果:
1
2
3
4
4
3
2
1
该程序中有两个递归函数。传递同样的参数，但他们的输出结果刚好相反。理解这两个函数的调用过程可以很好的帮助我们理解递归:
我想能够把上面三个函数的递归调用过程理解了，你已经把递归调用理解的差不多了.并且从上面的递归调用中我们可以总结出递归的一个规律：他是逐级的调用，而在函数结束的时候是从最后面往前反序的结束.这种方式是很占用资源，也很费时的。但是有的时候使用递归写出来的程序很容易理解，很易读.
为什么使用递归:
1 有时候使用递归写出来的程序很容易理解，很易读.
2 有些问题只有递归能够解决.非递归的方法无法实现.如:汉诺塔.
递归的条件:
并不是说所有的问题都可以使用递归解决，他必须的满足一定的条件。即有一个出口点.也就是说当满足一定条件时，程序可以结束，从而完成递归调用，否则就陷入了无限的递归调用之中了.并且这个条件还要是可达到的.
递归有哪些优点:
易读，容易理解，代码一般比较短.
递归有哪些缺点:
占用内存资源多，费时，效率低下.
因此在我们写程序的时候不要轻易的使用递归，虽然他有他的优点，但是我们要在易读性和空间，效率上多做权衡.一般情况下我们还是使用非递归的方法解决问题.若一个算法非递归解法非常难于理解。我们使用递归也未尝不可.如:二叉树的遍历算法.非递归的算法很难与理解.而相比递归算法就容易理解很多.
对于递归调用的问题，我们在前一段时间写图形学程序时，其中有一个四连同填充算法就是使用递归的方法。结果当要填充的图形稍微大一些时，程序就自动关闭了.这不是一个人的问题，所有人写出来的都是这个问题.当时我们给与的解释就是堆栈溢出。就多次递归调用占用太多的内存资源致使堆栈溢出，程序没有内存资源执行下去，从而被操作系统强制关闭了.这是一个真真切切的例子。所以我们在使用递归的时候需要权衡再三.
表示一个功能，函数定义着是提供功能的人，函数调用者是使用功能的人。
print:打印功能，将括号中的内容，显示到终端。
将括号中的内容显示在控制台.
input：输入功能，从终端中获取输入的信息，存到程序变量当中
作用：将用户输入的内容赋值给变量
第一个字符必须是字母表中字母或下划线 _ 。
标识符的其他的部分由字母、数字和下划线组成。
标识符对大小写敏感。
python最具特色的就是使用缩进来表示代码块，不需要使用大括号 {} 。
缩进的空格数是可变的，但是同一个代码块的语句必须包含相同的缩进空格数。实例如下：
使用print时，也可以在语句中添加多个表达式，每个表达式用逗 号分隔；在用逗号分隔输出时，print语句会在每个输出项后面自动添加一 个空格；
注意：不管时字符串还是其他类型都是转化为字符串进行打印！
Python 有很多有用的内置函数， 但还是不能满足程序员的需求， 所以需要 自定义函数 。
如何编写 自定义函数 ， 需要用到 def语句， 函数名， 括号及参数， 冒号， 函数说明，内置缩进编码模块，return 语句 ， 其中有一些也可省略不写，后面会慢慢介绍。
编写函数不可或缺的元素， 一定都要写。函数名尽量写得简单易懂。
一般是对函数的描述说明。
这是编写具体的 操作命令 的地方， 如果还未想好如何编写， 可以使用 pass 来占位，让程序可以运行起来，防止调试出错。
参数放在最后讲， 是因为这里面的东西还是很多的。首先看个例子。
如上的案例都是限制了参数个数的， 最多传三个参数 name/age/city ， 但是如果有一些特例，需要传多个参数怎么办呢。 参数前面加个 * , 变成 可变参数 。
那如果想要传多个包含名称的参数，例如a=1，b=2，c=3......，那该怎么写呢。参数前面加个 ** , 变成 关键字参数 。
python的常用内置函数
1.abs() 函数返回数字的绝对值
abs(-40)=40
2. dict() 函数用于创建一个字典
dict()
{} #创建一个空字典类似于u={},字典的存取方式一般为key-value
例如u = {"username":"tom", "age":18}
3. help() 函数用于查看函数或模块用途的详细说明
help('math')查看math模块的用处
a=[1,2,3,4]
help(a)查看列表list帮助信息
4.dir()获得当前模块的属性列表
dir(help)
['__call__', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__']
5.min() 方法返回给定参数的最小值 /参数可以为序列
a= min(10,20,30,40)
a
10
6. next() 返回迭代器的下一个项目
it = iter([1, 2, 3, 4, 5])
next(it)
1
next(it)
2
7. id() 函数用于获取对象的内存地址
a=12
id(a)
1550569552
8.enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
a=["tom","marry","leblan"]
list(enumerate(a))
[(0, 'tom'), (1, 'marry'), (2, 'leblan')]
9. oct() 函数将一个整数转换成8进制字符串
oct(15)
'0o17'
oct(10)
'0o12'
10. bin() 返回一个整数 int 或者长整数 long int 的二进制表示
bin(10)
'0b1010'
bin(15)
'0b1111'
11.eval() 函数用来执行一个字符串表达式，并返回表达式的值
eval('2+2')
4
12.int() 函数用于将一个字符串会数字转换为整型
int(3)
3
int(3.6)
3
int(3.9)
3
int(4.0)
4
13.open() 函数用于打开一个文件，创建一个file对象，相关的方法才可以调用它进行读写
f=open('test.txt')
14.str() 函数将对象转化为适于人阅读的形式
str(3)
'3'
15. bool() 函数用于将给定参数转换为布尔类型，如果没有参数，返回 False
bool()
False
bool(1)
True
bool(10)
True
bool(10.0)
True
16.isinstance() 函数来判断一个对象是否是一个已知的类型
a=5
isinstance(a,int)
True
isinstance(a,str)
False
17. sum() 方法对系列进行求和计算
sum([1,2,3],5)
11
sum([1,2,3])
6
18. super() 函数用于调用下一个父类(超类)并返回该父类实例的方法。super 是用来解决多重继承问题的，直接用类名调用父类方法
class User(object):
def__init__(self):
class Persons(User):
super(Persons,self).__init__()
19. float() 函数用于将整数和字符串转换成浮点数
float(1)
1.0
float(10)
10.0
20. iter() 函数用来生成迭代器
a=[1,2,3,4,5,6]
iter(a)
for i in iter(a):
... print(i)
...
1
2
3
4
5
6
21.tuple 函数将列表转换为元组
a=[1,2,3,4,5,6]
tuple(a)
(1, 2, 3, 4, 5, 6)
22.len() 方法返回对象（字符、列表、元组等）长度或项目个数
s = "playbasketball"
len(s)
14
a=[1,2,3,4,5,6]
len(a)
6
23. property() 函数的作用是在新式类中返回属性值
class User(object):
def __init__(self,name):
self.name = name
def get_name(self):
return self.get_name
@property
def name(self):
return self_name
24.type() 函数返回对象的类型
25.list() 方法用于将元组转换为列表
b=(1,2,3,4,5,6)
list(b)
[1, 2, 3, 4, 5, 6]
26.range() 函数可创建一个整数列表，一般用在 for 循环中
range(10)
range(0, 10)
range(10,20)
range(10, 20)
27. getattr() 函数用于返回一个对象属性值
class w(object):
... s=5
...
a = w()
getattr(a,'s')
5
28. complex() 函数用于创建一个复数或者转化一个字符串或数为复数。如果第一个参数为字符串，则不需要指定第二个参数
complex(1,2)
(1+2j)
complex(1)
(1+0j)
complex("1")
(1+0j)
29.max() 方法返回给定参数的最大值，参数可以为序列
b=(1,2,3,4,5,6)
max(b)
6
30. round() 方法返回浮点数x的四舍五入值
round(10.56)
11
round(10.45)
10
round(10.45,1)
10.4
round(10.56,1)
10.6
round(10.565,2)
10.56
31. delattr 函数用于删除属性
class Num(object):
... a=1
... b=2
... c=3.
.. print1 = Num()
print('a=',print1.a)
a= 1
print('b=',print1.b)
b= 2
print('c=',print1.c)
c= 3
delattr(Num,'b')
print('b=',print1.b)
Traceback (most recent call last): File "", line 1, inAttributeError: 'Num' object has no attribute 'b'
32. hash() 用于获取取一个对象（字符串或者数值等）的哈希值
hash(2)
2
hash("tom")
-1675102375494872622
33. set() 函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。
a= set("tom")
b = set("marrt")
a,b
({'t', 'm', 'o'}, {'m', 't', 'a', 'r'})
ab#交集
{'t', 'm'}
a|b#并集
{'t', 'm', 'r', 'o', 'a'}
a-b#差集
{'o'}