A. Числа Пелля

Числа Пелля заданы так: $P_1 = 1$, $P_2 = 2$, а при $k > 2$ выполнено $P_k = 2P_{k-1} + P_{k-2}$.

Напишите рекурсивную функцию, которая по числу $n$ вычисляет $P_n$.

Задача учебная: здесь важно правильно выделить базу и шаг. База — это те значения, которые известны сразу и дальше не раскладываются; шаг — выражение через меньшие. Если база забыта или неполна, рекурсия не остановится.

Одна строка содержит число $n$ ($1 \le n \le 30$).

Одно число — $P_n$.