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 有些问题只有递归能够解决.非递归的方法无法实现.如:汉诺塔.
递归的条件:
并不是说所有的问题都可以使用递归解决，他必须的满足一定的条件。即有一个出口点.也就是说当满足一定条件时，程序可以结束，从而完成递归调用，否则就陷入了无限的递归调用之中了.并且这个条件还要是可达到的.
递归有哪些优点:
易读，容易理解，代码一般比较短.
递归有哪些缺点:
占用内存资源多，费时，效率低下.
因此在我们写程序的时候不要轻易的使用递归，虽然他有他的优点，但是我们要在易读性和空间，效率上多做权衡.一般情况下我们还是使用非递归的方法解决问题.若一个算法非递归解法非常难于理解。我们使用递归也未尝不可.如:二叉树的遍历算法.非递归的算法很难与理解.而相比递归算法就容易理解很多.
对于递归调用的问题，我们在前一段时间写图形学程序时，其中有一个四连同填充算法就是使用递归的方法。结果当要填充的图形稍微大一些时，程序就自动关闭了.这不是一个人的问题，所有人写出来的都是这个问题.当时我们给与的解释就是堆栈溢出。就多次递归调用占用太多的内存资源致使堆栈溢出，程序没有内存资源执行下去，从而被操作系统强制关闭了.这是一个真真切切的例子。所以我们在使用递归的时候需要权衡再三.
在进行数据处理时，如果数据简单，数量不多，excel是大家的首选。但是当数据众多，类型复杂，需要灵活地显示切片、进行索引、以及排序时，python会更加方便。借助python中的numpy和pandas库，它能快速完成各种任务，包括数据的创建、检查、清洗、预处理、提取、筛选、汇总、统计等。接下来几篇文章，将以excel为参照，介绍python中数据的处理。
提到pandas，那就不得不提两类重要的数据结构，Series和DataFrame，这两类数据结构都是建立在numpy的数组array基础上。与array相比，Series是一个一维的数据集，但是每个数据元素都带有一个索引，有点类似于字典。而DataFrame在数组的基础上，增加了行索引和列索引，类似于Series的字典，或者说是一个列表集。
所以在数据处理前，要安装好numpy , pandas。接下来就看看如何完成一套完整的数据操作。
创建数据表的方法分两种，分别是从外部导入数据，以及直接写入数据。
在python中，也可外部导入xlsx格式文件，使用read_excel()函数：
import pandas as pd
from pandas import DataFrame,Series
data=DataFrame(pd.read_excel('c:/python27/test.xlsx'))
print data
输出：
Gene Size Function
0 arx1 411 NaN
1 arx2 550 monooxygenase
2 arx3 405 aminotransferase
……
即：调用pandas中read_excel属性，来读取文件test.xlsx，并转换成DataFrame格式，赋给变量data。在每一行后，自动分了一个索引值。除了excel，还支持以下格式文件的导入和写入：
Python写入的方法有很多，但还是不如excel方便。常用的例如使用相等长度的字典或numpy数组来创建：
data1 = DataFrame(
{'Gene':['arx1','arx2','arx3'],
'Size':[411,550,405],
'Func':[np.NaN,'monooxygenase','aminotransferase ']})
print data1
输出
Func Gene Size
0 NaN arx1 411
1 monooxyg arx2 550
2 amino arx3 405
分配一个行索引后，自动排序并输出。
在python中，可以使用info()函数查看整个数据的详细信息。
print data.info()
输出
RangeIndex: 7 entries, 0 to 6
Data columns (total 3 columns):
Gene 7 non-null object
Size 7 non-null int64
Function 5 non-null object
dtypes: int64(1), object(2)
memory usage: 240.0+ bytes
None
此外，还可以通过shape, column, index, values, dtypes等函数来查看数据维度、行列组成、所有的值、 数据类型：
print data1.shape
print data1.index
print data1.columns
print data1.dtypes
输出
(3, 3)
RangeIndex(start=0, stop=3, step=1)
Index([u'Func', u'Gene', u'Size'], dtype='object')
Func object
Gene object
Size int64
dtype: object
在excel中可以按“F5”，在“定位条件”中选择“空值”，选中后，输入替换信息，再按“Ctrl+Enter”即可完成替换。
在python中，使用函数 isnull 和 notnull 来检测数据丢失, 包含空值返回True，不包含则返回False。
pd.isnull(data1)
pd.notnull(data1)
也可以使用函数的实例方法，以及加入参数，对某一列进行检查：
print data1['Func'].isnull()
输出
Func Gene Size
0 True False False
1 False False False
2 False False False
再使用fillna对空值进行填充：
data.fillna(value=0)
#用0来填充空值
data['Size'].fillna(data1['Size'].mean())
#用data1中Size列的平均值来填充空值
data['Func']=data['Func'].map(str.strip)
#清理Func列中存在的空格
Excel中可以按“Ctrl+F”，可调出替换对话框，替换相应数据。
Python中，使用replace函数替换：
data['Func'].replace('monooxygenase', 'oxidase')
将Func列中的'monooxygenase'替换成'oxidase'。
Excel中，通过“数据-筛选-高级”可以选择性地看某一列的唯一值。
Python中，使用unique函数查看：
print data['Func'].unique()
输出
[nan u'monooxygenase' u'aminotransferase' u'methyltransferase']
Excel中，通过UPPER、LOWER、PROPER等函数来变成大写、小写、首字母大写。
Python中也有同名函数：
data1['Gene'].str.lower()
Excel中可以通过“数据-删除重复项”来去除重复值。
Python中，可以通过drop_duplicates函数删除重复值：
print data['Func'].drop_duplicates()
输出
0 NaN
1 monooxygenase
2 aminotransferase
3 methyltransferase
Name: Func, dtype: object
还可以设置“ keep=’last’ ”参数，后出现的被保留，先出现的被删除：
print data['Func'].drop_duplicates(keep='last')
输出
2 aminotransferase
3 methyltransferase
6 monooxygenase
8 NaN
Name: Func, dtype: object
内容参考：
Python For Data Analysis
蓝鲸网站分析博客，作者蓝鲸（王彦平）
这份资料非常纯粹，只有Python的基础语法，专门针对想要学习Python的小白。
Python中用#表示单行注释，#之后的同行的内容都会被注释掉。
使用三个连续的双引号表示多行注释，两个多行注释标识之间内容会被视作是注释。
Python当中的数字定义和其他语言一样：
我们分别使用+, -, *, /表示加减乘除四则运算符。
这里要注意的是，在Python2当中，10/3这个操作会得到3，而不是3.33333。因为除数和被除数都是整数，所以Python会自动执行整数的计算，帮我们把得到的商取整。如果是10.0 / 3，就会得到3.33333。目前Python2已经不再维护了，可以不用关心其中的细节。
但问题是Python是一个 弱类型 的语言，如果我们在一个函数当中得到两个变量，是无法直接判断它们的类型的。这就导致了同样的计算符可能会得到不同的结果，这非常蛋疼。以至于程序员在运算除法的时候，往往都需要手工加上类型转化符，将被除数转成浮点数。
在Python3当中拨乱反正，修正了这个问题，即使是两个整数相除，并且可以整除的情况下，得到的结果也一定是浮点数。
如果我们想要得到整数，我们可以这么操作：
两个除号表示 取整除 ，Python会为我们保留去除余数的结果。
除了取整除操作之外还有取余数操作，数学上称为取模，Python中用%表示。
Python中支持 乘方运算 ，我们可以不用调用额外的函数，而使用**符号来完成：
当运算比较复杂的时候，我们可以用括号来强制改变运算顺序。
Python中用首字母大写的True和False表示真和假。
用and表示与操作，or表示或操作，not表示非操作。而不是C++或者是Java当中的, || 和！。
在Python底层， True和False其实是1和0 ，所以如果我们执行以下操作，是不会报错的，但是在逻辑上毫无意义。
我们用==判断相等的操作，可以看出来True==1， False == 0.
我们要小心Python当中的bool()这个函数，它并不是转成bool类型的意思。如果我们执行这个函数，那么 只有0会被视作是False，其他所有数值都是True ：
Python中用==判断相等，表示大于，=表示大于等于， 表示小于，=表示小于等于，!=表示不等。
我们可以用and和or拼装各个逻辑运算：
注意not，and，or之间的优先级，其中not and or。如果分不清楚的话，可以用括号强行改变运行顺序。
关于list的判断，我们常用的判断有两种，一种是刚才介绍的==，还有一种是is。我们有时候也会简单实用is来判断，那么这两者有什么区别呢？我们来看下面的例子：
Python是全引用的语言，其中的对象都使用引用来表示。is判断的就是 两个引用是否指向同一个对象 ，而==则是判断两个引用指向的具体内容是否相等。举个例子，如果我们把引用比喻成地址的话，is就是判断两个变量的是否指向同一个地址，比如说都是沿河东路XX号。而==则是判断这两个地址的收件人是否都叫张三。
显然，住在同一个地址的人一定都叫张三，但是住在不同地址的两个人也可以都叫张三，也可以叫不同的名字。所以如果a is b，那么a == b一定成立，反之则不然。
Python当中对字符串的限制比较松， 双引号和单引号都可以表示字符串 ，看个人喜好使用单引号或者是双引号。我个人比较喜欢单引号，因为写起来方便。
字符串也支持+操作，表示两个字符串相连。除此之外，我们把两个字符串写在一起，即使没有+，Python也会为我们拼接：
我们可以使用[]来查找字符串当中某个位置的字符，用 len 来计算字符串的长度。
我们可以在字符串前面 加上f表示格式操作 ，并且在格式操作当中也支持运算，比如可以嵌套上len函数等。不过要注意，只有Python3.6以上的版本支持f操作。
最后是None的判断，在Python当中None也是一个对象， 所有为None的变量都会指向这个对象 。根据我们前面所说的，既然所有的None都指向同一个地址，我们需要判断一个变量是否是None的时候，可以使用is来进行判断，当然用==也是可以的，不过我们通常使用is。
理解了None之后，我们再回到之前介绍过的bool()函数，它的用途其实就是判断值是否是空。所有类型的 默认空值会被返回False ，否则都是True。比如0，""，[], {}, ()等。
除了上面这些值以外的所有值传入都会得到True。
Python当中的标准输入输出是 input和print 。
print会输出一个字符串，如果传入的不是字符串会自动调用__str__方法转成字符串进行输出。 默认输出会自动换行 ，如果想要以不同的字符结尾代替换行，可以传入end参数：
使用input时，Python会在命令行接收一行字符串作为输入。可以在input当中传入字符串，会被当成提示输出：
Python支持 三元表达式 ，但是语法和C++不同，使用if else结构，写成：
上段代码等价于：
Python中用[]表示空的list，我们也可以直接在其中填充元素进行初始化：
使用append和pop可以在list的末尾插入或者删除元素：
list可以通过[]加上下标访问指定位置的元素，如果是负数，则表示 倒序访问 。-1表示最后一个元素，-2表示倒数第二个，以此类推。如果访问的元素超过数组长度，则会出发 IndexError 的错误。
list支持切片操作，所谓的切片则是从原list当中 拷贝 出指定的一段。我们用start: end的格式来获取切片，注意，这是一个 左闭右开区间 。如果留空表示全部获取，我们也可以额外再加入一个参数表示步长，比如[1:5:2]表示从1号位置开始，步长为2获取元素。得到的结果为[1, 3]。如果步长设置成-1则代表反向遍历。
如果我们要指定一段区间倒序，则前面的start和end也需要反过来，例如我想要获取[3: 6]区间的倒序，应该写成[6:3:-1]。
只写一个:，表示全部拷贝，如果用is判断拷贝前后的list会得到False。可以使用del删除指定位置的元素，或者可以使用remove方法。
insert方法可以 指定位置插入元素 ，index方法可以查询某个元素第一次出现的下标。
list可以进行加法运算，两个list相加表示list当中的元素合并。 等价于使用extend 方法：
我们想要判断元素是否在list中出现，可以使用 in关键字 ，通过使用len计算list的长度：
tuple和list非常接近，tuple通过()初始化。和list不同， tuple是不可变对象 。也就是说tuple一旦生成不可以改变。如果我们修改tuple，会引发TypeError异常。
由于小括号是有改变优先级的含义，所以我们定义单个元素的tuple， 末尾必须加上逗号 ，否则会被当成是单个元素：
tuple支持list当中绝大部分操作：
我们可以用多个变量来解压一个tuple：
解释一下这行代码：
我们在b的前面加上了星号， 表示这是一个list 。所以Python会在将其他变量对应上值的情况下，将剩下的元素都赋值给b。
补充一点，tuple本身虽然是不可变的，但是 tuple当中的可变元素是可以改变的 。比如我们有这样一个tuple：
我们虽然不能往a当中添加或者删除元素，但是a当中含有一个list，我们可以改变这个list类型的元素，这并不会触发tuple的异常：
dict也是Python当中经常使用的容器，它等价于C++当中的map，即 存储key和value的键值对 。我们用{}表示一个dict，用:分隔key和value。
对 。我们用{}表示一个dict，用:分隔key和value。
dict的key必须为不可变对象，所以 list、set和dict不可以作为另一个dict的key ，否则会抛出异常：
我们同样用[]查找dict当中的元素，我们传入key，获得value，等价于get方法。
我们可以call dict当中的keys和values方法，获取dict当中的所有key和value的集合，会得到一个list。在Python3.7以下版本当中，返回的结果的顺序可能和插入顺序不同，在Python3.7及以上版本中，Python会保证返回的顺序和插入顺序一致：
我们也可以用in判断一个key是否在dict当中，注意只能判断key。
如果使用[]查找不存在的key，会引发KeyError的异常。如果使用 get方法则不会引起异常，只会得到一个None ：
setdefault方法可以 为不存在的key 插入一个value，如果key已经存在，则不会覆盖它：
我们可以使用update方法用另外一个dict来更新当前dict，比如a.update(b)。对于a和b交集的key会被b覆盖，a当中不存在的key会被插入进来：
我们一样可以使用del删除dict当中的元素，同样只能传入key。
Python3.5以上的版本支持使用**来解压一个dict：
set是用来存储 不重复元素 的容器，当中的元素都是不同的，相同的元素会被删除。我们可以通过set()，或者通过{}来进行初始化。注意当我们使用{}的时候，必须要传入数据，否则Python会将它和dict弄混。
set当中的元素也必须是不可变对象，因此list不能传入set。
可以调用add方法为set插入元素：
set还可以被认为是集合，所以它还支持一些集合交叉并补的操作。
set还支持 超集和子集的判断 ，我们可以用大于等于和小于等于号判断一个set是不是另一个的超集或子集：
和dict一样，我们可以使用in判断元素在不在set当中。用copy可以拷贝一个set。
Python当中的判断语句非常简单，并且Python不支持switch，所以即使是多个条件，我们也只能 罗列if-else 。
我们可以用in来循环迭代一个list当中的内容，这也是Python当中基本的循环方式。
如果我们要循环一个范围，可以使用range。range加上一个参数表示从0开始的序列，比如range(10)，表示[0, 10)区间内的所有整数：
如果我们传入两个参数，则 代表迭代区间的首尾 。
如果我们传入第三个元素，表示每次 循环变量自增的步长 。
如果使用enumerate函数，可以 同时迭代一个list的下标和元素 ：
while循环和C++类似，当条件为True时执行，为false时退出。并且判断条件不需要加上括号：
Python当中使用 try和except捕获异常 ，我们可以在except后面限制异常的类型。如果有多个类型可以写多个except，还可以使用else语句表示其他所有的类型。finally语句内的语法 无论是否会触发异常都必定执行 ：
在Python当中我们经常会使用资源，最常见的就是open打开一个文件。我们 打开了文件句柄就一定要关闭 ，但是如果我们手动来编码，经常会忘记执行close操作。并且如果文件异常，还会触发异常。这个时候我们可以使用with语句来代替这部分处理，使用with会 自动在with块执行结束或者是触发异常时关闭打开的资源 。
以下是with的几种用法和功能：
凡是可以使用in语句来迭代的对象都叫做 可迭代对象 ，它和迭代器不是一个含义。这里只有可迭代对象的介绍，想要了解迭代器的具体内容，请移步传送门：
Python——五分钟带你弄懂迭代器与生成器，夯实代码能力
当我们调用dict当中的keys方法的时候，返回的结果就是一个可迭代对象。
我们 不能使用下标来访问 可迭代对象，但我们可以用iter将它转化成迭代器，使用next关键字来获取下一个元素。也可以将它转化成list类型，变成一个list。
使用def关键字来定义函数，我们在传参的时候如果指定函数内的参数名， 可以不按照函数定义的顺序 传参：
可以在参数名之前加上*表示任意长度的参数，参数会被转化成list：
也可以指定任意长度的关键字参数，在参数前加上**表示接受一个dict：
当然我们也可以两个都用上，这样可以接受任何参数：
传入参数的时候我们也可以使用*和**来解压list或者是dict：
Python中的参数 可以返回多个值 ：
函数内部定义的变量即使和全局变量重名，也 不会覆盖全局变量的值 。想要在函数内部使用全局变量，需要加上 global 关键字，表示这是一个全局变量：
Python支持 函数式编程 ，我们可以在一个函数内部返回一个函数：
Python中可以使用lambda表示 匿名函数 ，使用:作为分隔，:前面表示匿名函数的参数，:后面的是函数的返回值：
我们还可以将函数作为参数使用map和filter，实现元素的批量处理和过滤。关于Python中map、reduce和filter的使用，具体可以查看之前的文章：
五分钟带你了解map、reduce和filter
我们还可以结合循环和判断语来给list或者是dict进行初始化：
使用 import语句引入一个Python模块 ，我们可以用.来访问模块中的函数或者是类。
我们也可以使用from import的语句，单独引入模块内的函数或者是类，而不再需要写出完整路径。使用from import *可以引入模块内所有内容（不推荐这么干）
可以使用as给模块内的方法或者类起别名：
我们可以使用dir查看我们用的模块的路径：
这么做的原因是如果我们当前的路径下也有一个叫做math的Python文件，那么 会覆盖系统自带的math的模块 。这是尤其需要注意的，不小心会导致很多奇怪的bug。
我们来看一个完整的类，相关的介绍都在注释当中
以上内容的详细介绍之前也有过相关文章，可以查看：
Python—— slots ，property和对象命名规范
下面我们来看看Python当中类的使用：
这里解释一下，实例和对象可以理解成一个概念，实例的英文是instance，对象的英文是object。都是指类经过实例化之后得到的对象。
继承可以让子类 继承父类的变量以及方法 ，并且我们还可以在子类当中指定一些属于自己的特性，并且还可以重写父类的一些方法。一般我们会将不同的类放在不同的文件当中，使用import引入，一样可以实现继承。
我们创建一个蝙蝠类：
我们再创建一个蝙蝠侠的类，同时继承Superhero和Bat：
执行这个类：
我们可以通过yield关键字创建一个生成器，每次我们调用的时候执行到yield关键字处则停止。下次再次调用则还是从yield处开始往下执行：
除了yield之外，我们还可以使用()小括号来生成一个生成器：
关于生成器和迭代器更多的内容，可以查看下面这篇文章：
五分钟带你弄懂迭代器与生成器，夯实代码能力
我们引入functools当中的wraps之后，可以创建一个装饰器。装饰器可以在不修改函数内部代码的前提下，在外面包装一层其他的逻辑:
装饰器之前也有专门的文章详细介绍，可以移步下面的传送门：
一文搞定Python装饰器，看完面试不再慌
不知道有多少小伙伴可以看到结束，原作者的确非常厉害，把Python的基本操作基本上都囊括在里面了。如果都能读懂并且理解的话，那么Python这门语言就算是入门了。
如果你之前就有其他语言的语言基础，我想本文读完应该不用30分钟。当然在30分钟内学会一门语言是不可能的，也不是我所提倡的。但至少通过本文我们可以做到熟悉Python的语法，知道大概有哪些操作，剩下的就要我们亲自去写代码的时候去体会和运用了。
根据我的经验，在学习一门新语言的前期，不停地查阅资料是免不了的。希望本文可以作为你在使用Python时候的查阅文档。
最后，我这里有各种免费的编程类资料，有需要的及时私聊我，回复"学习"，分享给大家，正在发放中............