\nLa cosa buffa \u00e8 che per\u00f2 \u00e8 relativamente semplice trovare spiegazioni sull’induzione, ma almeno per i matematici non ci sono cos\u00ec tante informazioni su un modo in un certo senso simile per risolvere i problemi matematici: la ricorsione<\/b>. La mia sensazione \u00e8 che la ricorsione era sempre stata usata dai matematici del passato, ma veniva considerata una tecnica di serie B e quindi snobbata nelle dimostrazioni “ufficiali”. Poi \u00e8 arrivata l’informatica, dove la ricorsione \u00e8 parecchio usata; di nuovo per\u00f2 i matematici pensano che una cosa usata dagli informatici non \u00e8 poi cos\u00ec importante… Ma lasciamo perdere queste disquisizioni, e vediamo come funziona la ricorsione.
\nTecnicamente la ricorsione consiste nel risolvere un problema P con dati in ingresso D riconducendosi alla risoluzione del problema P con dati in ingresso D’, dove i dati D’ sono “pi\u00f9 semplici” dei dati D. La frasetta magica “ricondursi al caso precedente” ricorre spesso nelle barzellette create dai fisici per prendere in giro i matematici; ma in questo caso la cosa \u00e8 piuttosto diversa, e molto pi\u00f9 seria. Ecco l’esempio canonico di ricorsione, tanto per mettere le cose pi\u00f9 in chiaro: il calcolo del fattoriale.
\nCome probabilmente ricordate, il fattoriale di un numero intero positivo n<\/i>, indicato con n<\/i>!, \u00e8 il prodotto dei numeri da 1 a n<\/i>. Per convenzione, 0! e 1! sono uguali a 1. Per calcolare n<\/i>! si pu\u00f2 appunto fare il prodotto dei numeri da 1 a n<\/i>, ma si pu\u00f2 anche operare in altro modo. Un informatico per esempio scriverebbe un programma la cui parte principale dice pi\u00f9 o meno cos\u00ec: “Per calcolare la funzione “fattoriale di n<\/i>“, chiamo la funzione “fattoriale di n<\/i>-1″ e moltiplico il risultato per n<\/i>.” Chi non \u00e8 abituato a queste cose fa un balzo sulla sedia: “Ma come fa questo qua a scrivere una cosa del genere? Com’\u00e8 possibile definire una funzione per mezzo di s\u00e9 stessa? Non si sovrappongono i pezzi?” Per quanto riguarda la struttura informatica, vi posso assicurare che non ci sono problemi: quello che viene richiamato non \u00e8 il programma inteso come archetipo ma una sua istanza<\/I>, insomma un suo clone. Il punto chiave \u00e8 che dobbiamo essere certi che il procedimento non si espenda all’infinito, oppure che a un certo punto si ritorni al punto di partenza ottenendo cos\u00ec un circolo vizioso. Ma per fortuna questo non \u00e8 il caso: il numero di cui si deve calcolare il fattoriale continua a ridursi, e prima o poi diventer\u00e0 1 (beh, ammesso che l’input sia stato un numero intero positivo. Ma quello del validare i dati in ingresso \u00e8 un altro tipo di problema: qui si fa matematica, non informatica). Ma noi sappiamo quanto vale il fattoriale di 1! (per la cronaca, quest’ultimo \u00e8 un punto esclamativo, non il simbolo di fattoriale), cio\u00e8 1. In definitiva, basta aggiungere il caso particolare; “Per calcolare la funzione “fattoriale di n<\/i>“, verifico se n<\/i>=1; in caso affermativo il risultato \u00e8 1, altrimenti, ecc. ecc.”.
\nNotata la differenza con l’induzione? L\u00ec partivamo da 1 e salivamo fino all’infinito, grazie al quinto postulato di Peano; qui partiamo da un numero qualunque e scendiamo fino a 1. C’\u00e8 per\u00f2 un altro punto che in genere viene trascurato. L’induzione parte da una formula chiusa, una cio\u00e8 dove basta infilare il numero e si ottiene il risultato; con la ricorsione non c’\u00e8 nulla del genere, e anzi trovare una formula chiusa a partire da quella ricorsiva non \u00e8 sempre cos\u00ec semplice. Tanto per fare un esempio pratico, prendiamo i numeri di Fibonacci. Come ricordate, la loro definizione \u00e8 ricorsiva: F1<\/sub> = F2<\/sub> = 1, e Fn<\/i>+1<\/sub> = Fn<\/i><\/sub> + Fn<\/i>-1<\/sub>. \u00c8 anche possibile avere una formula esplicita per l’n<\/i>-simo numero di Fibonacci:
\n
![\"[1\/sqrt(5)](\"https:\/\/i0.wp.com\/xmau.com\/notiziole\/files\/fibo.PNG\")
\ndove φ1<\/sub> \u00e8 (1+√5)\/2 e φ2<\/sub> \u00e8 (1-√5)\/2. Semplice, no? Vero che ce l’avevate sulla punta della lingua? D’accordo, questo \u00e8 forse un caso limite: ma in genere ci vuole comunque una certa arte per trovare la formula chiusa corrispondente a una formula ricorsiva.
\nNonostante tutto, per\u00f2, la ricorsione almeno a mio parere \u00e8 un modo pi\u00f9 naturale per trovare la soluzione di tutta una classe di problemi, e quindi dovrebbe essere sempre pronta nella borsa degli attrezzi di un matematico.<\/p>\n","protected":false},"excerpt":{"rendered":"
due parole sulla ricorsione, o come si pu\u00f2 definire una cosa per mezzo di s\u00e9 stessa.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[214],"tags":[],"class_list":["post-7805","post","type-post","status-publish","format-standard","hentry","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-21T","jetpack-related-posts":[{"id":7806,"url":"https:\/\/xmau.com\/notiziole\/2010\/04\/08\/fibonacci_e_la\/","url_meta":{"origin":7805,"position":0},"title":"Fibonacci e la ricorsione","author":".mau.","date":"2010-04-08","format":false,"excerpt":"Come (ri)dimostrare un teorema in maniera pi\u00f9 civile.","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7733,"url":"https:\/\/xmau.com\/notiziole\/2010\/03\/08\/linduzione_mate_1\/","url_meta":{"origin":7805,"position":1},"title":"L’induzione matematica [2\/2]","author":".mau.","date":"2010-03-08","format":false,"excerpt":"seconda parte delle spiegazioni sull'induzione matematica.","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":15754,"url":"https:\/\/xmau.com\/notiziole\/2017\/11\/12\/quizzino-della-domenica-ricorsione-mancata\/","url_meta":{"origin":7805,"position":2},"title":"Quizzino della domenica: ricorsione mancata","author":".mau.","date":"2017-11-12","format":false,"excerpt":"Fantastico! Un mio articolo sull'ipertraduzione nella tradizione iperuranica di Urania \u00e8 stato pubblicato su una Prestigiosa Rivista Ismiziana! Come potete immaginare, io non spiccico una parola di ismiziano, ma mi fido incondizionatamente del professor Tnak che ha gentilmente tradotto il testo. Volendo ringraziarlo, ho aggiunto in fondo all'articolo una nota:\u2026","rel":"","context":"In "giochi"","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2017\/11\/q282a.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":7732,"url":"https:\/\/xmau.com\/notiziole\/2010\/03\/05\/linduzione_mate\/","url_meta":{"origin":7805,"position":3},"title":"L’induzione matematica [1\/2]","author":".mau.","date":"2010-03-05","format":false,"excerpt":"che cos'\u00e8 l'induzione?","rel":"","context":"In "matematica_light"","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":28265,"url":"https:\/\/xmau.com\/notiziole\/2024\/02\/08\/matematica-cosa-ci-sara\/","url_meta":{"origin":7805,"position":4},"title":"MATEMATICA: cosa ci sar\u00e0","author":".mau.","date":"2024-02-08","format":false,"excerpt":"una panoramica ad alto livello della collana","rel":"","context":"In "io"","block_context":{"text":"io","link":"https:\/\/xmau.com\/notiziole\/category\/io\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/02\/piano.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":29434,"url":"https:\/\/xmau.com\/notiziole\/2024\/08\/07\/che-cosa-non-e-una-dimostrazione-elegante\/","url_meta":{"origin":7805,"position":5},"title":"Che cosa NON \u00c8 una dimostrazione elegante","author":".mau.","date":"2024-08-07","format":false,"excerpt":"Cominciamo dal fondo, insomma","rel":"","context":"In "mate-light-2024"","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"\"proof\"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/08\/%E2%80%94Pngtree%E2%80%94proof-text-effect-editable_6100719-300x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/7805","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=7805"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/7805\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=7805"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=7805"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=7805"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}