CS50 problem set 2+3 作業回顧

迴圈 (loop) 與遞回 (recursion)

pset2 作業 crack 本質上就是實作暴力解長度最多為 4 個字元的密碼，直覺上最快是直寫四個迴圈不斷產生a, b … z, aa, ab … 的字串做完 hash 後用 strcmp 比對 crypt 出的 hash 值，peusdo code：

for (int i = 'A' ; i <= 'z' ; i++ )
    {
        if (isalpha(i))  // 不懂資料結構前的寫法，畢竟中間不是英文的字不多
        比對 crypt(i, salt="50") 出來的值是否跟目標相同
        for (int j= 'A' ; i <= 'z' ; i++ )
        {
             ... 開始不動大腦重覆刻迴圈 ...
        }
    }

雖然直覺但應該有更簡潔的寫法，於是在 python 上實作一版遞迴

def alphabet_generator(plain_text, input_hash):
    先做一個可能字元的 list
    if 字串長度到最大值 (4個字元) 就回傳作完 Null (Base Case)
    elif 字串長度為零，base case
        把 list 每一個字元出來作 crypt 跟比較
    else 開始進遞回
        從 list 裡再撈一個字元跟進來的 plain_text 加在一起做 crypt 比較
        alphabet_generator(plain_text+j) 進遞迴繼續找 (Recursive Case)

目前對寫出一個有限遞迴的心得大概兩點：

1. Base case 要確保遞迴可以被結束
2. 進遞迴的參數要想清楚，可以產生預想的組合

pset3 其中一題是實作二分搜尋，在還不熟悉遞回寫法時，可能會寫出以下無效的方式

Bool Binary_search(int value, int values[], int start, int end);
Binary_search(…) {
…
Bool Found = Binary_search(int value, int values[], int start, int end); // recursion case
…
Return True; // found
…
Return False; // not found
}

遞迴函式沒有把回傳值放進去往下遞迴，在途中搜尋到也不會回值搜㝷成功，修改成下面的方式將回傳值代入即可：

Bool Binary_search(int value, int values[], int start, int end, bool found);

這樣一但搜尋成功就會一路將 True值傳上去。

下次寫卡很慘的 pset4 ，誤解作業要求卡五天最後發現其實不用作到太複雜

Reference

Recursive function: https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/recursion2.html