Specjalne liczby - algorytm

Siedzę już od paru dni nad tym zadaniem, i nie mogę znaleźć jakiegoś sposobu na niego. Czy ma ktoś jakiś pomysł jak wyszukać takie liczby rekurencyjnie ? Bo chyba nie chodzi w tym zaadaniu by zrobić pełen przegląd liczb, chyba że się mylę.

 Specjalne liczby to liczby, w których cyfry (od 1 do 9) ustawione są w porządku nierosnącym (np 9999877777652, 542 itp)
oraz dodatkowo dwie cyfry stojące obok siebie są albo takie same albo mają różną parzystość
(zatem 9999877777652 jest specjalna, ale 542 już nie bo 4 i 2 stoją obok siebie i obie są parzyste).

Zadanie:

Część 1
Znajdź liczbę n-cyfrowych liczb specjalnych metodą rekurencyjną.
Obliczenia przeprowadź modulo 10000 aby uniknąć nadmiaru arytmetycznego.

Część 2
Rozwiąż to samo zadanie, tym razem używając programowania dynamicznego.

Część 3
Rozwiąż używając programowania dynamicznego uogólnioną wersję problemu. Tym razem nie liczymy liczby specjalnych liczb.
Funkcja jako parametr dostaje dodatkowo tablicę booli 9x9 (cały czas używamy cyfr 1 - 9).
W tej tablicy jeśli na pozycji [i, j] jest true to cyfra i + 1 może występować przed cyfrą j + 1,
jeśli na pozycji [i, j] jest false to nie może. 
Znajdź liczbę n-cyfrowych liczb spełniających wymogi zdefiniowane w tablicy booli.
Obliczenia przeprowadź modulo 10000 aby uniknąć nadmiaru arytmetycznego.

To może wróć do jakiegoś kursu:

fun(value,count)
  {
   if(count<=0) display(value);
   else
     {
      digit=value%10;
      fun(value*10+digit,count-1);
      for(--digit;digit>=0;digit-=2) fun(value*10+digit,count-1);
     }
  }