Будет ли функция Фибоначчи корректно выполнена в Android с учетом синхронизации

Что проверяют

Вопрос почти всегда идёт к конкретному куску кода: рекурсивный fib, помеченный synchronized или с общим кэшем, который вызывают из нескольких потоков. Проверяют, видите ли вы сразу четыре вещи: дедлок, гонку, переполнение типа и блокировку главного потока. Следом просят переписать функцию так, чтобы она была и быстрой, и потокобезопасной.

Как отвечать

Разберите код по пунктам:

• повторный захват монитора: рекурсивный synchronized-метод не зависнет, мониторы в JVM и ART реентерабельны, поток повторно входит в свой же замок. Но все потоки выстроятся в очередь, и параллельности не будет;
• корутины: Mutex из kotlinx.coroutines нереентерабелен. Рекурсивная функция, которая берёт тот же Mutex внутри withLock, зависнет навсегда;
• общий кэш: мемоизация в обычном HashMap из нескольких потоков это гонка и порча структуры. ConcurrentHashMap помогает, но рекурсивный computeIfAbsent на нём нарушает контракт метода: в зависимости от версии получите IllegalStateException или зависание;
• переполнение: Int переполняется уже на fib(47), Long на fib(93). Дальше нужен BigInteger, иначе результат молча становится отрицательным;
• главный поток: наивная рекурсия растёт экспоненциально, fib(45) это больше миллиарда вызовов. Если главный поток 5 секунд не отвечает на ввод, система покажет ANR.

Правильный ответ: итеративная версия за O(n) на локальных переменных. Общего состояния нет, синхронизация не нужна вообще. Считать в фоне через withContext(Dispatchers.Default) из viewModelScope, а не через AsyncTask, который устарел в API 30.

Где спотыкаются

Отвечают «будет дедлок» на рекурсивный synchronized. Для Java это неверно, зато верно для Mutex в корутинах, и путать их нельзя.

Пугают переполнением стека при fib(50). Глубина рекурсии равна n, пятьдесят кадров стек выдержит легко. Проблема в числе вызовов, а не в глубине.

Навешивают synchronized на всё подряд вместо того, чтобы убрать общее состояние. Функция без разделяемых данных потокобезопасна сама по себе.