python3 递归

最近写代码遇到一个问题：在 python 中，编写一个函数，在该函数内 有 for 循环，在for循环下 继续调用自身函数。

先复习一下递归

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

递归函数有一些特性：

1. 必须有一个明确的结束条件；
2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
3. 相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
4. 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

# 这是一个计算阶乘的例子 
# n! = 1 x 2 x 3 x ... x n
def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)

这个例子都是学习编程中已经很熟悉的了。

下面是遇到一个问题：从 开始 节点（红色） 寻找 特点 这个节点
如图

graph

一开始是这样写的，得到结果是打印出来 找到了 这句话，但是返回回来却是 None。

# recursion to get label node
def recursion_search_node(self,start,label):
    '''
        recursion to get sepecified label node
        start : Node to start to crawl
        label : specified label
    '''
    for x in self.graph.match((start,)):
        print(x)
        if x.end_node['name'] == label:
            print("wowowowow 找到了 wowowow")
            print(x.end_node)
            return  x.end_node
        else:
            return self.recursion_search_node(x.end_node,label,y)

后来在网上查询了许久，或许根本没人这样去写递归，或许别人有更好的方法去获取到结果。

终于在一个 stackoverflow 找到一个帖子谈到这个问题，是因为每次调用函数 返回给上一层，需要用一个 变量来接收结果。

于是乎，就有了下面的代码

    # recursion to get label node
    def recursion_search_node(self,start,label,y=None):
        '''
            recursion to get sepecified label node
            start : Node to start to crawl
            label : specified label
            
        '''
        for x in self.graph.match((start,)):
            print(x)
            if x.end_node['name'] == label:
                print("wowowowow 找到了 wowowow")
                print(x.end_node)
                y =  x.end_node
                return y
            else:
                y = self.recursion_search_node(x.end_node,label,y)
        return y

多加了一个参数 y, 这个y 是可以想象是当作在函数调用之间的一个桥梁，一个共享对象。

参考资料：

1. https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431756044276a15558a759ec43de8e30eb0ed169fb11000
2. https://stackoverflow.com/questions/47740347/recursive-function-with-for-loop-in-python