Решение
// Copyright 2023 Google LLC
// SPDX-License-Identifier: Apache-2.0
fn fib(n: u32) -> u32 {
if n < 2 {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
fn main() {
let n = 20;
println!("fib({n}) = {}", fib(n));
}Здесь мы используем синтаксис return, чтобы вернуть значения из функции. Позже в курсе мы увидим, что последнее выражение в блоке возвращается автоматически, и тогда ключевое слово return можно опускать ради более лаконичного стиля.
Условие if n < 2 не требует скобок, это стандартный стиль Rust.
Паника
В упражнении спрашивается, при каких условиях эта функция вызовет панику. Последовательность Фибоначчи растёт очень быстро. Для u32 вычисляемые значения превысят 32-битный предел (4 294 967 295), когда n достигнет 48.
В Rust арифметика целых проверяет переполнение в отладочном режиме (он используется по умолчанию при cargo run). Если переполнение происходит, программа паникует (аварийно завершается с сообщением об ошибке). В релизном режиме (cargo run --release) проверки переполнения по умолчанию отключены, и число «переходит» через границу (арифметика по модулю), что даёт неверный результат.
- Пройдите решение по шагам.
- Объясните рекурсивные вызовы и то, как они приводят к итоговому результату.
- Обсудите проблему переполнения целых. Для
u32функция вызовет панику примерно приn= 47. Можно показать это, изменив входное значение вmain. - Покажите итеративное решение как альтернативу и сравните его производительность и использование памяти с рекурсивным. Итеративное решение будет намного эффективнее.
Для дальнейшего изучения
Для более продвинутого обсуждения можно рассказать о мемоизации или динамическом программировании, чтобы оптимизировать рекурсивный расчёт Фибоначчи, хотя это выходит за рамки текущей темы.