Sequència dinosaure X98947

Escriviu en Python una funció recursiva dinosaure(n) que donat un enter $n\ge{0}$ imprimeixi la seqüencia corresponent a $n$, segons el patró que es dedueix dels exemples següents:

dinosaure(0) -> 0
dinosaure(1) -> 01
dinosaure(2) -> 0120
dinosaure(3) -> 0120301
dinosaure(4) -> 012030140120
dinosaure(5) -> 01203014012050120301

Observació

Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

Afegiu com a comentaris al codi l’especificació de la funció i la resposta a les següents preguntes (aquesta part val un 20% de la nota d’aquest problema).

1. Quan es va resoldre el problemes de les Torres de Hanoi vam deduir una recurrència pel temps d’execució de l’estil $T(n) = 2T(n-1) + 1$
   Proposeu una recurrència del mateix estil per la longitud de la seqüència generada per dinosaure(n).

2. Quina serà la longitut de la seqüència generada per dinosaure(9)? Raoneu la resposta usant la recurrència proposada anteriorment.

                        /\               /\__                  
              /\       /  \             (  o \_                         
        /\   /  \     /    \     /\    (   ____)
  ___/\/  \_/    \_/\/      \_/\/  \__(    |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~