我們都知道任何正整數都可以分解為質因數之乘積，稱為質因數分解。同樣的，任何正整數也都可以分解為「相異的費波那契數之和」，而且可能有多種組合，每種組合的費波那契數都不同。例如：

101 = F(1) + F(4) + F(6) + F(11)

之前提過，費波那契數的密度比質數低很多，到19位整數也不過92個費波那契數。19位整數相當於10億的10億倍，這麼多數字裡面只有92個費波那契數，可見之稀少，但卻只要這92個費波那契數，就能夠組合出10億的10億倍的數字，不由得讓人吃驚。所以老子說：「道生一，一生二，二生三，三生萬物」，的確很有道理。

我們用程式來驗證一下，看任意整數是否都能分解為相異費波那契數之和。

// 1-6a 整數分解（費波那契數之和）
// Created by Heman, 2021/07/22
var 數列 = [0, 1]
var 最大索引 = 1

func 費氏數列(_ n: Int) -> Int {
    if n < 0 { return -1 }
    if n <= 最大索引 {
        return 數列[n]
    }
    let m = 最大索引 + 1
    for i in m...n {
        let 下一個 = 數列[i-1] + 數列[i-2]
        數列 = 數列 + [下一個]
    }
    最大索引 = n
    return 數列[n]
}

func 整數分解(_ n: Int) -> [Int] {
    var 數列: [Int] = []
    var 索引 = 0
    if n <= 0 { return [] }
    while 費氏數列(索引) < n {
        索引 = 索引 + 1
    }
    if 費氏數列(索引) == n { return [n] }
    let 最近費數 = 費氏數列(索引-1)
    let 差值 = n - 最近費數
    數列 = 整數分解(差值) + [最近費數]
    return 數列
}

print(整數分解(2021))

利用上一課1-5c的「費氏數列()」函式，我們只需要再增加一個函式「整數分解(n)」，傳回n分解為費波那契數的數列。

基本的想法很直覺，就是先找到最接近（但小於或等於）參數n的費波那契數，這用一個 while 迴圈句就能搞定。

    while 費氏數列(索引) < n {
        索引 = 索引 + 1
    }

當脫離迴圈時，「索引」所指的費波那契數會大於或等於n。接下來用一個條件句：

    if 費氏數列(索引) == n { return [n] }

如果n剛好是費波那契數，直接命中，那就傳回 [n] 這個小陣列，不用再加別的費波那契數了。否則的話：

    let 最近費數 = 費氏數列(索引-1)
    let 差值 = n - 最近費數
    數列 = 整數分解(差值) + [最近費數]

最接近的費波那契數應該是「索引-1」的那個數，這樣就找到數列的最後一個元素了。然後將差值再傳入「整數分解(差值) 」函式中，傳回結果再與前次找到的最後一個元素的陣列，相加（陣列合併）在一起。

這裡函式有個特殊的用法，就是在函式的宣告裡面呼叫自己，像這樣：

func 整數分解(_ n: Int) -> [Int] {
    ....
    整數分解(差值)
    ....
}

這叫做「遞迴」呼叫(Recursive call)，有點像佛教裡的輪迴，呼叫上一輩子的自己，問他上輩子的事情。以上面程式中「整數分解(2021)」為例，遞迴的過程如下圖所示。