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

Напишите функцию fib(n), которая по данному целому положительному n возвращает n-e число Фибоначчи. В этой задаче нельзя использовать циклы - используйте рекурсию.

Последовательность Фибоначчи определяется так:

F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2 …, F(n) = F(n−1) + F(n−2).

Что подается на вход

Вводится целое число n.

Что получается на выходе

Выводится ответ на задачу.