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. |
|
|
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:
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.
Exercicio:
- Onde está o proceso recursivo?. Fai un comentario nel
- Modifica os parámetros para que debuxe menos cadrados ou máis cadrados. Tes que decir o nº de cadrados exactos que vai debuxar.
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:
- Podes facelo con un bucle en vez de recursivo?. Proba en Scratch se queres facelo rápido.
- Modifica o número de intentos para que sexa infinito (ollo, con iso, logo tes que saber sair).
- 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).