Recursividade

Antes en Python :

  • Funcións.
  • Parámetros ou argumentos

Definimos a recursividade como unha función que se emprega a si mesma  na súa definición  (en lingua diríamos ser redundantes). Vexámolo cun exemplo:O proceso recursivo máis coñecido por calquera estudante é o factorial dun número N, que é igual a N multiplicado polo factorial de N-1 (sempre que N sexa positivo e non sexa 0 nin 1):

N! = N·(N-1)!

O proceso recursivo foi utilizar a verba factorial para definir outra vez factorial. Lingüísticamente non ten moito sentido, pero algorítmicamente permite resover cantidade de problemas complexos dun xeito máis compacto e eficaz. O proceso recursivo ten que rematar obrigatoriamente con unha definición, chamado paso base. No caso do factorial, por definición, 0! = 1. En resumo:

Función Definición Paso base
Factorial dun número N! = N·(N-1)! 0! = 1

Son moi famosos (falamos de nerds, claro ;-) os acrónimos recursivos, sendo o principal para calquera estudante de TIC o de GNU = "GNU Non é Unix". Tamén son interesante PHP, Lame, Wine, PIP en Python...

 

Conta atrás recursiva

A recursividade substitúe en xeral aos bucles, ou fainos máis compactos. Isto non implica que sexa mellor facer un algoritmo recursivo que un bucle, dependerá do problema concreto e a cantidade ou complexidade de datos a utilizar. Vexamos como substituir un bucle e unha variable por un proceso recursivo que fai unha conta atrás dende 10 ata 0:

  Scratch 2.0 - bucle (non recursivo) Scratch 2.0 - recursivo  
O bucle parte dunha variable en 10 e vai baixando un nº ata chegar a 0, e visualizamos os valores intermedios.

comando scratch input()

 

 

A función Conta_recursiva  (10) é igual a visualizar 10 + Conta_recursiva(9)

E volta a empezar: Conta_recursiva(9) é igual a visualizar 9 + Conta_recursiva(8)...

O resultado é o mesmo pero o proceso computacional é distinto. O que pode axudarte para entendelo é escribir secuencialmente a execución do programa, a saída, ou debuxar un diagrama cos pasos.

Vexamos o proceso recursivo en Python:

Comezo

 

Cadrado recursivo

Aquí temos unha función que debuxa un cadrado non pechado (utilizando un módulo ou biblioteca para debuxar, turtle) e que volve a debuxalo cada vez máis pequeno.

cadrado recursivo

Exercicio:

  1. Onde está o proceso recursivo?. Fai un comentario nel
  2. Modifica os parámetros para que debuxe menos cadrados ou máis cadrados. Tes que decir o nº de cadrados exactos que vai debuxar.

 

Comezo

De que cor é o cabalo branco de Santiago recursivamente?

Imos ver outro exemplo, con este simple xogo textual. Temos unha función, xogar(), que se chama a si mesma recursivamente. Establecemos 3 intentos para acertar.

Exercicio:

  1. Podes facelo con un bucle en vez de recursivo?. Proba en Scratch se queres facelo rápido.
  2. Modifica o número de intentos para que sexa infinito (ollo, con iso, logo tes que saber sair).
  3. Modifica o programa para que admita como respostas válidas 'Branco' e 'BRANCO' (busca a orde que permite transformar a resposta a todo maiúsculas ou todo minúsculas).

Comezo

Factorial Serie de Fibonacci Iteras ou recurres