如何將遞迴函數改成迭代函數？

遞迴(Recursive)函數是在執行的過程又會直接或間接地呼叫自己本身的函數。通常透過遞迴函數可以快速地驗證我們的演算法，用簡短的程式碼處理複雜的問題，但是函數在呼叫時需要建立新的堆疊框(Stack Frame)，除了會需要額外的開支(Overhead)之外，如果在函數中呼叫函數，而這函數又會呼叫函數，持續下去，很容易就會造成堆疊溢出(Stack Overflow)。雖然有些程式語言的編譯器會做尾端呼叫消除(Tail Call Elimination, TCE)的優化(Tail Call Optimization, TCO)，可以讓我們將遞迴函數設計成尾端遞迴(Tail Recursive)來避免分配額外的堆疊空間建立新的堆疊框，但編譯器其實並不能都保證一定會去進行尾端呼叫消除。遇到這種情形，我們還是只好使用迭代函數。那麼大問題就來了：要如何將遞迴函數改成迭代函數呢？

將遞迴函數改成迭代函數的流程

以下會以經典的費氏數列來說明將遞迴函數逐步改成迭代函數的流程。

費氏數列又稱費布那西(Fibonacci)數列，它是一種發散數列，第1項的值為0，第2項的值為1，第#{{n}}#項(#{{ n \geq 3 }}#)的值為第#{{n - 1}}#項和第#{{n - 2}}#項的總和。費氏數列看起來會長得像以下這樣：

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

以數學函數來表示費氏數列，可以寫成：

#{{{
\begin{eqnarray}
F(1) &=& 0 \nonumber \\
F(2) &=& 1 \nonumber \\
F(n) &=& F(n - 1) + F(n - 2), \text{where } n \geq 3 \nonumber \\
\end{eqnarray}
}}}#

有沒有清楚發現費氏數列函數在運算的時候又去呼叫自己本身的函數？所以它是一個遞迴函數。

步驟一：理解遞迴函數

要將遞迴函數改為迭代函數，我們要先理解這個函數的每個部份(或是至少遞迴呼叫的部份)在幹嘛。費氏數列很簡單，就不多說了。如果用程式碼來實作費氏數列，最直覺的方式會是以下這個樣子：

pub fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

public static int fibonacci(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

function fibonacci(n: number): number {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

func Fibonacci(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		return Fibonacci(n-1) + Fibonacci(n-2)
	}
}

由於寫程式習慣從0開始數，所以這邊將費氏數列的第一項設計為#{{ F(0) }}#。

步驟二：將遞迴函數改為尾端遞迴

函數被遞迴呼叫的位置若是在函數執行的最後，就是尾端遞迴。以上程式碼因為費氏數列函數在被遞迴呼叫後還多做了加法運算，所以不能算是尾端遞迴。我們要想辦法將它改成尾端遞迴，好讓我們能夠把它變成迭代函數。

我們可以增加遞迴函數的參數，讓函數在遞迴的時候帶走更多資訊。像是費氏數列，就可以讓遞迴函數多加兩個參數，來儲存每次遞迴時第#{{ n - 1 }}#項的值和第#{{ n }}#項的值。如此一來就可以在每次遞迴時計算出下一項的值，並將這個值又作為下一次遞迴呼叫時的第#{{ n }}#項的值，同時也將原本第#{{ n }}#項的值作為下一次第#{{ n - 1 }}#項的值。而原本的參數n就會變成計次用途了。

修改後的程式碼如下：

fn fibonacci_recursively(counter: u32, init: u32, accumulator: u32) -> u32 {
    if counter == 0 {
        init
    } else {
        fibonacci_recursively(counter - 1, accumulator, init + accumulator)
    }
}

pub fn fibonacci(n: u32) -> u32 {
    fibonacci_recursively(n, 0, 1)
}

static int fibonacciRecursively(final int counter, final int init, final int accumulator) {
    if (counter == 0) {
        return init;
    } else {
        return fibonacciRecursively(counter - 1, accumulator, init + accumulator);
    }
}

public static int fibonacci(final int n) {
    return fibonacciRecursively(n, 0, 1);
}

function fibonacciRecursively(counter: number, init: number, accumulator: number) {
    if (counter === 0) {
        return init;
    } else {
        return fibonacciRecursively(counter - 1, accumulator, init + accumulator);
    }
}

function fibonacci(n: number) {
    return fibonacciRecursively(n, 0, 1);
}

func fibonacciRecursively(counter int, init int, accumulator int) int {
	if counter == 0 {
		return init
	} else {
		return fibonacciRecursively(counter-1, accumulator, init+accumulator)
	}
}

func Fibonacci(n int) int {
	return fibonacciRecursively(n, 0, 1)
}

步驟三：用迴圈將遞迴函數的主體(Body)包起來

這是一個過渡性的步驟(程式碼不一定能編譯成功)，我們要用一個總是可以被執行的迴圈來將原本遞迴函數主體中的所有程式敘述包起來，並在迴圈中的最後加上break關鍵字來跳離迴圈。

所以上面的程式碼要修改成：

fn fibonacci_recursively(counter: u32, init: u32, accumulator: u32) -> u32 {
    loop {
        if counter == 0 {
            return init;
        } else {
            return fibonacci_recursively(counter - 1, accumulator, init + accumulator);
        }
        
        break;
    }
}

pub fn fibonacci(n: u32) -> u32 {
    fibonacci_recursively(n, 0, 1)
}

static int fibonacciRecursively(final int counter, final int init, final int accumulator) {
    while (true) {
        if (counter == 0) {
            return init;
        } else {
            return fibonacciRecursively(counter - 1, accumulator, init + accumulator);
        }

        break;
    }
}

public static int fibonacci(final int n) {
    return fibonacciRecursively(n, 0, 1);
}

function fibonacciRecursively(counter: number, init: number, accumulator: number) {
    for (; ;) {
        if (counter === 0) {
            return init;
        } else {
            return fibonacciRecursively(counter - 1, accumulator, init + accumulator);
        }

        break;
    }
}

function fibonacci(n: number) {
    return fibonacciRecursively(n, 0, 1);
}

func fibonacciRecursively(counter int, init int, accumulator int) int {
	for {
		if counter == 0 {
			return init
		} else {
			return fibonacciRecursively(counter-1, accumulator, init+accumulator)
		}

		break
	}
}

func Fibonacci(n int) int {
	return fibonacciRecursively(n, 0, 1)
}

步驟四：將尾端遞迴呼叫的程式敘述改為直接修改函數參數的敘述，並加上`continue`關鍵字

這也是一個過渡性的的步驟(程式碼不一定能編譯成功)，如果尾端遞迴呼叫的地方有需要回傳(return)尾端遞迴呼叫後的結果的話，就直接把那個「return」拿掉吧！

修改後的程式碼如下：

fn fibonacci_recursively(mut counter: u32, mut init: u32, mut accumulator: u32) -> u32 {
    loop {
        if counter == 0 {
            return init;
        } else {
            counter -= 1;

            let temp = accumulator;
            accumulator += init;

            init = temp;
            
            continue;
        }

        break;
    }
}

pub fn fibonacci(n: u32) -> u32 {
    fibonacci_recursively(n, 0, 1)
}

static int fibonacciRecursively(int counter, int init, int accumulator) {
    while (true) {
        if (counter == 0) {
            return init;
        } else {
            --counter;
            
            final int temp = accumulator;
            accumulator += init;
            
            init = temp;
            
            continue;
        }
        
        break;
    }
}

public static int fibonacci(final int n) {
    return fibonacciRecursively(n, 0, 1);
}

function fibonacciRecursively(counter: number, init: number, accumulator: number) {
    for (; ;) {
        if (counter === 0) {
            return init;
        } else {
            counter -= 1;

            const temp = accumulator;
            accumulator += init;

            init = temp;

            continue;
        }

        break;
    }
}

function fibonacci(n: number) {
    return fibonacciRecursively(n, 0, 1);
}

func fibonacciRecursively(counter int, init int, accumulator int) int {
	for {
		if counter == 0 {
			return init
		} else {
			counter--

			temp := accumulator
			accumulator += init

			init = temp

			continue
		}

		break
	}
}

func Fibonacci(n int) int {
	return fibonacciRecursively(n, 0, 1)
}

步驟五：整理程式碼

將以上被我們改到變得怪怪的程式碼稍微整理一下，讓它可以被正確編譯。

pub fn fibonacci(n: u32) -> u32 {
    let mut init = 0;
    let mut accumulator = 1;

    for _ in 0..n {
        let temp = accumulator;
        accumulator += init;

        init = temp;
    }

    init
}

public static int fibonacci(final int n) {
    int init = 0;
    int accumulator = 1;

    for (int counter = 0; counter < n; ++counter) {
        final int temp = accumulator;
        accumulator += init;

        init = temp;
    }

    return init;
}

function fibonacci(n: number) {
    let init = 0;
    let accumulator = 1;

    for (let counter = 0;counter < n;counter++) {
        const temp = accumulator;
        accumulator += init;

        init = temp;
    }

    return init;
}

func fibonacci(n int) int {
	init := 0
	accumulator := 1

	for counter := 0; counter < n; counter++ {
		temp := accumulator
		accumulator += init

		init = temp
	}

	return init
}

至此我們就成功地把遞迴的費氏數列函數改成迭代版本了！

更多的轉換例子

簡單的遞迴函數基本上都可以嘗試使用上面的流程來轉換成迭代函數，以下再舉幾個例子。

階乘(Factorial)函數

計算某數(正整數)的階乘，是指計算所有小於及等於該數的正整數的積。方程式表示如下：

#{{{
n! = 1 \times 2 \times 3 \times \dotsb \times (n - 1) \times n
}}}#

且定義

#{{{
0! = 1
}}}#

我們可以將階乘的第#{{ n }}#項移出，使得#{{n! = n \times (n - 1)!}}#。如何？明顯又是個遞迴函數了吧！

由於階乘函數比費氏數列函數還要簡單，所以直接看以下程式碼吧！

pub fn factorial_1(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        n * factorial_1(n - 1)
    }
}

fn factorial_2_recursively(n: u32, accumulator: u32) -> u32 {
    if n <= 1 {
        accumulator
    } else {
        factorial_2_recursively(n - 1, n * accumulator)
    }
}

pub fn factorial_2(n: u32) -> u32 {
    factorial_2_recursively(n, 1)
}

fn factorial_3_recursively(n: u32, accumulator: u32) -> u32 {
    loop {
        if n <= 1 {
            return accumulator;
        } else {
            return factorial_3_recursively(n - 1, n * accumulator);
        }

        break;
    }
}

pub fn factorial_3(n: u32) -> u32 {
    factorial_3_recursively(n, 1)
}

fn factorial_4_inner(mut n: u32, mut accumulator: u32) -> u32 {
    loop {
        if n <= 1 {
            return accumulator;
        } else {
            accumulator = n * accumulator;
            
            n -= 1;

            continue;
        }

        break;
    }
}

pub fn factorial_4(n: u32) -> u32 {
    factorial_4_inner(n, 1)
}

pub fn factorial_5(n: u32) -> u32 {
    let mut accumulator = 1;

    for i in 2..=n {
        accumulator *= i;
    }

    accumulator
}

public static int factorial1(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial1(n - 1);
    }
}

static int factorial2Recursively(final int n, final int accumulator) {
    if (n <= 1) {
        return accumulator;
    } else {
        return factorial2Recursively(n - 1, n * accumulator);
    }
}

public static int factorial2(final int n) {
    return factorial2Recursively(n, 1);
}

static int factorial3Recursively(final int n, final int accumulator) {
    while (true) {
        if (n <= 1) {
            return accumulator;
        } else {
            return factorial3Recursively(n - 1, n * accumulator);
        }

        break;
    }
}

public static int factorial3(final int n) {
    return factorial3Recursively(n, 1);
}

static int factorial4Inner(int n, int accumulator) {
    while (true) {
        if (n <= 1) {
            return accumulator;
        } else {
            accumulator *= n;

            --n;

            continue;
        }

        break;
    }
}

public static int factorial4(final int n) {
    return factorial4Inner(n, 1);
}

public static int factorial5(final int n) {
    int accumulator = 1;

    for (int i = 2; i <= n; ++i) {
        accumulator *= i;
    }

    return accumulator;
}

function factorial1(n: number) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial1(n - 1);
    }
}

function factorial2Recursively(n: number, accumulator: number) {
    if (n <= 1) {
        return accumulator;
    } else {
        return factorial2Recursively(n - 1, n * accumulator);
    }
}

function factorial2(n: number) {
    return factorial2Recursively(n, 1);
}

function factorial3Recursively(n: number, accumulator: number) {
    for (; ;) {
        if (n <= 1) {
            return accumulator;
        } else {
            return factorial3Recursively(n - 1, n * accumulator);
        }

        break;
    }
}

function factorial3(n: number) {
    return factorial3Recursively(n, 1);
}

function factorial4Inner(n: number, accumulator: number) {
    for (; ;) {
        if (n <= 1) {
            return accumulator;
        } else {
            accumulator *= n;

            --n;

            continue;
        }

        break;
    }
}

function factorial4(n: number) {
    return factorial4Inner(n, 1);
}

function factorial5(n: number) {
    let accumulator = 1;

    for (let i = 2;i <= n;i++) {
        accumulator *= i;
    }

    return accumulator;
}

func Factorial1(n int) int {
	if n <= 1 {
		return 1
	} else {
		return n * Factorial1(n-1)
	}
}

func factorial2Recursively(n int, accumulator int) int {
	if n <= 1 {
		return accumulator
	} else {
		return factorial2Recursively(n-1, n*accumulator)
	}
}

func Factorial2(n int) int {
	return factorial2Recursively(n, 1)
}

func factorial3Recursively(n int, accumulator int) int {
	for {
		if n <= 1 {
			return accumulator
		} else {
			return factorial3Recursively(n-1, n*accumulator)
		}

		break
	}
}

func Factorial3(n int) int {
	return factorial3Recursively(n, 1)
}

func factorial4Inner(n int, accumulator int) int {
	for {
		if n <= 1 {
			return accumulator
		} else {
			accumulator *= n

			n--

			continue
		}

		break
	}
}

func Factorial4(n int) int {
	return factorial4Inner(n, 1)
}

func Factorial5(n int) int {
	accumulator := 1

	for i := 2; i <= n; i++ {
		accumulator *= i
	}

	return accumulator
}

二元搜尋(Binary Search)

二元搜尋法是一種搜尋演算法，可以在已排序好的陣列中快速搜尋指定的元素。有關於二元搜尋法的介紹可以參考這篇文章：

https://magiclen.org/binary-search/

二元搜尋法可以用遞迴函數來實作，也可以轉成迭代函數，程式碼如下：

pub fn binary_search_1(array: &[i32], target_element: i32, start: usize, end: usize) -> Option<usize> {
    let middle = (end + start) / 2;

    let element = array[middle];

    if element == target_element {
        Some(middle)
    } else if end == start {
        None
    } else {
        if target_element > element {
            binary_search_1(array, target_element, middle + 1, end)
        } else {
            if middle > 0 {
                binary_search_1(array, target_element, start, middle - 1)
            } else {
                None
            }
        }
    }
}

pub fn binary_search_3(array: &[i32], target_element: i32, start: usize, end: usize) -> Option<usize> {
    loop {
        let middle = (end + start) / 2;

        let element = array[middle];

        if element == target_element {
            Some(middle)
        } else if end == start {
            None
        } else {
            if target_element > element {
                binary_search_3(array, target_element, middle + 1, end)
            } else {
                if middle > 0 {
                    binary_search_3(array, target_element, start, middle - 1)
                } else {
                    None
                }
            }
        }

        break;
    }
}

pub fn binary_search_4(array: &[i32], target_element: i32, mut start: usize, mut end: usize) -> Option<usize> {
    loop {
        let middle = (end + start) / 2;

        let element = array[middle];

        if element == target_element {
            Some(middle)
        } else if end == start {
            None
        } else {
            if target_element > element {
                start = middle + 1;

                continue;
            } else {
                if middle > 0 {
                    end = middle - 1;

                    continue;
                } else {
                    None
                }
            }
        }

        break;
    }
}

pub fn binary_search_5(array: &[i32], target_element: i32, mut start: usize, mut end: usize) -> Option<usize> {
    while end >= start {
        let middle = (end + start) / 2;

        let element = array[middle];

        if element == target_element {
            return Some(middle);
        } else {
            if target_element > element {
                start = middle + 1;
            } else {
                if middle > 0 {
                    end = middle - 1;
                } else {
                    return None;
                }
            }
        }
    }

    None
}

public static int binarySearch1(final int[] array, final int targetElement, final int start, final int end) {
    final int middle = (end + start) / 2;

    final int element = array[middle];

    if (element == targetElement) {
        return middle;
    } else if (end == start) {
        return -1;
    } else {
        if (targetElement > element) {
            return binarySearch1(array, targetElement, middle + 1, end);
        } else {
            return binarySearch1(array, targetElement, start, middle - 1);
        }
    }
}

public static int binarySearch3(final int[] array, final int targetElement, final int start, final int end) {
    while (true) {
        final int middle = (end + start) / 2;

        final int element = array[middle];

        if (element == targetElement) {
            return middle;
        } else if (end == start) {
            return -1;
        } else {
            if (targetElement > element) {
                return binarySearch3(array, targetElement, middle + 1, end);
            } else {
                return binarySearch3(array, targetElement, start, middle - 1);
            }
        }

        break;
    }
}

public static int binarySearch4(final int[] array, final int targetElement, int start, int end) {
    while (true) {
        final int middle = (end + start) / 2;

        final int element = array[middle];

        if (element == targetElement) {
            return middle;
        } else if (end == start) {
            return -1;
        } else {
            if (targetElement > element) {
                start = middle + 1;

                continue;
            } else {
                end = middle - 1;

                continue;
            }
        }

        break;
    }
}

public static int binarySearch5(final int[] array, final int targetElement, int start, int end) {
    while (end >= start) {
        final int middle = (end + start) / 2;

        final int element = array[middle];

        if (element == targetElement) {
            return middle;
        } else {
            if (targetElement > element) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
    }

    return -1;
}

function binarySearch1(array: number[], targetElement: number, start: number, end: number) {
    const middle = Math.floor((end + start) / 2);

    const element = array[middle];

    if (element === targetElement) {
        return middle;
    } else if (end === start) {
        return -1;
    } else if (targetElement > element) {
        return binarySearch1(array, targetElement, middle + 1, end);
    } else {
        return binarySearch1(array, targetElement, start, middle - 1);
    }
}

function binarySearch3(array: number[], targetElement: number, start: number, end: number) {
    for (; ;) {
        const middle = Math.floor((end + start) / 2);

        const element = array[middle];

        if (element === targetElement) {
            return middle;
        } else if (end === start) {
            return -1;
        } else if (targetElement > element) {
            return binarySearch3(array, targetElement, middle + 1, end);
        } else {
            return binarySearch3(array, targetElement, start, middle - 1);
        }

        break;
    }
}

function binarySearch4(array: number[], targetElement: number, start: number, end: number) {
    for (; ;) {
        const middle = Math.floor((end + start) / 2);

        const element = array[middle];

        if (element === targetElement) {
            return middle;
        } else if (end === start) {
            return -1;
        } else if (targetElement > element) {
            start = middle + 1;

            continue;
        } else {
            end = middle - 1;

            continue;
        }

        break;
    }
}

function binarySearch5(array: number[], targetElement: number, start: number, end: number) {
    while (end >= start) {
        const middle = Math.floor((end + start) / 2);

        const element = array[middle];

        if (element === targetElement) {
            return middle;
        } else if (targetElement > element) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }

    return -1;
}

func BinarySearch1(array []int, targetElement int, start int, end int) int {
	middle := (end + start) / 2

	element := array[middle]

	if element == targetElement {
		return middle
	} else if end == start {
		return -1
	} else {
		if targetElement > element {
			return BinarySearch1(array, targetElement, middle+1, end)
		} else {
			return BinarySearch1(array, targetElement, start, middle-1)
		}
	}
}

func BinarySearch3(array []int, targetElement int, start int, end int) int {
	for {
		middle := (end + start) / 2

		element := array[middle]

		if element == targetElement {
			return middle
		} else if end == start {
			return -1
		} else {
			if targetElement > element {
				return BinarySearch3(array, targetElement, middle+1, end)
			} else {
				return BinarySearch3(array, targetElement, start, middle-1)
			}
		}

		break
	}
}

func BinarySearch4(array []int, targetElement int, start int, end int) int {
	for {
		middle := (end + start) / 2

		element := array[middle]

		if element == targetElement {
			return middle
		} else if end == start {
			return -1
		} else {
			if targetElement > element {
				start = middle + 1

				continue
			} else {
				end = middle - 1

				continue
			}
		}

		break
	}
}

func BinarySearch5(array []int, targetElement int, start int, end int) int {
	for end >= start {
		middle := (end + start) / 2

		element := array[middle]

		if element == targetElement {
			return middle
		} else {
			if targetElement > element {
				start = middle + 1
			} else {
				end = middle - 1
			}
		}
	}

	return -1
}

二元搜尋樹(BST, Binary Search Tree)的搜尋

二元搜尋樹是一種二元樹(Binary Tree)。節點如果有左邊子節點的話，其左邊子節點連接的所有值都必須要小於該節點的值；節點如果有右邊子節點的話，其右邊子節點連接的所有值都必須要大於或等於該節點的值。例如以下結構即為二元搜尋樹：

        7
       / \
      /   \
     /     \
    /       \
   3         9
  / \       / \
 /   \     /   \
1     5   8     9
 \   / \
  2 4   6

若我們想在二元搜尋樹中找出擁有某個目標值的節點，或者小於但最接近這某個目標值的節點，可以使用遞迴函數來輕易完成。程式碼如下：

use std::cell::RefCell;
use std::rc::Rc;
use std::cmp::Ordering;

#[derive(Debug)]
pub struct Node {
    pub value: i32,
    pub left_child: Option<Rc<RefCell<Node>>>,
    pub right_child: Option<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(value: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node {
            value,
            left_child: None,
            right_child: None,
        }))
    }

    pub fn get_left_child(node: Rc<RefCell<Node>>) -> Option<Rc<RefCell<Node>>> {
        node.borrow().left_child.as_ref().cloned()
    }

    pub fn get_right_child(node: Rc<RefCell<Node>>) -> Option<Rc<RefCell<Node>>> {
        node.borrow().right_child.as_ref().cloned()
    }
}

pub fn bst_find_node(
    node: Option<Rc<RefCell<Node>>>,
    target_value: i32,
) -> Option<Rc<RefCell<Node>>> {
    match node {
        Some(n) => {
            let value = n.borrow().value;

            match target_value.cmp(&value) {
                Ordering::Equal => Some(n),
                Ordering::Less => bst_find_node(Node::get_left_child(n), target_value),
                Ordering::Greater => {
                    let right_sub_node =
                        bst_find_node(Node::get_right_child(n.clone()), target_value);

                    match right_sub_node {
                        Some(right_sub_n) => Some(right_sub_n),
                        None => Some(n),
                    }
                }
            }
        }
        None => None,
    }
}

同樣地，若要把這個遞迴函數改成迭代函數，就要讓它使用尾端遞迴。我們可以替這個遞迴函數新增一個參數來儲存當node參數為空時，函數會回傳的結果。

函數修改後如下：

fn bst_find_node_inner(
    node: Option<Rc<RefCell<Node>>>,
    target_value: i32,
    default: Option<Rc<RefCell<Node>>>,
) -> Option<Rc<RefCell<Node>>> {
    match node {
        Some(n) => {
            let value = n.borrow().value;

            match target_value.cmp(&value) {
                Ordering::Equal => Some(n),
                Ordering::Less => {
                    bst_find_node_inner(Node::get_left_child(n), target_value, default)
                }
                Ordering::Greater => {
                    bst_find_node_inner(Node::get_right_child(n.clone()), target_value, Some(n))
                }
            }
        }
        None => default,
    }
}

pub fn bst_find_node(
    node: Option<Rc<RefCell<Node>>>,
    target_value: i32,
) -> Option<Rc<RefCell<Node>>> {
    bst_find_node_inner(node, target_value, None)
}

按照先前介紹的方式，把只有尾端遞迴呼叫的遞迴函數改成迭代的版本吧！

// fn bst_find_node_inner(
//     mut node: Option<Rc<RefCell<Node>>>,
//     target_value: i32,
//     mut default: Option<Rc<RefCell<Node>>>,
// ) -> Option<Rc<RefCell<Node>>> {
//     loop {
//         match node {
//             Some(n) => {
//                 let value = n.borrow().value;
//
//                 match target_value.cmp(&value) {
//                     Ordering::Equal => return Some(n),
//                     Ordering::Less => {
//                         node = Node::get_left_child(n);
//
//                         continue;
//                     }
//                     Ordering::Greater => {
//                         default = Some(n.clone());
//
//                         node = Node::get_right_child(n);
//
//                         continue;
//                     }
//                 }
//             }
//             None => return default,
//         }
//
//         break;
//     }
// }

pub fn bst_find_node(
    mut node: Option<Rc<RefCell<Node>>>,
    target_value: i32,
) -> Option<Rc<RefCell<Node>>> {
    let mut default = None;

    while let Some(n) = node.as_ref().cloned() {
        let value = n.borrow().value;

        match target_value.cmp(&value) {
            Ordering::Equal => return Some(n),
            Ordering::Less => {
                node = Node::get_left_child(n);
            }
            Ordering::Greater => {
                default = Some(n.clone());

                node = Node::get_right_child(n);
            }
        }
    }

    default
}

遞迴關係式(Recurrence Relation)的另外轉換方式

對於階乘數列或是費氏數列這類有遞迴關係的數列，我們其實不一定要找出其尾端遞迴函數，就有辦法將其轉成迭代函數。

就以前面非尾端遞迴版本的階乘遞迴函數來舉例好了。程式碼如下：

pub fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

function factorial(n: number) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

func Factorial(n int) int {
	if n <= 1 {
		return 1
	} else {
		return n * Factorial(n-1)
	}
}

步驟一：將遞迴呼叫的部份拆成子程序

為了方便理解程式碼，我們要先從遞迴呼叫發生的位置，一直到之後函數結束執行的部份都轉一個子程序(另外寫成新的函數)。

程式碼如下：

fn step(n: u32) -> u32 {
    n * factorial(n - 1)
}

pub fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        step(n)
    }
}

static int step(final int n) {
    return n * factorial(n - 1);
}

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        return step(n);
    }
}

function step(n: number): number {
    return n * factorial(n - 1);
}

function factorial(n: number) {
    if (n <= 1) {
        return 1;
    } else {
        return step(n);
    }
}

func step(n int) int {
	return n * Factorial(n-1)
}

func Factorial(n int) int {
	if n <= 1 {
		return 1
	} else {
		return step(n)
	}
}

步驟二：拆解子程序的程式敘述

將子程序的步驟分為三大部份：遞迴呼叫(取得前項結果)、計算目前這項的結果，以及回傳結果。

程式碼如下：

fn step(n: u32) -> u32 {
    let previous_x = factorial(n - 1);
    let x = n * previous_x;
    x
}

pub fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        step(n)
    }
}

static int step(final int n) {
    final int previousX = factorial(n - 1);
    final int x = n * previousX;
    return x;
}

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        return step(n);
    }
}

function step(n: number) {
    const previousX = factorial(n - 1);
    const x = n * previousX;
    return x;
}

function factorial(n: number): number {
    if (n <= 1) {
        return 1;
    } else {
        return step(n);
    }
}

func step(n int) int {
	previousX := Factorial(n - 1)
	x := n * previousX
	return x
}

func Factorial(n int) int {
	if n <= 1 {
		return 1
	} else {
		return step(n)
	}
}

步驟三：替子程序新增參數，使其可以透過參數傳入前項結果

以往我們在求遞迴關係式之數列的時候，為了要求得第#{{n}}#項的結果，就要先去計算第#{{n}}#項之前的結果。但是我們現在要反過來，變成先求得第#{{n}}#項之前的結果，再直接用這個結果算出第#{{n}}#項。有沒有聽起來更像是用迴圈就可以完成的事？

這個步驟算是一個過渡性的步驟(單獨看無意義)，是為了之後的修改而做的鋪墊。

fn step(n: u32, previous_x: Option<u32>) -> u32 {
    let previous_x = if let Some(previous_x) = previous_x {
        previous_x
    } else {
        factorial(n - 1)
    };

    let x = n * previous_x;
    x
}

pub fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        step(n, None)
    }
}

static int step(final int n, final Optional<Integer> previousX) {
    final int iPreviousX;
    
    if (previousX.isPresent()) {
        iPreviousX = previousX.get();
    } else {
        iPreviousX = factorial(n - 1);
    }
    
    final int x = n * iPreviousX;
    return x;
}

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        return step(n, Optional.empty());
    }
}

function step(n: number, previousX?: number) {
    if (typeof previousX !== "number") {
        previousX = factorial(n - 1);
    }
    const x = n * previousX;
    return x;
}

function factorial(n: number): number {
    if (n <= 1) {
        return 1;
    } else {
        return step(n);
    }
}

func step(n int, previousX ...int) int {
	var iPreviousX int

	if len(previousX) > 0 {
		iPreviousX = previousX[0]
	} else {
		iPreviousX = Factorial(n - 1)
	}

	x := n * iPreviousX
	return x
}

func Factorial(n int) int {
	if n <= 1 {
		return 1
	} else {
		return step(n)
	}
}

步驟四：讓子程序除了回傳目前這項的計算結果外，也回傳計算下一項時會用到的參數

若我們讓子程序除了回傳目前這項的計算結果外，也回傳計算下一項時會用到的參數，就可以在每次呼叫子程序後，得到目前這項的結果，以及計算下一項需要用到的參數，如此一來我們便可以再利用這些數值套入公式，直接計算出下一項的結果。當然，如果有不變的參數，子程序就沒有必要再將其回傳出來了。這也是一個過渡性的步驟(單獨看無意義，且回傳出來的新參數暫時用不到)。

fn step(n: u32, previous_x: Option<u32>) -> (u32, u32) {
    let previous_x = if let Some(previous_x) = previous_x {
        previous_x
    } else {
        factorial(n - 1)
    };

    let x = n * previous_x;
    (n - 1, x)
}

pub fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        step(n, None).1
    }
}

static int[] step(final int n, final Optional<Integer> previousX) {
    final int iPreviousX;

    if (previousX.isPresent()) {
        iPreviousX = previousX.get();
    } else {
        iPreviousX = factorial(n - 1);
    }

    final int x = n * iPreviousX;
    return new int[]{n + 1, x};
}

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        return step(n, Optional.empty())[1];
    }
}

function step(n: number, previousX?: number) {
    if (typeof previousX !== "number") {
        previousX = factorial(n - 1);
    }
    const x = n * previousX;
    return [n + 1, x];
}

function factorial(n: number): number {
    if (n <= 1) {
        return 1;
    } else {
        return step(n)[1];
    }
}

func step(n int, previousX ...int) (int, int) {
	var iPreviousX int

	if len(previousX) > 0 {
		iPreviousX = previousX[0]
	} else {
		iPreviousX = Factorial(n - 1)
	}

	x := n * iPreviousX
	return n + 1, x
}

func Factorial(n int) int {
	if n <= 1 {
		return 1
	} else {
		_, x := step(n)

		return x
	}
}

步驟五：現在，改用迴圈來呼叫子程序吧！

我們只要按照遞迴關係數列的基礎項定義參數的初始值，就可以從初始值利用迴圈重複呼叫剛才完成的子程序，來計算到我們要的第#{{n}}#項。

以階乘數列來說，基礎項就是#{{0! = 1}}#，所以計算時要從#{{1!}}#開始計算。#{{1!}}#的前一項是#{{0!}}#，也就是要以#{{1}}#作為子程序上一項的結果，並以計算第1項為始去呼叫子程序，計算#{{n}}#次後就是我們要的第#{{n}}#項了。程式修改如下：

fn step(n: u32, previous_x: Option<u32>) -> (u32, u32) {
    let previous_x = if let Some(previous_x) = previous_x {
        previous_x
    } else {
        factorial(n - 1)
    };

    let x = n * previous_x;
    (n + 1, x)
}

pub fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        let t = n;

        let (mut n, mut previous_x) = (1, 1);

        for _ in 0..t {
            let (next_n, x) = step(n, Some(previous_x));

            n = next_n;
            previous_x = x;
        }

        previous_x
    }
}

static int[] step(final int n, final Optional<Integer> previousX) {
    final int iPreviousX;

    if (previousX.isPresent()) {
        iPreviousX = previousX.get();
    } else {
        iPreviousX = factorial(n - 1);
    }

    final int x = n * iPreviousX;
    return new int[]{n + 1, x};
}

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    } else {
        final int t = n;

        int nn = 1;
        int previousX = 1;

        for (int i = 0; i < t; ++i) {
            final int[] r = step(nn, Optional.of(previousX));

            nn = r[0];
            previousX = r[1];
        }

        return previousX;
    }
}

function step(n: number, previousX?: number) {
    if (typeof previousX !== "number") {
        previousX = factorial(n - 1);
    }
    const x = n * previousX;
    return [n + 1, x];
}

function factorial(n: number) {
    if (n <= 1) {
        return 1;
    } else {
        const t = n;

        let nn = 1;
        let previousX = 1;

        for (let i = 0;i < t;i++) {
            [nn, previousX] = step(nn, previousX);
        }

        return previousX;
    }
}

func step(n int, previousX ...int) (int, int) {
	var iPreviousX int

	if len(previousX) > 0 {
		iPreviousX = previousX[0]
	} else {
		iPreviousX = Factorial(n - 1)
	}

	x := n * iPreviousX
	return n + 1, x
}

func Factorial(n int) int {
	if n <= 1 {
		return 1
	} else {
		t := n

		nn := 1
		previousX := 1

		for i := 0; i < t; i++ {
			nn, previousX = step(nn, previousX)
		}

		return previousX
	}
}

步驟六：整理程式碼

觀察我們目前寫出來的程式碼，其實不難發現，因為一開始就有給子程序計算目前這項數值時會用到的前項數值，所以子程序完全不會進入遞迴呼叫的流程，所以這部份的程式碼可以直接拿掉了。再來就是遞迴關係數列的基礎項，原先有用if等關鍵字事先判斷，也可以視情況將其移除。

於是我們可以將程式碼整理如下：

fn step(n: u32, previous_x: u32) -> (u32, u32) {
    let x = n * previous_x;
    (n + 1, x)
}

pub fn factorial(n: u32) -> u32 {
    let t = n;

    let (mut n, mut previous_x) = (1, 1);

    for _ in 0..t {
        let (next_n, x) = step(n, previous_x);

        n = next_n;
        previous_x = x;
    }

    previous_x
}

static int[] step(final int n, final int previousX) {
    final int x = n * previousX;
    return new int[]{n + 1, x};
}

public static int factorial(final int n) {
    final int t = n;

    int nn = 1;
    int previousX = 1;

    for (int i = 0; i < t; ++i) {
        final int[] r = step(nn, previousX);

        nn = r[0];
        previousX = r[1];
    }

    return previousX;
}

function step(n: number, previousX: number) {
    const x = n * previousX;
    return [n + 1, x];
}

function factorial(n: number) {
    const t = n;

    let nn = 1;
    let previousX = 1;

    for (let i = 0;i < t;i++) {
        [nn, previousX] = step(nn, previousX);
    }

    return previousX;
}

func step(n int, previousX int) (int, int) {
	x := n * previousX
	return n + 1, x
}

func Factorial(n int) int {
	t := n

	nn := 1
	previousX := 1

	for i := 0; i < t; i++ {
		nn, previousX = step(nn, previousX)
	}

	return previousX
}

至此我們就成功地把遞迴的階乘函數改成迭代版本了！

步驟七：將子程序內聯(inline)回原本的函數

如果子程序並不複雜，我們完全可以考慮把它移回原來的函數中，省下呼叫函數時所產生的開支。雖然有些編譯器會自動對簡單的函數做內聯優化，但這件事自己來做才能保證最終它們不是分開的函數。

pub fn factorial(n: u32) -> u32 {
    let t = n;

    let (mut n, mut previous_x) = (1, 1);

    for _ in 0..t {
        previous_x *= n;
        n += 1;
    }

    previous_x
}

public static int factorial(final int n) {
    final int t = n;

    int nn = 1;
    int previousX = 1;

    for (int i = 0; i < t; ++i) {
        previousX *= nn;
        ++nn;
    }

    return previousX;
}

function factorial(n: number) {
    const t = n;

    let nn = 1;
    let previousX = 1;

    for (let i = 0;i < t;i++) {
        previousX *= nn;
        nn += 1;
    }

    return previousX;
}

func Factorial(n int) int {
	t := n

	nn := 1
	previousX := 1

	for i := 0; i < t; i++ {
		previousX *= nn
		nn++
	}

	return previousX
}

步驟八：再次整理程式碼

內聯之後的迭代函數，可能會有一些冗餘的地方可以進行合併與刪減。

整理一下後，程式碼最終會變成：

pub fn factorial(n: u32) -> u32 {
    let mut previous_x = 1;

    for i in 2..=n {
        previous_x *= i;
    }

    previous_x
}

public static int factorial(final int n) {
    int previousX = 1;

    for (int i = 2; i <= n; ++i) {
        previousX *= i;
    }

    return previousX;
}

function factorial(n: number) {
    let previousX = 1;

    for (let i = 2;i <= n;i++) {
        previousX *= i;
    }

    return previousX;
}

func Factorial(n int) int {
	previousX := 1

	for i := 2; i <= n; i++ {
		previousX *= i
	}

	return previousX
}

更多的轉換例子

有遞迴關係的數列函數基本上都可以嘗試使用上面的流程來轉換成迭代函數，以下再舉別的例子。

費氏數列

本篇文章最一開始就有詳細說明費氏數列的遞迴函數轉迭代函數的方式，現在則要改用第二種方式來進行轉換。

直接看以下程式碼吧！

fn step_1(n: u32) -> u32 {
    fibonacci_1(n - 1) + fibonacci_1(n - 2)
}

pub fn fibonacci_1(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => step_1(n),
    }
}

fn step_2(n: u32) -> u32 {
    let previous_x = fibonacci_2(n - 1);
    let before_previous_x = fibonacci_2(n - 2);
    let x = previous_x + before_previous_x;
    x
}

pub fn fibonacci_2(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => step_2(n),
    }
}

fn step_3(n: u32, previous_x: Option<u32>, before_previous_x: Option<u32>) -> u32 {
    let previous_x = if let Some(previous_x) = previous_x {
        previous_x
    } else {
        fibonacci_3(n - 1)
    };

    let before_previous_x = if let Some(before_previous_x) = before_previous_x {
        before_previous_x
    } else {
        fibonacci_3(n - 2)
    };

    let x = previous_x + before_previous_x;
    x
}

pub fn fibonacci_3(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => step_3(n, None, None),
    }
}

fn step_4(n: u32, previous_x: Option<u32>, before_previous_x: Option<u32>) -> (u32, u32, u32) {
    let previous_x = if let Some(previous_x) = previous_x {
        previous_x
    } else {
        fibonacci_4(n - 1)
    };

    let before_previous_x = if let Some(before_previous_x) = before_previous_x {
        before_previous_x
    } else {
        fibonacci_4(n - 2)
    };

    let x = previous_x + before_previous_x;
    (n + 1, previous_x, x)
}

pub fn fibonacci_4(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => step_4(n, None, None).2,
    }
}

fn step_5(n: u32, previous_x: Option<u32>, before_previous_x: Option<u32>) -> (u32, u32, u32) {
    let previous_x = if let Some(previous_x) = previous_x {
        previous_x
    } else {
        fibonacci_5(n - 1)
    };

    let before_previous_x = if let Some(before_previous_x) = before_previous_x {
        before_previous_x
    } else {
        fibonacci_5(n - 2)
    };

    let x = previous_x + before_previous_x;
    (n + 1, previous_x, x)
}

pub fn fibonacci_5(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => {
            let t = n - 1;

            let (mut n, mut previous_x, mut before_previous_x) = (2, 1, 0);

            for _ in 0..t {
                let (next_n, next_before_previous_x, x) = step_5(n, Some(previous_x), Some(before_previous_x));

                n = next_n;
                previous_x = x;
                before_previous_x = next_before_previous_x;
            }

            previous_x
        }
    }
}

fn step_6(n: u32, previous_x: u32, before_previous_x: u32) -> (u32, u32, u32) {
    let x = previous_x + before_previous_x;
    (n + 1, previous_x, x)
}

pub fn fibonacci_6(n: u32) -> u32 {
    match n {
        0 => 0,
        n => {
            let t = n - 1;

            let (mut n, mut previous_x, mut before_previous_x) = (2, 1, 0);

            for _ in 0..t {
                let (next_n, next_before_previous_x, x) = step_6(n, previous_x, before_previous_x);

                n = next_n;
                previous_x = x;
                before_previous_x = next_before_previous_x;
            }

            previous_x
        }
    }
}

pub fn fibonacci_7(n: u32) -> u32 {
    match n {
        0 => 0,
        n => {
            let t = n - 1;

            let (mut n, mut previous_x, mut before_previous_x) = (2, 1, 0);

            for _ in 0..t {
                let x = previous_x + before_previous_x;

                n += 1;
                before_previous_x = previous_x;
                previous_x = x;
            }

            previous_x
        }
    }
}

pub fn fibonacci_8(n: u32) -> u32 {
    match n {
        0 => 0,
        n => {
            let (mut previous_x, mut before_previous_x) = (1, 0);

            for _ in 1..n {
                let x = previous_x + before_previous_x;

                before_previous_x = previous_x;
                previous_x = x;
            }

            previous_x
        }
    }
}

static int step1(final int n) {
    return fibonacci1(n - 1) + fibonacci7(n - 2);
}

public static int fibonacci1(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step1(n);
    }
}

static int step2(final int n) {
    final int previousX = fibonacci2(n - 1);
    final int beforePreviousX = fibonacci2(n - 2);
    final int x = previousX + beforePreviousX;
    return x;
}

public static int fibonacci2(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step2(n);
    }
}

static int step3(final int n, final Optional<Integer> previousX, final Optional<Integer> beforePreviousX) {
    final int iPreviousX, iBeforePreviousX;

    if (previousX.isPresent()) {
        iPreviousX = previousX.get();
    } else {
        iPreviousX = fibonacci3(n - 1);
    }

    if (beforePreviousX.isPresent()) {
        iBeforePreviousX = beforePreviousX.get();
    } else {
        iBeforePreviousX = fibonacci3(n - 2);
    }

    final int x = iPreviousX + iBeforePreviousX;
    return x;
}

public static int fibonacci3(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step3(n, Optional.empty(), Optional.empty());
    }
}

static int[] step4(final int n, final Optional<Integer> previousX, final Optional<Integer> beforePreviousX) {
    final int iPreviousX, iBeforePreviousX;

    if (previousX.isPresent()) {
        iPreviousX = previousX.get();
    } else {
        iPreviousX = fibonacci4(n - 1);
    }

    if (beforePreviousX.isPresent()) {
        iBeforePreviousX = beforePreviousX.get();
    } else {
        iBeforePreviousX = fibonacci4(n - 2);
    }

    final int x = iPreviousX + iBeforePreviousX;
    return new int[]{n + 1, iPreviousX, x};
}

public static int fibonacci4(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step4(n, Optional.empty(), Optional.empty())[2];
    }
}

static int[] step5(final int n, final Optional<Integer> previousX, final Optional<Integer> beforePreviousX) {
    final int iPreviousX, iBeforePreviousX;

    if (previousX.isPresent()) {
        iPreviousX = previousX.get();
    } else {
        iPreviousX = fibonacci5(n - 1);
    }

    if (beforePreviousX.isPresent()) {
        iBeforePreviousX = beforePreviousX.get();
    } else {
        iBeforePreviousX = fibonacci5(n - 2);
    }

    final int x = iPreviousX + iBeforePreviousX;
    return new int[]{n + 1, iPreviousX, x};
}

public static int fibonacci5(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            final int t = n - 1;

            int nn = 2;
            int previousX = 1;
            int beforePreviousX = 0;

            for (int i = 0; i < t; ++i) {
                final int[] r = step5(nn, Optional.of(previousX), Optional.of(beforePreviousX));

                nn = r[0];
                previousX = r[2];
                beforePreviousX = r[1];
            }

            return previousX;
    }
}

static int[] step6(int n, final int previousX, final int beforePreviousX) {
    final int x = previousX + beforePreviousX;
    return new int[]{n + 1, previousX, x};
}

public static int fibonacci6(final int n) {
    switch (n) {
        case 0:
            return 0;
        default:
            final int t = n - 1;

            int nn = 2;
            int previousX = 1;
            int beforePreviousX = 0;

            for (int i = 0; i < t; ++i) {
                final int[] r = step6(nn, previousX, beforePreviousX);

                nn = r[0];
                previousX = r[2];
                beforePreviousX = r[1];
            }

            return previousX;
    }
}

public static int fibonacci7(final int n) {
    switch (n) {
        case 0:
            return 0;
        default:
            final int t = n - 1;

            int nn = 2;
            int previousX = 1;
            int beforePreviousX = 0;

            for (int i = 0; i < t; ++i) {
                final int x = previousX + beforePreviousX;

                ++nn;
                beforePreviousX = previousX;
                previousX = x;
            }

            return previousX;
    }
}

public static int fibonacci8(final int n) {
    switch (n) {
        case 0:
            return 0;
        default:
            int previousX = 1;
            int beforePreviousX = 0;

            for (int i = 1; i < n; ++i) {
                final int x = previousX + beforePreviousX;

                beforePreviousX = previousX;
                previousX = x;
            }

            return previousX;
    }
}

function step1(n: number) {
    return fibonacci1(n - 1) + fibonacci1(n - 2);
}

function fibonacci1(n: number): number {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step1(n);
    }
}

function step2(n: number) {
    const previousX = fibonacci2(n - 1);
    const beforePreviousX = fibonacci2(n - 2);
    const x = previousX + beforePreviousX;
    return x;
}

function fibonacci2(n: number): number {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step2(n);
    }
}

function step3(n: number, previousX?: number, beforePreviousX?: number) {
    if (typeof previousX !== "number") {
        previousX = fibonacci3(n - 1);
    }

    if (typeof beforePreviousX !== "number") {
        beforePreviousX = fibonacci3(n - 2);
    }

    const x = previousX + beforePreviousX;
    return x;
}

function fibonacci3(n: number): number {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step3(n);
    }
}

function step4(n: number, previousX?: number, beforePreviousX?: number) {
    if (typeof previousX !== "number") {
        previousX = fibonacci4(n - 1);
    }

    if (typeof beforePreviousX !== "number") {
        beforePreviousX = fibonacci4(n - 2);
    }

    const x = previousX + beforePreviousX;
    return [n + 1, previousX, x];
}

function fibonacci4(n: number): number {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return step4(n)[2];
    }
}

function step5(n: number, previousX?: number, beforePreviousX?: number) {
    if (typeof previousX !== "number") {
        previousX = fibonacci5(n - 1);
    }

    if (typeof beforePreviousX !== "number") {
        beforePreviousX = fibonacci5(n - 2);
    }

    const x = previousX + beforePreviousX;
    return [n + 1, previousX, x];
}

function fibonacci5(n: number) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default: {
            const t = n - 1;

            let nn = 2;
            let previousX = 1;
            let beforePreviousX = 0;

            for (let i = 0;i < t;i++) {
                [nn, beforePreviousX, previousX] = step5(nn, previousX, beforePreviousX);
            }

            return previousX;
        }
    }
}

function step6(n: number, previousX: number, beforePreviousX: number) {
    const x = previousX + beforePreviousX;
    return [n + 1, previousX, x];
}

function fibonacci6(n: number) {
    switch (n) {
        case 0:
            return 0;
        default: {
            const t = n - 1;

            let nn = 2;
            let previousX = 1;
            let beforePreviousX = 0;

            for (let i = 0;i < t;i++) {
                [nn, beforePreviousX, previousX] = step6(nn, previousX, beforePreviousX);
            }

            return previousX;
        }
    }
}

function fibonacci7(n: number) {
    switch (n) {
        case 0:
            return 0;
        default: {
            const t = n - 1;

            let nn = 2;
            let previousX = 1;
            let beforePreviousX = 0;

            for (let i = 0;i < t;i++) {
                const x = previousX + beforePreviousX;

                nn += 1;
                beforePreviousX = previousX;
                previousX = x;
            }

            return previousX;
        }
    }
}

function fibonacci8(n: number) {
    switch (n) {
        case 0:
            return 0;
        default: {
            let previousX = 1;
            let beforePreviousX = 0;

            for (let i = 1;i < n;i++) {
                const x = previousX + beforePreviousX;

                beforePreviousX = previousX;
                previousX = x;
            }

            return previousX;
        }
    }
}

func step1(n int) int {
	return Fibonacci1(n-1) + Fibonacci1(n-2)
}

func Fibonacci1(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		return step1(n)
	}
}

func step2(n int) int {
	previousX := Fibonacci2(n - 1)
	beforePreviousX := Fibonacci2(n - 2)
	x := previousX + beforePreviousX
	return x
}

func Fibonacci2(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		return step2(n)
	}
}

func step3(n int, previous ...int) int {
	var previousX, beforePreviousX int

	if len(previous) > 0 {
		previousX = previous[0]
	} else {
		previousX = Fibonacci3(n - 1)
	}

	if len(previous) > 1 {
		beforePreviousX = previous[1]
	} else {
		beforePreviousX = Fibonacci3(n - 2)
	}

	x := previousX + beforePreviousX
	return x
}

func Fibonacci3(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		return step3(n)
	}
}

func step4(n int, previous ...int) (int, int, int) {
	var previousX, beforePreviousX int

	if len(previous) > 0 {
		previousX = previous[0]
	} else {
		previousX = Fibonacci4(n - 1)
	}

	if len(previous) > 1 {
		beforePreviousX = previous[1]
	} else {
		beforePreviousX = Fibonacci4(n - 2)
	}

	x := previousX + beforePreviousX
	return n + 1, previousX, x
}

func Fibonacci4(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		_, _, x := step4(n)

		return x
	}
}

func step5(n int, previous ...int) (int, int, int) {
	var previousX, beforePreviousX int

	if len(previous) > 0 {
		previousX = previous[0]
	} else {
		previousX = Fibonacci5(n - 1)
	}

	if len(previous) > 1 {
		beforePreviousX = previous[1]
	} else {
		beforePreviousX = Fibonacci5(n - 2)
	}

	x := previousX + beforePreviousX
	return n + 1, previousX, x
}

func Fibonacci5(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		t := n - 1

		nn := 2
		previousX := 1
		beforePreviousX := 0

		for i := 0; i < t; i++ {
			nn, beforePreviousX, previousX = step5(nn, previousX, beforePreviousX)
		}

		return previousX
	}
}

func step6(n int, previousX int, beforePreviousX int) (int, int, int) {
	x := previousX + beforePreviousX
	return n + 1, previousX, x
}

func Fibonacci6(n int) int {
	switch n {
	case 0:
		return 0
	default:
		t := n - 1

		nn := 2
		previousX := 1
		beforePreviousX := 0

		for i := 0; i < t; i++ {
			nn, beforePreviousX, previousX = step6(nn, previousX, beforePreviousX)
		}

		return previousX
	}
}

func Fibonacci7(n int) int {
	switch n {
	case 0:
		return 0
	default:
		t := n - 1

		nn := 2
		previousX := 1
		beforePreviousX := 0

		for i := 0; i < t; i++ {
			x := previousX + beforePreviousX

			nn++
			beforePreviousX = previousX
			previousX = x
		}

		return previousX
	}
}

func Fibonacci8(n int) int {
	switch n {
	case 0:
		return 0
	default:
		previousX := 1
		beforePreviousX := 0

		for i := 1; i < n; i++ {
			x := previousX + beforePreviousX

			beforePreviousX = previousX
			previousX = x
		}

		return previousX
	}
}

動態規劃

動態規劃是一個將遞迴函數轉迭代函數的有效方式，不過有點複雜，請參考另一篇文章：

https://magiclen.org/dynamic-programming-basic/

自行建立空間來模擬堆疊空間

實務上，我們常會遇到無法或是很難被轉成尾端遞迴的遞迴函數，這時候我們可以自行建立額外的堆疊(Stack)空間或堆積(Heap)空間來模擬函數在遞迴時使用到的堆疊空間，以此提升效能或是避免堆疊空間不足。換句話說，我們要自己寫程式實作出遞迴發生時，參數(和區域變數，但不建議)在模擬的堆疊空間內的存取情形。

要以這樣的方式將遞迴函數轉成迭代函數，可以先根據遞迴函數主體的結構來判斷能不能符合以下幾種型樣(pattern)，再分別用不同的方式來模擬堆疊空間的存取。

遞迴函數無回傳，遞迴呼叫只連續發生在尾端

void f(param1, param2, ..., paramN) {
    // do something

    f(a, b, ..., n); // recursive call 1
    f(aa, bb, ..., nn); // recursive call 2
    // ...
    f(aaa, bbb, ..., nnn); // recursive call n
}

以上這種遞迴函數的結構是最簡單的，我們只需要先用總是可以被執行的迴圈來將原本遞迴函數主體中的所有程式敘述包起來，然後在這個迴圈外的上方建立一個堆疊空間，把傳進遞迴函數的參數push到堆疊空間中(只需存會有變化的參數)。接著在剛才加上的迴圈內，一開始的時候去pop這些參數，用這些參數去做原本該做的事，最後反轉(因為堆疊是先進後出)遞迴呼叫的部份，並且將遞迴呼叫的程式敘述都改成把遞迴呼叫時的參數push到堆疊空間中。若迴圈一開始無法從堆疊空間中pop到參數，就跳出迴圈。

所以之後形成的迭代函數看起來會像以下這樣：

void f(param1, param2, ..., paramN) {
    stack = Empty Stack;
    push param1, param2, ..., paramN to stack

    loop {
       pop param1, param2, ..., paramN from stack, if pop nothing then break

       // do something

       push aaa, bbb, ..., nnn to stack // recursive call n
       // ...
       push aa, bb, ..., nn to stack // recursive call 2
       push a, b, ..., n to stack // recursive call 1
    }
}

這邊要注意的是，遞迴呼叫時傳入函數的參數有可能會是內容可變的(mutable)指標或是參考，此時就要注意資料改變的地方是否會去影響到其它的遞迴呼叫，如果會的話就要用不同的方式來實作了。尾端連續發生的遞迴呼叫可以允許夾雜是否要進行遞迴呼叫的判斷式。

快速排序法的實作方式就是這個型樣的典型例子。有關於快速排序法的介紹以及程式碼，可以參考這篇文章：

https://magiclen.org/quick-sort/

遞迴函數無回傳，遞迴呼叫只發生在前端

void f(param1, param2, ..., paramN) {
    if condition {
        f(a, b, ..., n); // recursive call
    }

    // do something
}

以上這種遞迴函數的結構也是最簡單的。我們可以先將函數主體分成兩個部份，第一個部份就是一開始發生的遞迴呼叫(包括是否要進行遞迴呼叫的條件式)，第二個部份就是遞迴呼叫完後續的部份。使第一部份自成一個迴圈，第二部份自成一個迴圈。在兩個迴圈的最上方，建立出一個堆疊空間。建立了堆疊空間後，把傳進遞迴函數的參數push到堆疊空間中(只需存會變化的參數)。

在第一部份的迴圈內，將遞迴呼叫的程式敘述改成把遞迴呼叫時的參數push到堆疊空間中，並直接修改參數。若遞迴呼叫的條件式無法成立，就跳出迴圈。

而在第二部份的迴圈內，一開始要先去pop堆疊空間中的參數，並用這些參數去做原本該做的事。若迴圈一開始無法從堆疊空間中pop到參數，就跳出迴圈。

所以之後形成的迭代函數看起來會像以下這樣：

void f(param1, param2, ..., paramN) {
    stack = Empty Stack;
    push param1, param2, ..., paramN to stack

    loop {
        if condition {
            push a, b, ..., n to stack // recursive call
            param1 = a, param2 = b, ..., paramN = n
        } else {
            break;
        }
    }

    loop {
       pop param1, param2, ..., paramN from stack, if pop nothing then break

       // do something
    }
}

遞迴函數無回傳，遞迴呼叫只連續發生在前端

void f(param1, param2, ..., paramN) {
    f(a, b, ..., n); // recursive call 1
    f(aa, bb, ..., nn); // recursive call 2
    // ...
    f(aaa, bbb, ..., nnn); // recursive call n

    // do something
}

我們可以先將函數主體分成兩個部份，第一個部份就是一開始連續發生的遞迴呼叫，第二個部份就是遞迴呼叫完後續的部份。使第一部份自成一個迴圈，第二部份自成一個迴圈。在兩個迴圈的最上方，建立出兩個堆疊空間。第一個堆疊空間要用來存放遞迴呼叫時，傳進函數的參數(只需存會變化的參數)。第二個堆疊空間則是要存放從第一個堆疊空間中取出來的參數(只需存第二部份會用到的參數)。建立了兩個堆疊空間後，把傳進遞迴函數的參數push到第一個堆疊空間中。

在第一部份的迴圈內，一開始要先去pop第一個堆疊空間中的這些參數，接著將遞迴呼叫的程式敘述都改成把遞迴呼叫時的參數push到堆疊空間中，最後再把參數push進第二個堆疊空間內。若迴圈一開始無法從第一個堆疊空間中pop到參數，就跳出迴圈。

而在第二部份的迴圈內，一開始要先去pop第二個堆疊空間中的參數，並用這些參數去做原本該做的事。若迴圈一開始無法從第二個堆疊空間中pop到參數，就跳出迴圈。

所以之後形成的迭代函數看起來會像以下這樣：

void f(param1, param2, ..., paramN) {
    stack1 = Empty Stack;
    stack2 = Empty Stack;
    push param1, param2, ..., paramN to stack1

    loop {
        pop param1, param2, ..., paramN from stack1, if pop nothing then break

        push a, b, ..., n to stack1 // recursive call 1
        push aa, bb, ..., nn to stack1 // recursive call 2
        // ...
        push aaa, bbb, ..., nnn to stack1 // recursive call n


        push param1, param2, ..., paramN to stack2
    }

    loop {
       pop param1, param2, ..., paramN from stack2, if pop nothing then break

       // do something
    }
}

這邊要注意的是，遞迴呼叫時傳入函數的參數有可能會是內容可變的指標或是參考，此時就要注意資料改變的地方是否會去影響到其它的遞迴呼叫，如果會的話就要用不同的方式來實作了。前端連續發生的遞迴呼叫可以允許夾雜是否要進行遞迴呼叫的判斷式。

不過我們其實比較不希望看到用兩個以上的堆疊空間來模擬遞迴的方式，若還有優化餘地，儘量還是將遞迴函數以一個堆疊空間來實作成迭代函數吧！

遞迴函數無回傳，遞迴呼叫只發生在前端和尾端

void f(param1, param2, ..., paramN) {
    if condition1 {
        f(a, b, ..., n); // recursive call 1
    }

    // do something

    if condition2 {
        f(aa, bb, ..., nn); // recursive call 2
    }
}

基本上看到尾端遞迴的部份，我們都可以用前面提過的方式先將它轉成迭代版本。轉換後看起來會像以下這樣：

void f(param1, param2, ..., paramN) {
    loop {
        if condition1 {
            f(a, b, ..., n); // recursive call 1
        }

        // do something

        if condition2 {
            param1 = aa, param2 = bb, ..., paramN = nn // recursive call 2
            continue;
        }

        break;
    }
}

再來就只剩下前端的遞迴呼叫了，雖然它現在出現在一層迴圈中，我們還是可以套用前面提過的方式來建立堆疊和新增迴圈。轉換後看起來會像以下這樣：

void f(param1, param2, ..., paramN) {
    stack = Empty Stack;

    'outer: loop {
        push param1, param2, ..., paramN to stack

        loop {
            if condition1 {
                push a, b, ..., n to stack // recursive call 1
                param1 = a, param2 = b, ..., paramN = n
            } else {
                break;
            }
        }

        loop {
            pop param1, param2, ..., paramN from stack, if pop nothing then break 'outer

            // do something

            if condition2 {
                param1 = aa, param2 = bb, ..., paramN = nn // recursive call 2
                continue 'outer;
            }
        }
    }
}

比較需要注意的是，第二部份的迴圈中如果堆疊空間已清空的話，是直接跳出外層的迴圈。且第二部份的迴圈中，因移除尾端遞迴而新增的continue關鍵字，其作用對象也是外層迴圈。原先因移除尾端遞迴而添加的迴圈，其中最後使用的break關鍵字就要移除掉，因為現在是依我們自己建立的堆疊空間來決定要不要繼續下一次的迭代。

其它

若遞迴函數的主體無法符合上述提到的型樣，可以多加理解該遞迴函數運作的原理，來進行迭代函數的轉換。

例如前面提到的二元搜尋樹，我們可以用以下的遞迴函數，來將二元搜尋樹的資料結構，轉成已排序好的陣列。

pub fn bt_flatten(node: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
    match node {
        Some(n) => {
            let mut nodes = bt_flatten(Node::get_left_child(n.clone()));

            nodes.push(n.borrow().value);
            nodes.extend_from_slice(&bt_flatten(Node::get_right_child(n)));

            nodes
        }
        None => vec![],
    }
}

觀察這個遞迴函數的行為，可以了解到它一開始會使用空的陣列，接著從二元樹最左邊的子節點開始將值放進陣列中。左邊子節點處理完之後就換右邊子節點，然後以右邊子節點為起始點尋找其下最左邊的子節點，如此循環。以下面這個二元搜尋樹為例：

        7
       / \
      /   \
     /     \
    /       \
   3         9
  / \       / \
 /   \     /   \
1     5   8     9
 \   / \
  2 4   6

從7開始找最左邊的子節點，找到1。將1放入陣列後，再看右邊的子節點2，2沒有子節點，將2放入陣列。再回到3這個節點，將3放入陣列後，再看右邊的子節點5。從5開始找最左邊的子節點，找到4，將4放入陣列。之後的步驟依此類推。

現在不要理會遞迴函數怎麼實作的，我們就使用一個堆疊空間，來創造出全新的迭代函數吧！

利用堆疊儲存往左搜尋時遇到的節點，當已經最左時，就將找到的節點值放進陣列中，並且再從右邊子節點開始找最左邊的節點，同樣地利用堆疊儲存過程中遇到的子節點。而堆疊存在的目的是要記錄待處理的節點。於是我們就可以井然有序地實作出以下迭代版本的函數：

pub fn bt_flatten(mut node: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
    let mut stack = vec![];
    let mut array = vec![];

    while let Some(n) = node.as_ref().cloned() {
        node = Node::get_left_child(n.clone());
        stack.push(n);
    }

    while let Some(n) = stack.pop() {
        array.push(n.borrow().value);

        node = Node::get_right_child(n.clone());

        while let Some(n) = node {
            node = Node::get_left_child(n.clone());
            stack.push(n);
        }
    }

    array
}

如何將遞迴函數改成迭代函數？

將遞迴函數改成迭代函數的流程

步驟一：理解遞迴函數

步驟二：將遞迴函數改為尾端遞迴

步驟三：用迴圈將遞迴函數的主體(Body)包起來

步驟四：將尾端遞迴呼叫的程式敘述改為直接修改函數參數的敘述，並加上continue關鍵字

步驟五：整理程式碼

更多的轉換例子

階乘(Factorial)函數

二元搜尋(Binary Search)

二元搜尋樹(BST, Binary Search Tree)的搜尋

遞迴關係式(Recurrence Relation)的另外轉換方式

步驟一：將遞迴呼叫的部份拆成子程序

步驟二：拆解子程序的程式敘述

步驟三：替子程序新增參數，使其可以透過參數傳入前項結果

步驟四：讓子程序除了回傳目前這項的計算結果外，也回傳計算下一項時會用到的參數

步驟五：現在，改用迴圈來呼叫子程序吧！

步驟六：整理程式碼

步驟七：將子程序內聯(inline)回原本的函數

步驟八：再次整理程式碼

更多的轉換例子

費氏數列

動態規劃

自行建立空間來模擬堆疊空間

遞迴函數無回傳，遞迴呼叫只連續發生在尾端

遞迴函數無回傳，遞迴呼叫只發生在前端

遞迴函數無回傳，遞迴呼叫只連續發生在前端

遞迴函數無回傳，遞迴呼叫只發生在前端和尾端

其它

步驟四：將尾端遞迴呼叫的程式敘述改為直接修改函數參數的敘述，並加上`continue`關鍵字