【Day11】- 递回Recursion

递回(Recursion)的概念是将一个大的问题,分割成许多小问题去解决。而从程序设计角度来看,函式不单只能被其他函式呼叫,也能被它自己呼叫,也就是在一个函式当中呼叫它自己,即为递回函式(Recursive Function)。


例如:
要做一个5的阶乘: 5!

5 x 4 x 3 x 2 x 1

def factorial(n):
    if n == 1:  
        return 1
    else:
        return (n * factorial(n - 1))
print(factorial(5))#120

执行过程为下图
https://ithelp.ithome.com.tw/upload/images/20210922/20121027nwuXjcARyP.jpg


而递回函式通常需要有两项条件,一项是重复执行它自己另一项则是跳出执行的出口,避免造成无穷回圈

能够使用递回函式,是因为函式堆叠(Stack)的特性,当函式呼叫另一个函式时,需等候里面的函式执行完,才会继续回来执行自己的函式内容,应用到堆叠(Stack)资料结构後进先出(LIFO)的概念。

堆叠的介绍可以参考此篇

def first():
    print('1')
    last()
    print('2')

def last():
    print('3')

print(first()) #1>3>2

费波那契数列(Fibonacci Sequence)

又称费氏数列,是最有名的递回例子,里面隐藏了黄金比例法则,详细介绍如下影片:

影片来源

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

第0项值是0,第1项值是1,其他值会等於本身前两项的值相加,因此公式可以定义为:
F(0) = 0
F(1) = 1
F(n ) = F( n-1 ) + F( n-2 )

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

https://ithelp.ithome.com.tw/upload/images/20210922/20121027gIMrN89S88.jpg

之所以先在这边提到递回,是因为後面有许多实作会应用到递回函式。


<<:  【Day 07】欢迎来到实力至上主义的 Shellcode (上) - Windows x86 Shellcode

>>:  IT 铁人赛 k8s 入门30天 -- day8 Demo Project: MongoDB and MongoExpress

Spring Framework X Kotlin Day 27 Kubernetes

GitHub Repo https://github.com/b2etw/Spring-Kotlin...

Day 18-制作购物车系统之产品架构与描述

今天要输入购物网站中有卖的产品 以下内容有参考教学影片,底下有附网址。 (内容包括我的不专业解说分析...

【左京淳的JAVA学习笔记】第一章 JAVA基础

阿姆斯壮的一小步-准备好装备 在网路上搜寻、下载并安装好最新的JDK(JAVA编辑器套装) 设定系统...

javascript HTML DOM2

现在我们来运用HTML DOM来做选单开合的功能,点第一下关闭选单,点第二下选单又会回来。 ...

[Day 22] 实作 Database Plugin 整合 Exposed ORM, HikariCP 及 Flyway

Java Web 框架通常都至少整合一种 ORM,只要 Gradle depenency 加一下,再...