ааа ну рекурсия это вызов функции самой себя некоторое количество раз.
общий принцип построения:
ОБЯЗАТЕЛЬНО условие выход из рекурсии
Тело рекурсии
Вызов этой же функции опять.
если "разложить" код приведенный выше для функции fib(3) то получим
"переменной" - "функции" после первого прохода возвращается
fib(3-1)+ fib(3 - 2) т.е. fib(2)+fib(1) после второго прохода
fib(2) переходит в fib(1) - fib(0) a fib(1) просто в 1
дальше
fib(1) -> 1 fib(0)-> 1 ну и 1
в общем у нас получается 3
проверяем
№ 0 1 2 3
числа фиб. 1 1 2 3
как видим мы посчитали реально не для 3-го элемента а для 4-го т.к. номера элементов начинаются с 0