Числа Фибоначчи

Числа Фибоначчи — последовательность чисел, которая начинается следующим образом: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 и так далее. Эти числа получаются по следующему алгоритму:

• Начальное число ноль.
• Первое число один.
• Каждое следующее число — сумма двух предыдущих.

Напишите функцию fib, которая вычисляет произвольное N-е число Фибоначчи.

Пример

fib(6) // 8
fib(13) // 233
fib(30) // 832040

Подсказки

• Вам понадобится рекурсия. Подробнее о ней вы можете узнать из курса Введение в программирование. Не бойтесь другого языка. Важна концепция.