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)穷尽。
计算机通常处理此类问题用的方法就是递归。
# python
def 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
# linux
import 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
联系客服