遞歸函數返回一個Vec

我繼續爲遞歸的概念掙扎。我有一個函數，它需要一個u64並返回該整數的因子Vec<u64>。我想在Vec的每個項目上遞歸地調用這個函數，返回一個扁平化的Vec，直到函數爲每個項目返回Vec<self>，即每個項目爲素數。遞歸函數返回一個Vec

fn prime_factors(x: u64) -> Vec<u64> { 
    let factors = factoring_method(x); 
    factors.iter().flat_map(|&i| factoring_method(i)).collect() 
}

（The complete code）

這僅返回的最後一次迭代的因素Vec，也沒有條件的，允許其繼續下去，直到項目都是素數。

factoring_method是我很滿意的廣場的一致性。我確定有很多優化的空間，但我希望在重構之前完成一個工作版本。我認爲這個遞歸應該在congruence_of_squares之內 - 自己調用Vec的每個成員，但是我不確定如何設置條件以防止它無限地執行。

來源

2017-09-20 Matthew Stevenson

其實，這是很難不說'factoring_method'回答。請提供[MCVE]。 –

'factoring_method'和'prime_factors'是否應該是相同的函數？ – sellibitze

@sellibitze - 沒有保理的方法是分開的，你遇到了Shepmaster指出的同樣的概念問題。我很抱歉沒有使用E_net4請求的代碼更新問題。生病了幾天。我會盡量在今天晚上更新以澄清。 –

有用的遞歸需要兩兩件事：

一個函數調用本身，無論是直接或間接的影響。
有一些終止的情況。一個數的因式分解的

一個定義是：

如果數字是素數，這是唯一的主要因素
否則，結合一對因素的首要因素數字

由此，我們可以確定終止條件（「如果它是素數」）和遞歸調用（「因素的主要因素」）。

請注意，我們還沒有編寫任何代碼 - 這一切都是概念性的。

然後，我們可以錄製的想法，防鏽：

fn prime_factors(x: u64) -> Vec<u64> { 
    if is_prime(x) { 
     vec![x] 
    } else { 
     factors(x).into_iter().flat_map(prime_factors).collect() 
    } 
}

有趣的作品在這裏：

我們使用into_iter以避免需要取消引用迭代值。
我們可以直接將函數名作爲閉包傳遞，因爲類型是對齊的。

一些（低效率）的輔助功能完善了實施：

fn is_prime(x: u64) -> bool { 
    !(2..x).any(|i| x % i == 0) 
} 

fn factors(x: u64) -> Vec<u64> { 
    match (2..x).filter(|i| x % i == 0).next() { 
     Some(v) => vec![v, x/v], 
     None => vec![], 
    } 
}

來源

2017-09-23 15:34:26 Shepmaster

遞歸函數返回一個Vec

回答

相關問題