迴圈轉遞迴（稿）-文字檔
- import "@preview/algo:0.3.3": *
- set par(
justify: true, leading: 1em,
)
- let CJKNonCJKSpacing = 0.2em
- let RegExCJK = "[\p{Han}\p{Hiragana}\p{Katakana}\p{Hangul}\p{Bopomofo}]"
- let RegExNonCJK = "[^\p{Han}\p{Hiragana}\p{Katakana}\p{Hangul}\p{Bopomofo}]"
- let RegExNonCJK = "[^\p{Han}\p{Hiragana}\p{Katakana}\p{Hangul}\p{Bopomofo}]"
- show regex(RegExCJK+RegExNonCJK) : it => {
text[#it.text.first()#box(width: CJKNonCJKSpacing,"")#it.text.last()]
}
- show regex(RegExNonCJK+RegExCJK) : it => {
text[#it.text.first()#box(width: CJKNonCJKSpacing,"")#it.text.last()]
}
- set page(
numbering: "1 / 1",
)
- set text(
size: 12pt,
font: ("Linux Libertine", "Noto Serif CJK TC"),// "Linux Libertine Mono O"
)
- let hd1(txt) = box[
#set text(
font: ("FreeSans", "Noto Sans CJK TC"),// "Linux Libertine Mono O"
)
= #txt ]
- let hd2(txt) = box[
#set text(
font: ("FreeSans", "Noto Sans CJK TC"),// "Linux Libertine Mono O"
)
== #txt ]
- let remark(txt, number) = box(width:100%,
fill: rgb("#EBFAEF"), [
- v(1em)
- align(center,[#txt~~#sub(#number)])
- v(1em)])
- hd1("迴圈轉遞迴（稿）")
_2023-07-20 by Yoxem_（2024-10-05：修正發佈日期）
迴圈和遞迴其實習習相關，最近略讀論文 _Transforming Programs into Recursive Functions_ (Myreen & Gordon, 2008)，提到迴圈如何轉換成遞迴的方法。我在這邊想到一些思路。
一個迴圈可以理解為條件(cond)和滿足條件即執行的程式本體(body)，即： ```python while (cond):
body
```
其中一些while外的變數，被body處理之後，在body的最後就會變。假設輸入到body改變數值的變數為$x_i space (i=0, 1,dots)$，輸出的結果是$x^prime_i$，那我們可以假設$bold(accent(x,->))$是$x_i$組成的向量，$bold(accent(x,->)^prime)$是是$x^prime_i$組成的向量，則body可以視為函數，且$bold(accent(x,->)^prime) = "body"(bold(accent(x,->)))$。
舉下列求除法商數的$"Quotient"(a, b) = a$除以$b$的商數"為例，為求簡化，$a, b$均為自然數：
- algo(
title: "Quotient",
parameters: ("a","b"),
strong-keywords: true // display keywords in bold
)[
let q = 0 #comment[商數] \ while $a gt.eq b$:#i#comment[cond]\ // $a <- a - b$ #comment[body的第1行]\ $ q <- q + 1$ #comment[body的第2行]:#d\
return q ]
其中 $a, b$ 和 $q$ 是body外的變數，$"body"(a, b, q)$ $= (a-b, b, q+1)$，比較下，$bold(accent(x,->)) = (a, b, q)$，$bold(accent(x,->)^prime) = (a-b, b, q+1)$然後可以把`while(cond){body}`組合$bold(accent(x,->))$想成這樣的OCaml函數：
```ML (* 以下括號非必要則略 *) WHILE cond body XVec= if cond then
let NewXVec = body XVec in (* NewXVec = body XVec *) WHILE cond body NewXVec (* 帶 NewXVec 重新進去WHILE函數，做if判斷的手續 *)
else
XVec (* XVec 不變 *)
```
另可以這樣改寫，其中cond視為輸入$bold(accent(x,->))$的函數：
```ML let WHILE cond body XVec = if (cond XVec) then
WHILE cond (body XVec)
else
XVec
```
那麼這個除法可以這樣寫成類OCaml風格：
```ML ……
let q = 0 in (*原樣*) while a >= b do
let a = a - b let q = q + 1
``` 但是要找出while外變數，可以找出a, b, q，且把狀態更新改為 let…in 模式，則 ```ML ……
let q = 0 in
let cond = fun a b q -> a >= b in WHILE cond
(fun a b q ->(
let a = b - a in
let q = q + 1 in
(WHILE cond [a; b; q] )))
a b q (* XVec*)
```
用let的規約規則轉換一下變成尾遞迴
```ML ……
let q = 0 in
let cond = fun a b q -> a >= b in WHILE cond
(fun a b q ->(
(WHILE cond [b - a; b; q + 1] )))
a, b, q
```
最後修改：
```ML ……
let cond = fun a b q -> a >= b in letrec WHILE cond =
(if (cond X) then (WHILE cond (b - a) b (q + 1)) else [a; b; q]) in
WHILE cond a b q (* 執行 LOOP *) ```