《零基础入门学习Python》第022讲：函数：递归是神马

短命女 2022-04-16 04:49 206阅读 0赞

**目录**

测试题

0. 递归在编程上的形式是如何表现的呢？

1. 递归必须满足哪两个基本条件？

2. 思考一下，按照递归的特性，在编程中有没有不得不使用递归的情况？

3. 用递归去计算阶乘问题或斐波那契数列是很糟糕的算法，你知道为什么吗？

4. 请聊一聊递归的优缺点（无需官方陈词，想到什么写什么就可以）

5. 拿手机拍一张“递归自拍照片”

动动手

0. 使用递归编写一个 power() 函数模拟内建函数 pow()，即 power(x, y) 为计算并返回 x 的 y 次幂的值。

1. 使用递归编写一个函数，利用欧几里得算法求最大公约数，例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。

3. 请写下这一节课你学习到的内容：格式不限，回忆并复述是加强记忆的好方式！

--------------------

# **测试题** #

## 0. 递归在编程上的形式是如何表现的呢？ ##

答：在编程上，递归表现为函数调用本身这么一个行为。  
  
举个例子（递归求阶乘）：

def factorial(n):
        if n == 1:
            return 1
        else:
            return n * factorial(n-1)
    
    number = int(input('请输入一个整数：'))
    result = factorial(number)
    
    print("%d的阶乘是：%d" % (number, result))

## 1. 递归必须满足哪两个基本条件？ ##

答：一、函数调用自身  
  
      二、设置了正确的返回条件

## 2. 思考一下，按照递归的特性，在编程中有没有不得不使用递归的情况？ ##

答：例如汉诺塔，目录索引（因为你永远不知道这个目录里边是否还有目录），快速排序（二十世纪十大算法之一），树结构的定义等如果使用递归，会事半功倍，否则会导致程序无法实现或相当难以理解。

## 3. 用递归去计算阶乘问题或斐波那契数列是很糟糕的算法，你知道为什么吗？ ##

答：小甲鱼在课程的开头说“普通程序员用迭代，天才程序员用递归”这句话是不无道理的。  
  
但是你不要理解错了，不是说会使用递归，把所有能迭代的东西用递归来代替就是“天才程序员”了，恰好相反，如果你真的这么做的话，那你就是“乌龟程序员”啦。  
  
为什么这么说呢？不要忘了，递归的实现可以是函数自个儿调用自个儿，每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈操作，所以在这上边是非常消耗时间和空间的。  
  
另外，如果递归一旦忘记了返回，或者错误的设置了返回条件，那么执行这样的递归代码就会变成一个无底洞：只进不出！所以在写递归代码的时候，千万要记住口诀：递归递归，归去来兮！出来混，总有一天是要还的！

## 4. 请聊一聊递归的优缺点（无需官方陈词，想到什么写什么就可以） ##

优点：  
  
1）递归的基本思想是把规模大的问题转变成规模小的问题组合，从而简化问题的解决难度（例如汉诺塔游戏）。  
  
2）有些问题使用递归使得代码简洁易懂（例如你可以很容易的写出前中后序的二叉树遍历的递归算法，但如果要写出相应的非递归算法就不是初学者可以做到的了。）  
  
缺点：  
  
1）由于递归的原理是函数调用自个儿，所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”（当然法拉利也奢侈，但还是很多人趋之若鹜）。  
  
2）初学者很容易错误的设置了返回条件，导致递归代码无休止调用，最终栈溢出，程序崩溃。

## 5. 拿手机拍一张“递归自拍照片” ##

![1459595zggbg7zzbeieoe7.jpg][]

--------------------

# **动动手** #

## 0. 使用递归编写一个 power() 函数模拟内建函数 pow()，即 power(x, y) 为计算并返回 x 的 y 次幂的值。 ##

def power(x, y):
        if y:
            return x * power(x, y-1)
        else:
            return 1
        
    print(power(2, 3))

## 1. 使用递归编写一个函数，利用欧几里得算法求最大公约数，例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。 ##

def gcd(x, y):
        if y:
            return gcd(y, x%y)
        else:
            return x
        
    print(gcd(4, 6))

## 3. 请写下这一节课你学习到的内容：格式不限，回忆并复述是加强记忆的好方式！ ##

（1）什么时候递归

有调用函数自身的行为

有正确的返回条件

（2）递归求阶乘

写一个求阶乘的函数：

首先看不用递归的程序：

def factorial(n):
    	if n ==0 or n == 1:
    		result = 1
    		return result
    	else:
    		result = n
    		for i in range(1,n):
    			result *= i
    		return result

然后使用递归实现：

def factorial(n):
    	if n == 1 or n == 0:
    		return 1
    	else:
    		return n * factorial(n-1)

[1459595zggbg7zzbeieoe7.jpg]: /images/20220416/28a0c57dfd97481791ca9dbd4f4e138d.png