редица на Purkiss

Числовата редица на  Purkiss (Purkiss sequence) съдържа естествени числа, съответстващи на броя движения при решаване на вид пъзел - китайски пръстени (baguenaudier), ако две едновременни движения на двата крайни пръстена се броят като едно. Представена е в в http://oeis.org/A051049 с рекурентна формула: a(n) = a(n-1) + 2*a(n-2) + 1. Съществува и редица на Lichtenberg, която се свързва със същата игра.

Съставете програма, чрез която се въвежда естествено число N от интервала [1..31] и се извеждат последователните числа от редица на Purkiss.  Програмата да използва две аналогични функции - рекурсия и итерация. Проверете друга рекурентна формула: a(0)=a(1)=1; a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) (подобна на използваната при описание числа на Трибоначи), дали извежда същите числа от тази редица.

Числата от редицата на Purkiss могат да бъдат разглеждани и като сума по ред в числовия триъгълник представен в http://oeis.org/A166692. Използваната формула е: T(n,k) = 2^(k-1), k>0. T(n,0) = (n+1) mod 2.

Описание за примерно приложение на подобен алгоритъм може да намерите на адреси:  https://en.wikipedia.org/wiki/Baguenaudier; http://mathworld.wolfram.com/Baguenaudier.html.

Разгледайте други основни типове примерни задачи, в чието решение се използват рекурсивни функции за извеждане на рекурентни редици. Прочетете допълнителен материал за ханойски кули, код на Грей, редица на Lichtenberg, игра на Wythoff, игра брюкселско зеле, ход на коня, ход на царицата, редица на Arima, редица на Alcuin.