Тренажёр: рекурсивные функции

У рекурсии всегда две части. База — случай, когда функция не вызывает себя и сразу возвращает значение. Рекурсивный шаг — вызов себя с меньшим аргументом. К примеру, $G(n)=2n$ при $n<10$ — база, а $G(n)=G(n-2)+1$ при $n\ge 10$ — шаг.

Каждый шаг уменьшает аргумент, пока он не попадёт в базу. Значит, значение большого аргумента считается от базы наверх: число шагов умножаем на добавку и прибавляем значение на базе. Например, $G(12)=G(10)+1=G(8)+2=16+2=18$.

Иногда шаг зависит от чётности аргумента: для чётного одно правило, для нечётного другое. Тогда просто идём от нужного аргумента к базе по подходящей строчке; много шагов удобно посчитать короткой программой.