從遞歸函數提前退出時返回什麼？

我有一個家庭作業，我需要計算兩個字符串之間的編輯距離。我得到了初始功能的工作，但我一直有這個部分的問題從遞歸函數提前退出時返回什麼？

現在添加截斷到編輯距離。這不應該改變產生的結果，但會大大加快性能。

這是我原來的功能：

static unsigned int compute_edit_distance(const char *const a, 
             const char *const b) 
{ 
    if (strcmp(a, b) == 0) return 0; 
    if (a[0] == '\0') return strlen(b); 
    if (b[0] == '\0') return strlen(a); 

    unsigned int remove_from_a = 
     compute_edit_distance(a + 1, b) + 1; 
    unsigned int remove_from_b = 
     compute_edit_distance(a, b + 1) + 1; 

    unsigned int remove_from_both = 
     compute_edit_distance(a + 1, b + 1); 
    if (tolower(a[0]) != tolower(b[0])) ++remove_from_both; 

    return get_min(get_min(remove_from_a, remove_from_b), 
       remove_from_both); 
}

我已經嘗試了一些東西，但他們沒有工作。我的最新的變化是這樣的

if (depth == MAX_EDIT_DISTANCE_DEPTH) 
{ 
    size_t a_length = strlen(a); 
    size_t b_length = strlen(b); 
    size_t max_length = (a_length > b_length) ? a_length : b_length; 
    return MAX_EDIT_DISTANCE_DEPTH + max_length; 
}

一個新的函數簽名

static unsigned int compute_edit_distance(const char *const a, 
             const char *const b, unsigned int depth)

但這並不工作。

我可以得到一個關於如何做到這一點的提示嗎？謝謝！

來源

2012-07-15 Eva

什麼是截斷？ – Rndm 2012-07-15 06:20:29

@ user1416970您從遞歸函數中早期返回的情況，因爲您知道您不會從遞歸獲得任何東西。 – quasiverse 2012-07-15 06:22:09

這必須做點事情。你是否正確地將「深度」傳遞給函數？ – 2012-07-15 06:30:38

最簡單的方法是將「深度剩餘」作爲參數傳入。也就是說，第一次調用會通過截止深度，所有遞歸調用都會傳遞一個較小的數字，您可以通過編輯的類型來確定這個數字。

最基本的想法是，在你的第一個解決方案中，深度是在分支被遞歸探索之後計算的。也就是說，這些呼叫都是在分支上完成的，然後在返回分支時將這些號碼加在一起。

您仍然可以這樣做來計算深度，但爲了防止分支變得太遠，您可以傳入您在分支中途中調用時已使用的編輯預算的總計運行總數，或等價地編輯預算仍然存在。

你需要一些技巧來從失敗的分支傳回一個數字，以確保該數字將被拒絕。例如，返回一個你知道的數字太大，然後檢查結果。例如，返回MAX_DEPTH + 1或類似的。

來源

2012-07-15 07:05:55 UncleO

我上面的失敗解決方案做了類似的事情，但不是返回一個常量，值取決於字符串的大小。（我認爲尺寸可能會影響編輯距離。）我嘗試將其更改爲常量，並打印出一組不同的錯誤值。 – Eva 2012-07-15 07:25:03

你沒有向我們展示如何減少深度預算，這是關鍵部分。您返回的價值不應該從原來的解決方案中改變太多。 – UncleO 2012-07-15 07:30:53

「減少深度預算」是什麼意思？在我的遞歸調用中深度參數是什麼？我只是加1到深度。 – Eva 2012-07-15 07:37:15

從遞歸函數提前退出時返回什麼？

回答

相關問題