人理解迭代 神理解递归

To iterate is human, to recurse, divine.

什么意思啊？

人理解迭代 神理解递归

？，不明觉厉

其实就是一个逻辑思维上的改变，经常在编程问题中遇到~

迭代这个词生活中也能遇到，递归就数学和计算机科学能遇到了吧

还真是这样！这说明迭代思维更接近人的思维。

那这俩什么区别，又是干啥的呢？

01

连环扣是迭代 俄罗斯套娃是递归

迭代每次需要把上一次的输出作为本次工作的输入，比如流水线上的工作，比如改了一次又一次的论文，每个工作是紧密相扣的，因此很像是连环扣。

环再多再乱也就是迭代N次的问题

俄罗斯套娃 第50下就停（狗头）

递归工作每次都要调用自己，包含自己。每个中国孩子儿时都会听过这样的故事：从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山...

咳咳，你要是问我什么时候故事可以讲完，那只有两种情况，一是你睡着了，在梦里就讲完了；二是真的有不在讲故事的故事。

所以说递归的概念本来就绕， 要理解递归，就得先了解什么是递归，这句话本身就是递归，所以你懂什么是递归了嘛。

02

渐进上升VS自顶向下

我们都知道做事情往往思路有很多，有的时候我们找到一个突破口不断挖掘，不断扩大，最终得到胜利的全貌，譬如开采，这种思路是往往是渐进上升的（或者叫自底向上）；而有的时候，我们需要从一个整体出发，不断向下延伸，最终接触到事物本质，譬如扶贫，这种思路基本都是自顶向下。目前还没有从过程中横插一刀的思路，这样既不接地气也不能把握顶层设计。

从这个思路来说，我们经常会遇到两种PPT图表，它们就很好反映了迭代和递归的思路，也就是渐进上升和自顶向下。

每个人都希望自己的人生像这样一样

又希望自己都位于树的顶端

03

谁都可以替代 谁都不可替代

递归和迭代不是一个互斥的概念，一件事情如果可以通过递归完成，那他同样可以通过迭代完成，反之同理。如果从这个角度来说标题那句话，大概意思是对于神学信仰者：神创造了人，对于唯物论学者：人创造了神。

每种理论在其特定的领域发挥着不可取代的作用，如果把递归换成迭代，可能事情就乱杂无章，一团乱麻；如果把迭代换成递归，可能事情就会无从下手，难以落地，开展不了。

至于选择哪一个嘛，递归需要考虑临时临时存放上层建筑的空间，递归嘛需要考虑优先摸清未来上层建筑的结构……

04

计算机编程里的递归迭代

先看数学问题，再看计算机问题：

斐波那契数列列问题：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)。

如果要求F(n)，n此时为具体值，两个办法，算通项公式，或者，按照F(n)=F(n-1)+F(n-2)穷尽。

计算机通常处理此类问题用的方法就是递归。

# pythondef fib(x): if x < 2: return 0 if x == 0 else 1 # 当x > 2时，开始递归调用fib()函数: return fib(x - 1) + fib(x - 2)
print(fib(6)) # 打印结果为:8

        在计算机科学中，最为常见的文件目录问题，是一个典型的树形结构，如果要对整个大文件下面所有文件进行处理，递归的作用就无处不在了。

        下面的代码是将根目录下所有文件名输出出来。

# python# linuximport os
def file_display(filepath): for each in os.listdir(filepath): # 得到文件的绝对路径: absolute_path = os.path.join(filepath， each) # 得到是否为文件还是目录的布尔值: is_file = os.path.isfile(absolute_path) if is_file: # 当前的绝对路径为文件: print(each) else: # 当前的绝对路径为目录: file_display(absolute_path)
file_display('/')

        XML格式文件，是一个典型的以树状结构储存数据的文件格式，利用递归可以轻松地将xml转换为字典或者json文件格式，下面给出了一个针对某特殊xml以递归方式写的函数。

# python import xml.etree.cElementTree as ET
def xml_dic(file_path):    tree = ET.ElementTree(file=file_path)    root = tree.getroot()    def getchildrenlist(node):     temp_list = []        temp_list.append(node.attrib)        for child in node:            temp_list.append(child.attrib)            children = child.getchildren()            if len(children)>0:                temp_list.append({child.tag:getchildrenlist(child)})        return temp_list    result_dic = {}    temp_list = []    for child in root:        temp_list.append(child.attrib)        children = child.getchildren()        if len(children)>0:         temp_list.append({child.tag:getchildrenlist(child)})    result_dic[root.tag] = temp_list    return result_dic    

点击蓝字关注我们