Один из, если не самый часто задаваемый вопрос во время технического собеседования для многих программистов касается последовательности Фибоначчи. Почему ты спрашиваешь? Потому что последовательность Фибоначчи — отличный тест на понимание программистом рекурсии, вызовов функций, переменных, стека и многих других ключевых понятий, которые должен знать любой хороший программист.

При этом, скорее всего, вам зададут этот вопрос.

Используя рекурсию, найдите n-й элемент в последовательности Фибоначчи.

В этой статье я расскажу о двух отдельных методах решения этой проблемы: рекурсии и итерации.

Рекурсия

Важно понимать на самом базовом уровне, что такое рекурсия. Рекурсия — это, по сути, функция, вызывающая сама себя. Чтобы достичь ожидаемого конечного результата для этой проблемы, мы будем использовать хвостовую рекурсию, что означает, что вызывающая функция не выполняет вычисления после выполнения рекурсивного вызова.

Построчно, во-первых, мы определяем нашу функцию, которая принимает параметр: индекс в последовательности Фибоначчи, которую вы пытаетесь найти. Мы устанавливаем два случая для этой функции, базовый случай и рекурсивный случай.

Базовый случай гарантирует, что программа имеет условие, поэтому функция не работает бесконечно, вызывая переполнение стека. Рекурсивный случай будет выполняться непрерывно, пока не будет выполнен базовый случай.

По сути, именно так рекурсивная функция будет работать и оценивать аргумент, который вы передаете. Каждый раз, когда вы выполняете вызов функции, память выделяется для нее в стеке, где хранятся разные копии локальных переменных для каждого вызова. Как только базовый случай будет достигнут, функция будет возвращать значение, к которому она вызывается, пока мы не вернемся к самому первому вызову функции.

Теперь, когда мы рассмотрели рекурсивный подход, давайте взглянем на интерактивный подход.

Итерация

Есть поговорка, что «все, что можно сделать рекурсивно, можно сделать и с помощью цикла». Итерация может выполняться различными способами, включая циклы do, while, until и for.

В этом примере итерации у нас есть 3 переменные. Чтобы получить значение индекса, это число получается путем сложения двух предыдущих чисел. Мы устанавливаем i=2 в цикле for, потому что если вернуться к первым трем числам в последовательности Фибоначчи, значение индекса 2 равно 2.

Таким образом, в первой итерации цикла for мы создаем начальные 3 числа в последовательности Фибоначчи. С каждой итерацией мы устанавливаем каждой переменной соответствующие значения, пока не достигнем индекса. При попадании в индекс мы возвращаем значение по этому индексу.

Заключение

Хотя это часто задаваемый вопрос на собеседовании, лучше всего знать различные подходы, которые вы можете использовать для достижения одного и того же решения. Важно дать интервьюеру решение, используя метод, который они просят у вас, но показать им, что вы можете использовать разные методы, может иметь большое значение.

Я надеюсь, что это была информативная статья!