Recursivitat ============ Vegeu els conceptes, les referències i els exercicis al tema :ref:`recursivitat` dins del material de l'assignatura. Tipus de problemes ------------------ Fòrmules recursives ~~~~~~~~~~~~~~~~~~~ - Definir una funció en Python a partir d'una fòrmula matemàtica recursiva: funció, eqüació, successió, sèrie... - Només cal fer un canvi de llenguatge: de notació matemàtica a Python. Exemples ++++++++ - Funcions que calculen nombres naturals - :doc:`inf:temes/recursivitat/Factorial/index` - :doc:`inf:temes/recursivitat/Nombre_combinatori/index` - :doc:`inf:temes/recursivitat/Màxim_comú_divisor/index` - Funcions que calculen els termes d'una successió - :doc:`inf:temes/recursivitat/Enumeració_dels_punts_del_primer_quadrant/index` - :doc:`inf:temes/recursivitat/Fibonacci/index` - :doc:`inf:temes/recursivitat/Recaman_seq_alt/index` - Funcions que generen llistes - :doc:`inf:temes/recursivitat/Llista_de_nombres_quadrats/index` - :doc:`inf:temes/recursivitat/Calamarsa/index` - :doc:`inf:temes/recursivitat/Recaman/index` - Funcions en què les dades són llistes - :doc:`inf:temes/recursivitat/Corbes_de_Bézier/index` Algorismes recursius ~~~~~~~~~~~~~~~~~~~~ - Definir una funció en Python a partir d'un algorisme recursiu. - Cal saber expressar l'algorisme en Python. Exemples ++++++++ - :doc:`inf:temes/recursivitat/Arrel_digital/index` - :doc:`inf:temes/recursivitat/Bisecció/index` - Funció :func:`~cercadic.es_en_llista` de :doc:`inf:temes/recursivitat/Cerca_dicotòmica/index` - :doc:`inf:temes/recursivitat/La_Corba_C_de_Lévy/index` - :doc:`inf:temes/recursivitat/Quadtree/index` - :doc:`inf:temes/recursivitat/Triangle_de_Sierpinski/index` - Funció :ref:`hi_es ` - Funció :ref:`ho_es ` Seqüències ~~~~~~~~~~ - L'estratègia més sencilla per reduir una seqüència és calcular-ne una llesca sense un dels elements. - Els elements més fàcils de descartar són el primer i l'últim. - `Esquemes recursius sobre seqüències`_. Exemples ++++++++ - Aplica - :func:`positius.positius_1` - Filtra - Sintetitza - :func:`~mes_no_nuls.mes_no_nuls` de :doc:`inf:temes/recursivitat/Polinomi_amb_més_coeficients_no_nuls/index`, màxim amb clau :func:`~mes_no_nuls.nombre_no_nuls` - :doc:`inf:temes/recursivitat/Cerca_la_paraula_amb_més_a_s/index` .. - Mínim: `mesCurta `__ - Cerca - Índex del primer element desordenat - Llista ordenada creixentment - Combinacions - Enumera, filtra i aplica: `indexos `__ - Intèrval i suma: :doc:`inf:temes/recursivitat/Suma_d_un_tros/index` - Finestres - Funció diferencies de `diferencies `__ - Cal definir l'algorisme recursiu - :doc:`inf:temes/recursivitat/Cap_i_cua/index` Immersió ~~~~~~~~ - Tècnica de disseny recursiu. - Imprescindible quan no sabem reduir cap dels paràmetres de la funció original. - Consisteix en definir una nova funció més general (*funció immersora*), que té més paràmetres. - La funció immersora calcula el mateix resultat que la funció original quan es crida amb alguns valors dels arguments que es corresponen als nous paràmetres. Immersió d'eficiència en seqüències +++++++++++++++++++++++++++++++++++ - Evita generar llesques de la llista original. - Afegeix un paràmetre de tipus :class:`range`. - Les llesques es fan sobre el nou paràmetre en comptes de la llista. - Immersió en `esquemes recursius sobre seqüències`_. Vegeu al `Python Tutor `_ la solució de l'esquema sintetitza `basada en llesques`__ i contrasteu-la amb la solució amb la `tècnica d'immersió`__. __ https://pythontutor.com/render.html#code=def%20sintetitza_1%28acumula,%20seq,%20neutre%29%3A%0A%20%20%20%20if%20len%28seq%29%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20r%20%3D%20neutre%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20r_0%20%3D%20sintetitza_1%28acumula,%20seq%5B%3A-1%5D,%20neutre%29%0A%20%20%20%20%20%20%20%20r%20%3D%20acumula%28r_0,%20seq%5B-1%5D%29%0A%20%20%20%20return%20r%0A%0Afrom%20operator%20import%20mul%0A%0Ap%20%3D%20sintetitza_1%28mul,%20%5B3,%201,%204,%202%5D,%201%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false __ https://pythontutor.com/render.html#code=def%20sintetitza_2%28acumula,%20seq,%20neutre%29%3A%0A%20%20%20%20return%20sintetitza_2_i%28acumula,%20seq,%20neutre,%20range%28len%28seq%29%29%29%0A%0Adef%20sintetitza_2_i%28acumula,%20seq,%20neutre,%20llesca%29%3A%0A%20%20%20%20if%20len%28llesca%29%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20r%20%3D%20neutre%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20r_0%20%3D%20sintetitza_2_i%28acumula,%20seq,%20neutre,%20llesca%5B%3A-1%5D%29%0A%20%20%20%20%20%20%20%20r%20%3D%20acumula%28r_0,%20seq%5Bllesca%5B-1%5D%5D%29%0A%20%20%20%20return%20r%0A%0Afrom%20operator%20import%20mul%0A%0Ap%20%3D%20sintetitza_2%28mul,%20%5B3,%201,%204,%202%5D,%201%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false .. heapPrimitives=true per veure tots els objectes al heap Exemples ++++++++ - Immersió d'eficiència en seqüències .. - Exercicis d'examen: `totvocals `__. - Solucions: `totvocals `__. - El resultat de la funció és un índex d'una seqüència - Funció :func:`~cercadic.index_llista` de :doc:`inf:temes/recursivitat/Cerca_dicotòmica/index` - Immersió imprescindible quan cap paràmetre es pot reduir - :doc:`inf:temes/recursivitat/Divisors_d_un_nombre_enter/index` - Immersió imprescindible en seqüències sense llesques - :doc:`inf:temes/recursivitat/Horner/index` - :doc:`inf:temes/recursivitat/Polinomi_amb_més_coeficients_no_nuls/index` - :doc:`inf:temes/recursivitat/Paquets/index` - Immersió en matrius - Decidir si una matriu és simètrica - :doc:`inf:temes/recursivitat/Quadtree/index` Dades recursives ~~~~~~~~~~~~~~~~ - `Tipus de dades recursius `__. Exemples ++++++++ - :doc:`inf:temes/recursivitat/Aplanar_una_llista/index` - :doc:`inf:temes/recursivitat/Arbres_d_Intervals/index` - :doc:`inf:temes/recursivitat/Quadtree/index` - :doc:`inf:examens/curs2015-2016/2/reava/recursivitat-2` - :doc:`inf:examens/curs2018-2019/1/extra/recursivitat` Funcions modificadores ~~~~~~~~~~~~~~~~~~~~~~ - També poden ser recursives. - Cal immersió per les funcions modificadores sobre seqüències. Exemples ++++++++ - Funció :func:`~positius.positius_2` - Recorregut en profunditat d'una graf Iteradors ~~~~~~~~~ - Les funcions que reben o calculen iteradors finits poden ser recursives. - Vegeu els `esquemes recursius sobre iteradors`_. Tipus de recursivitat --------------------- Recursivitat multiple ~~~~~~~~~~~~~~~~~~~~~ - Funció recursiva *lineal* o *simple*: per resoldre el cas recursiu, només cal que es cridi un cop a ella mateixa. - Funció recursiva *múltiple*: per resoldre el cas recursiu, cal cridar-la més d'un cop. Exemples ++++++++ - :doc:`inf:temes/recursivitat/Aplanar_una_llista/index` - :doc:`inf:temes/recursivitat/Fibonacci/index` - :doc:`inf:temes/recursivitat/Quadtree/index` - Funció :ref:`hi_es ` Recursivitat final ~~~~~~~~~~~~~~~~~~ - Funció recursiva lineal *final*: retorna directament el resultat de la crida recursiva. Exemples ++++++++ - :doc:`inf:temes/recursivitat/Arrel_digital/index` - :doc:`inf:temes/recursivitat/Fibonacci/index` - :doc:`inf:examens/curs2015-2016/2/reava/recursivitat-2` - Funció :ref:`ho_es ` .. `negatiu `__, `divina `__, `red_dif `__, `negatiu `__, `divina `__, `red_dif `__, Recursivitat estructural ~~~~~~~~~~~~~~~~~~~~~~~~ - Funcions recursives amb paràmetres o resultats que són `dades recursives`_. Recursivitat indirecta ~~~~~~~~~~~~~~~~~~~~~~ - Funció recursiva *directa*: la funció es crida a ella mateixa. - Funció recursiva *indirecta*: la funció no es crida a ella mateixa sinó que ho fa una altra funció a qui ha cridat. Esquemes recursius sobre seqüències ----------------------------------- .. toctree:: esquemes/aplica esquemes/filtra esquemes/sintetitza Esquemes recursius sobre iteradors ---------------------------------- .. toctree:: esquemes/iaplica esquemes/ifiltra esquemes/isintetitza