CAAD.XYZ

focus on computer-based architectural design

递归算法(二)

10 June 2020

To iterate is human,to recurse divine.—— L. Peter Deutsch

递归: 是指在函数的定义中使用函数自身的方法.

spiracl

递归经典案例

阶乘
阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是数学术语。 一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。1808年,基斯顿·卡曼引进这个表示法。 亦即n!=1×2×3×…×(n-1)×n。阶乘亦可以递归方式定义:0!=1,n!=(n-1)!×n。

"""
n!=n*(n-1)*(n-2)...1
为了求f(n)=n!, 根据递归定义我们也可以设定 f(n)=n*f(n-1), 在知道了f(0)=1 的情况下我们就可以递归出f(n)
"""
def factorial(n):
    if n is 0:
        return 1
    else:
        return n*factorial(n-1)

斐波那契数列
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*) fibonacci

"""
# 0  1
# 1  1
# 2  1 =0+1
# 3  2 =1+1
# 4  3 =1+2
# 5  5 =2+3
"""
def fibonacci(n):
    if n > 1 :
        return  fibonacci(n-1)+fibonacci(n-2)
    elif n==1:
        return 1
    elif n == 0:
        return 0

汉诺塔

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽

hanoi

"""
有三根杆子 A,B,C。A 杆上有 N 个穿孔圆盘,盘的尺寸由上到下依次变大,B,C 杆为空。
要求按下列规则将所有圆盘移至 C 杆: 每次只能移动一个圆盘; 大盘不能叠在小盘上面。
首先看下基本情况,即终止条件:N=1 时,直接从 A 移到 C。
再来看下通用情况:当有 N-1 个圆盘在 A 上,我们已经找到办法将其移到 C 杠上了.
我们怎么移动 N 个圆盘到 C 杠上呢?很简单,我们首先用将 N-1 个圆盘移动到 C 上的方法将 N 个圆盘都移动到 B 上,
然后再把第 N 个圆盘(最后一个)移动到 C 上,再用同样的方法将在 B 杠上的 N-1 个圆盘移动到 C 上,问题解决。
"""
i = 0
def hanoi(n, columnFrom="A", columnBuffer="B",columnTo="C"):
    global i
    if n==1:
        i+=1
        print columnFrom+"->"+columnTo ,
    else:
        hanoi(n-1,columnFrom,columnTo,columnBuffer)
        hanoi(1,columnFrom,columnBuffer,columnTo)
        hanoi(n-1,columnBuffer,columnFrom,columnTo)
hanoi(8)
print i

A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B C->A B->C B->A C->A C->B A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C B->A C->A C->B A->B C->A B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B C->A B->C B->A C->A C->B A->B A->C B->C A->B C->A C->B A->B C->A B->C B->A C->A B->C A->B A->C B->C B->A C->A C->B A->B C->A B->C B->A C->A C->B A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B C->A B->C B->A C->A C->B A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C B->A C->A C->B A->B C->A B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C B->A C->A C->B A->B C->A B->C B->A C->A C->B A->B A->C B->C A->B C->A C->B A->B C->A B->C B->A C->A B->C A->B A->C B->C B->A C->A C->B A->B C->A B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B C->A B->C B->A C->A C->B A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C B->A C->A C->B A->B C->A B->C B->A C->A B->C A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C 255

在GenerativeArt或Design中如何使用递归

Generative Art or Design是指全部或部分使用自主系统进行创作的艺术或设计。
这里所说的自主系统一般是指非人类的系统,它可以独立地决定作品的特征. 在某些情况下,人类创作者可能会声称,生成系统代表了他们自己的理念.
“生成艺术或设计”通常指的是算法(由算法决定的计算机生成的作品)

以下列举几个递归算法相关作品:

Justin Windle, a Creative Developer from London
github: https://github.com/soulwire

gt01 Recursion Toy

gt02 Mushroom Coral

Subdivision / Michael Hansmeyer “一方面,计算能力可以处理规模和复杂度超过人工方法的过程。另一方面,算法可以产生无穷无尽的概念方案的组合。只要对输入或过程稍作调整,就可以立即调整输出。当与评估函数相结合时,它们可以用来在功能和美学层面上递归优化输出,” —-Hansmeyer
colomns6

holger lippmann
形式和行为的数学可视化对算法结构的影响,是我工作的基本重点。 对我来说,它提供了一种看待/进入大自然的元层次。

circulation III (2019) circulation3

the spinners day (2), 2010
theSpinnerDay

Reference

  • L Peter Deutsch: The founder of Aladdin Enterprises and creator of Ghostscript, a free software PostScript and Portable Document Format interpreter. Deutsch’s other work includes the Smalltalk implementation that inspired Java just-in-time compilation technology about 15 years later.

相关文章

建筑师编程课推广

ikuku精选课 Python4Rhino 建筑师编程课 2020.5.16开始线上直播!讲师:马海东

python tutorial

Python4Rhino递归案例1
spiracl spiracl spiracl

Python4Rhino递归案例2
spiracl


Comments

    No comments found for this article.

    Join the discussion for this article on this ticket. Comments appear on this page instantly.