今日もLeetCodeのDaily Challengeをやりました.今日の問題は 「797. All Paths From Source to Target」でした.
閉路のない有向グラフにおいて,ある点からある点までのパスをすべて列挙しなさいという問題なんですが.
再帰を使って解こうと思ってこんなコードをかきました.
pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> { let mut answer: Vec<Vec<i32>> = vec![]; let n: i32 = graph.len() as i32; pub fn init_answer(path: Vec<i32>) -> () { // 再帰を使って answer を更新する } init_answer(vec![0]); return answer; }
答えをそのまま書くのはまずいかな?と思ったので概略だけですけど,なんとなくやりたいことは伝わってるんじゃないかと思います.
1: 関数は環境をキャプチャできない
ところがこれ,実行するとエラーになってしまうんですよね.
can't capture dynamic environment in a fn item
というエラーになります.要は関数 init_answer
の実行中に,環境中にある変数 answer
を利用することはできない,ということのようです.Rustでは関数は絶対に環境にある変数をキャプチャできません.
2: クロージャは再帰できない
そこでクロージャで書き直してみたんですが,またもやエラー.どうもドキュメントには書かれていないようなのですが,クロージャは再帰させることが(素直には)できないみたいです.
とても不便ですね.どうしてそんな仕様になっているのでしょうか.
仕方がないので,環境にある変数を参照で渡すように書き直しました.answer
は可変参照で,与えられるグラフ graph
は不変参照にします.
pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> { let mut answer: Vec<Vec<i32>> = vec![]; let n: i32 = graph.len() as i32; pub fn init_answer(path: Vec<i32>, graph: &Vec<Vec<i32>>, answer: &mut Vec<Vec<i32>>) -> () { // 再帰を使って answer にパスを詰めていく } init_answer(vec![0], &graph, &mut answer); return answer; }
これでようやく通りました.
クロージャで再帰ができないというのは不思議で,ただ不便なだけのように思えますね.何か意図があるのか….