可能存在无限递归_深刻理解递归——从底层存储（栈图）来理解

布满荆棘的人生 2023-01-06 11:57 181阅读 0赞

函数调用另外一个函数是合法的；函数调用自己也是合法的。调用自己的过程称为**递归函数**，这个执行过程叫做**递归**。

递归在数据结构中经常会用到，特别是解决树的递归问题时很好用。但是想明白递归是挺烧脑的，一般即使两层、三层递归也会容易给人绕进去。要是我们了解函数在底层的存储机制，利用栈（先进后出）来进行分析，或许就容易多了。

不讲废话，直接捞干的，我们首先回忆下递归的规则，

## 函数递归调用的重要规则 ##

1) 程序执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)

2) 函数的局部变量是独立的，不会相互影响

3) 递归必须向退出递归的条件逼近，否则就是无限递归，死龟了:)

4) 当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁。

## 分析递归流程 ##

我们一个例子来快速熟悉递归：

> 求函数值：  
> 已知 f(1)=3; f(n) = 2\*f(n-1)+1; 请使用递归的思想编程，求出f(n)的值.

### 编写程序 ###

# coding=utf-8
    # -*- coding:utf-8 -*-
    '''
    Author: Solorzhou
    Email: t-zhou@foxmail.com
    
    date: 2019/10/26 20:13
    desc:
    '''
    
    def f(n):
        if n == 1:
            return 3
        else:
            return 2 * f(n - 1) + 1
            print("n=", n)
    
    
    if __name__ == '__main__':
        f(4)

### 递归函数的栈图 ###

![238da40d61bbbd274df3e28c142420d0.png][]

可以看到，一个函数每次被调用时，都会在内存中创建一个帧，来包含函数的局部变量和参数，对于递归函数，栈上可能同时存在多个函数帧。当每调用一次函数f(n)时，栈顶指针就会往栈顶移动一个位置，直到满足退出递归的条件（n==1）.之后再依次返回当前的结果直接，栈顶指针往下移动。

递归，也就是先“递”后“归”。

本题则是：

f(4)=2 * f(3) + 1
    f(4)=2 * (2 * f(2) + 1) + 1
    f(4)=2 * (2 * (2 * f(1) + 1) + 1) + 1
    f(4)=2 * (2 * (2 * 3 + 1) + 1) + 1
    f(4)=2 * 15 + 1
    f(4)=31

## 一些例子 ##

1.  斐波那契数列

> 请使用递归的方式，求出斐波那契数 1,1,2,3,5,8,13... 给你一个整数 n，求出它的斐波那契数是多少？

1.  猴子吃桃子问题

> 有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再 多吃一个。当到第十天时，想再吃时（还没吃），发现只有 1 个桃子了。问题：最初共多少个桃子？

这些递归问题，当我们使用栈图来思考时就容易多了。

## 坚定信念 ##

跟踪程序执行的流程是阅读程序的一个方法，但是这样很快就会陷入到迷宫境况。之前在一本书中看到作者对于递归给出了一种“坚定信念”的思想。在遇到一个程序时，不去跟踪执行的流程，而是假定函数都是正确工作的，都能够返回正确的结果。

事实上，在使用内置函数时，我们已经在尝试这样坚持信念了。如：当调用`math.cos`或者`math.exp`时，我们并不会去检查函数的内部实现。因为我们假定他是正确的，因为些内置函数的程序员肯定都很优秀。

当调用自己写的函数时，假定它也是正确的，不需要检查他的执行流程。看一个关于斐波那契数列的例子：

fibonacci(0) = 0
    fibonacci(1) = 1
    fibonacci(2) = fibonacci(0) +fibonacci(1)

翻译成python语言，看起来是这样：

def fibonacci(n):
        if n ==0:
            return 0
        elif n ==1:
            return 1
        else:
            return fibonacci(n-1) + fibonacci(n-2)

假定写的程序是正确的，那么很明显第三个数等于前两个数字之和。以上程序运行后肯定也是正确的。

从一名不羁的码农开始，谈风月之余谈技术

![da56a10df438e4ae5921a8b8c4ff0bb1.png][]

[238da40d61bbbd274df3e28c142420d0.png]: /images/20221119/3316dcaef0ae4dcfa557f8c6ef0a51cb.png
[da56a10df438e4ae5921a8b8c4ff0bb1.png]: https://img-blog.csdnimg.cn/img_convert/da56a10df438e4ae5921a8b8c4ff0bb1.png