【Python学习之四】递归与尾递归

　　看完廖雪峰老师的教程，感觉尾递归函数是一个相对难点。于是复习一下，思考了一下，发表一些见解，记录一下。

1、递归函数

　　在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。　例如，阶乘的实现：f(n) = n! = 1x2x3x4......xn = f(n-1) x n。因此，f(n)用递归函数写出来是：

def f(n):

    if n == :

        return

    return f(n - ) * n

　　f(5)的计算过程如下：

===> f()

===>  * f()

===>  * ( * f())

===>  * ( * ( * f()))

===>  * ( * ( * ( * f())))

===>  * ( * ( * ( * )))

===>  * ( * ( * ))

===>  * ( * )

===>  *

===>

　　递归函数可以把复杂的循环，写成逻辑上容易理解的结构。但是，使用递归函数需要注意防止栈溢出。递归对系统内存的消耗是很大的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。于是，为了解决这个问题，提出了尾递归的概念。

2、尾递归函数

　　尾递归是指，在函数返回的时候，return语句不能包含表达式（含加减乘除等操作），只能是递归调用。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。下面是一个示例：

def f(n):

    return fact_iter(n, 1)    # 返回的是另一个递归调用函数的结果

def fact_iter(num, product):    # num是想要计算的值，product是结果

    if num == 1:

        return product

    return fact_iter(num - 1, num * product)    # 将乘积结果传入函数

　　比较递归函数和尾递归函数，很明显的是递归函数f(n)中 return f(n - 1) * n 是一个乘法表达式，不是递归调用函数。而fact_iter(num, product)函数则不一样， return fact_iter(num - 1, num * product) 是递归调用。f(5)对应的函数fact_iter(5, 1)计算过程:

===> fact_iter(5, 1)

===> fact_iter(4, 5)

===> fact_iter(3, 20)

===> fact_iter(2, 60)

===> fact_iter(1, 120)

===> 120

　　但是Python解释器没对尾递归做优化。

　　最后，汉诺塔的移动，使用递归算法，可以实现一下。我的实现如下：

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# @Date    : 2018-05-22 16:22:13

# @Author  : Chen Jing (cjvaely@foxmail.com)

# @Link    : https://github.com/Cjvaely

# @Version : $Id$

# 汉诺塔的移动可以用递归函数非常简单地实现

# 需求：打印出把所有盘子从A借助B移动到C的方法

def move(n, a, b, c):

    if n == 1:

        print(a, '-->', c)

    else:

        move(n - 1, a, c, b)

        move(1, a, b, c)

        move(n - 1, b, a, c)

        # 期待输出:

        # A --> C

        # A --> B

        # C --> B

        # A --> C

        # B --> A

        # B --> C

        # A --> C

move(3, 'A', 'B', 'C')

巴特西

【Python学习之四】递归与尾递归

1、递归函数

2、尾递归函数

最新文章

热门文章