python递归函数入门,python 递归函数

Python3：怎么通过递归函数

函数的递归调用

递归问题是一个说简单也简单，说难也有点难理解的问题.我想非常有必要对其做一个总结.

首先理解一下递归的定义，递归就是直接或间接的调用自身.而至于什么时候要用到递归，递归和非递归又有那些区别？又是一个不太容易掌握的问题，更难的是对于递归调用的理解.下面我们就从程序+图形的角度对递归做一个全面的阐述.

我们从常见到的递归问题开始:

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 有些问题只有递归能够解决.非递归的方法无法实现.如:汉诺塔.

递归的条件:

并不是说所有的问题都可以使用递归解决，他必须的满足一定的条件。即有一个出口点.也就是说当满足一定条件时，程序可以结束，从而完成递归调用，否则就陷入了无限的递归调用之中了.并且这个条件还要是可达到的.

递归有哪些优点:

易读，容易理解，代码一般比较短.

递归有哪些缺点:

占用内存资源多，费时，效率低下.

因此在我们写程序的时候不要轻易的使用递归，虽然他有他的优点，但是我们要在易读性和空间，效率上多做权衡.一般情况下我们还是使用非递归的方法解决问题.若一个算法非递归解法非常难于理解。我们使用递归也未尝不可.如:二叉树的遍历算法.非递归的算法很难与理解.而相比递归算法就容易理解很多.

对于递归调用的问题，我们在前一段时间写图形学程序时，其中有一个四连同填充算法就是使用递归的方法。结果当要填充的图形稍微大一些时，程序就自动关闭了.这不是一个人的问题，所有人写出来的都是这个问题.当时我们给与的解释就是堆栈溢出。就多次递归调用占用太多的内存资源致使堆栈溢出，程序没有内存资源执行下去，从而被操作系统强制关闭了.这是一个真真切切的例子。所以我们在使用递归的时候需要权衡再三.

相关问答

Q1: Python算法-爬楼梯与递归函数

可以看出来的是，该题可以用斐波那契数列解决。

楼梯一共有n层，每次只能走1层或者2层，而要走到最终的n层。不是从n-1或者就是n-2来的。

F(1) = 1

F(2) = 2

F(n) = F(n-1) + F(n-2) (n=3)

这是递归写法，但是会导致栈溢出。在计算机中，函数的调用是通过栈进行实现的，如果递归调用的次数过多，就会导致栈溢出。

针对这种情况就要使用方法二，改成非递归函数。

将递归进行改写，实现循环就不会导致栈溢出

Q2: Python该怎么入门?

作为初学者，第一个月的月目标应该是这样的：

熟悉基本概念（变量，条件，列表，循环，函数）

练习超过 30 个编程问题

利用这些概念完成两个项目

熟悉至少 2 个框架

开始使用集成开发环境（IDE），Github，hosting，services 等

整体计划

现在，我们先将月计划细化成周计划。

第一周：熟悉 Python

要积极探索 Python 的使用方法，尽可能多的完成下面这些任务：

第一天：基本概念（4 小时）：print，变量，输入，条件语句

第二天：基本概念（5 小时）：列表，for 循环，while 循环，函数，导入模块

第三天：简单编程问题（5 小时）：交换两个变量值，将摄氏度转换为华氏温度，求数字中各位数之和，判断某数是否为素数，生成随机数，删除列表中的重复项等等

第四天：中级编程问题（6 小时）：反转一个字符串（回文检测），计算最大公约数，合并两个有序数组，猜数字游戏，计算年龄等等

第五天：数据结构（6 小时）：栈，队列，字典，元组，树，链表。

第六天：面向对象编程（OOP）（6 小时）：对象，类，方法和构造函数，面向对象编程之继承

第七天：算法（6 小时）：搜索（线性和二分查找）、排序（冒泡排序、选择排序）、递归函数（阶乘、斐波那契数列）、时间复杂度（线性、二次和常量）

通过第一周时间，python大致能熟悉了，自学能力稍微弱一点找人带下你，节约自己的时间。

注意：别急着安装 Python 环境！

这看起来很矛盾，但是你一定要相信我。我有几个朋友，他们因为语言工具包和 IDE 安装的失败而逐渐失去了学习下去的欲望。因此，我的建议是先使用一些安卓 app 来探索这门语言，如果你是个技术小白，安装 Python 环境可不是你的首要任务。

第二周：开始软件开发（构建项目）

接下来，让我们朝着软件开发任务进军吧！不妨尝试综合你学到的知识完成一个实际的项目：

第一天：熟悉一种 IDE（5 小时）: IDE 是你在编写大型项目时的操作环境，所以你需要精通一个 IDE。在软件开发的初期，我建议你在 VS code 中安装 Python 扩展或使用 Jupyter notebook。

第二天：Github（6 小时）：探索 Github，并创建一个代码仓库。尝试提交（Commit）、查看变更（Diff）和上推（Push）你的代码。另外，还要学习如何利用分支工作，如何合并（merge）不同分支以及如何在一个项目中创建拉取请求（pull request）。

第三天：第一个项目——简单计算器（4 小时）：熟悉 Tkinter，创建一个简单的计算器

第四、五、六天：个人项目（每天 5 小时）：选定一个项目并完成它。如果你不知道你该做什么，可以查看下面的清单（ pythonprojects -for-an- middle - programmer/answer/jhankar - mahbub2）

第七天：托管项目（5 小时）：学习使用服务器和 hosting 服务来托管你的项目。创建一个 Heroku 设置并部署你构建的应用程序。

为什么要写项目？

如果仅仅按部就班地学习课堂上或视频中的内容，你无法拥有独立思考能力。所以，你必须把你的知识应用到一个项目中。当你努力寻找答案时，你也在慢慢地学会这些知识。

第三周：让自己成为一名程序员

第 3 周的目标是熟悉软件开发的整体过程。你不需要掌握所有的知识，但是你应该知道一些常识，因为它们会影响你的日常工作。

第一天：数据库基础（6 小时）：基本 SQL 查询（创建表、选择、Where 查询、更新）、SQL 函数（Avg、Max、Count）、关系数据库（规范化）、内连接、外连接等

第二天：使用 Python 数据库（5 小时）：利用一种数据库框架（SQLite 或 panda），连接到一个数据库，在多个表中创建并插入数据，再从表中读取数据。

第三天：API（5 小时）：如何调用 API。学习 JSON、微服务（micro-service）以及表现层应用程序转换应用程序接口（Rest API）。

第四天：Numpy（4 小时）：熟悉 Numpy（- Numpy -for- datascies-beginners-b8088722309f）并练习前 30 个 Numpy 习题（- 100/blob/master/100_numpy_excercises.md)

第五、六天：作品集网站（一天 5 小时）：学习 Django，使用 Django 构建一个作品集网站（- start-with-django -1/），也要了解一下 Flask 框架。

第七天：单元测试、日志、调试（5 小时）：学习单元测试（PyTest），如何设置和查看日志，以及使用断点调试。

真心话时间（绝密）

如果你非常「疯狂」，并且非常专注，你可以在一个月内完成这些任务。你必须做到：

把学习 Python 作为你的全职活动。你需要从早上 8 点开始学习，一直到下午 5 点。在此期间，你可以有一个午休时间和茶歇时间（共 1 小时）。

8 点列出你今天要学的东西，然后花一个小时复习和练习你昨天学过的东西。

从 9 点到 12 点：开始学习，并进行少量练习。在午饭后，你需要加大练习量，如果你卡在某个问题上，可以在网上搜索解决方案。

严格保持每天 4-5 小时的学习时间和 2-3 小时的练习时间（每周最多可以休息一天）。

你的朋友可能会认为你疯了。走自己的路，让别人去说吧！

如果你有一份全职工作，或者你是一名学生，完成这些流程可能需要更长的时间。作为一名全日制学生，我花了 8 个月的时间来完成这份清单。现在我是一名高级开发人员。所以，不管花多长时间，一定要完成它们。要想成功完成一个目标，必须付出百分之百的努力。

第四周：认真考虑工作（实习）问题

第 4 周的目标是认真思考如何才能被录用。即使你现在不想找工作，你也可以在探索这条道路的过程中学到很多东西。

第一天：准备简历（5 小时）：制作一份一页的简历。把你的技能总结放在最上面，必须在写项目的同时附上 Github 链接。

第二天：作品集网站（6 小时）：写几个博客，将它们添加到你之前开发的作品集网站中。

第三天：LinkedIn 简介（4 小时）：创建一个 LinkedIn 个人简介，把简历上的所有内容都放到 LinkedIn 上。

第四天：面试准备（7 小时）：准备一些谷歌常见的面试问题，练习白皮书中的 10 个面试编程问题。在 Glassdoor、Careercup 等网站中查看前人遇到的面试问题。

第五天：社交（~小时）：走出房门，开始参加聚会、招聘会，与其他开发人员和招聘人员见面。

第六天：工作申请（~小时）：搜索「Python Job」，查看 LinkedIn Job 和本地求职网站。选择 3 个工作岗位并发送工作申请。为每个工作定制你的简历。在每个工作要求中找出 2 到 3 件你不知道的事情，并在接下来的 3-4 天里学会它们。

第七天：在拒绝中学习（~小时）：每次你被拒绝的时候，找出两件为了获得这份工作你应该知道的事情，然后花 4-5 天 的时间来掌握它们。这样，每次拒绝都会让你成为更好的开发人员。