> For the complete documentation index, see [llms.txt](https://educacion.gitbook.io/programacion/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://educacion.gitbook.io/programacion/ud3-introducion-a-programacion-orientada-a-obxectos/recursividade.md). # Recursividade A recursividade é unha técnica de resolución de problemas que se basen en descompoñer un problema en instancias máis pequenas de si mesmo. Pode verse como unha forma de modularización xa que descompone un problema en instancias máis pequenas. De esta forma, o problea está autocontido. Para a súa resolución defínese unha función que establece polo menos dous condicionais: * Un caso base: Que define a variante mais sinxela do problema, que habitualmente é a que remata a execución recursiva * Un caso xeral: Que é no que a función se chama a si mesma cun "problema" máis sinxelo que o da execución actual Exemplos de problemas que se poden resolver de maneira recursiva son o factorial dun número, a secuencia de Fibonacci ou se unha palabra é Palíndroma. ## Factorial como problema recursivo O factorial dun número enteiro non negativo ![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAA4AAAAhCAMAAADebGoAAAAAAXNSR0IArs4c6QAAAF1QTFRFAAAAAAAAAAA6AABmADpmADqQAGa2OgAAOjoAOjo6Oma2OpDbZgAAZrbbZrb/kDoAkDo6kLbbkNv/tmYAtmY6tv//25A625Bm27Zm2////7Zm/9uQ/9u2//+2///bRw7NoAAAAAF0Uk5TAEDm2GYAAAAJcEhZcwAAFiUAABYlAUlSJPAAAAAZdEVYdFNvZnR3YXJlAE1pY3Jvc29mdCBPZmZpY2V/7TVxAAAAZUlEQVQoU91QSRKAIAxrccEVXBFE+f8zLVXHk3fHnJo26QbwA9gCMwdWYjrTNUvlDKqpBYP5edwoSgWwXjRoDm66N0l0jUgSgpexGLQYmBqsOUn9uROrXq2sIs3WPfM8rdV/5ckH3yQEgYT4/pUAAAAASUVORK5CYII=), que se escribe como ![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABUAAAAhCAMAAAABIhAfAAAAAXNSR0IArs4c6QAAAGBQTFRFAAAAAAAAAAA6AABmADpmADqQAGa2OgAAOgA6OjoAOjo6Oma2OpDbZgAAZrbbZrb/kDoAkDo6kLbbkNv/tmYAtmY6tv//25A625Bm27Zm2////7Zm/9uQ/9u2//+2///bpOTVywAAAAF0Uk5TAEDm2GYAAAAJcEhZcwAAFiUAABYlAUlSJPAAAAAZdEVYdFNvZnR3YXJlAE1pY3Jvc29mdCBPZmZpY2V/7TVxAAAAjklEQVQoU9WS0Q6DIAxFqXNj0224yUSBzf//S0tLE01w7/aBwMm97YWg1MHLwqVwgz16L2gd/KHTDc5eTRrqIVkDGFzH1jswn6dyPJwplq0a3IUtnTs6ZxqvPUl/j1PqaNkqNOoknbuKREI5YdSYZFVszW2Fb9vm0WJFx/dlsL0EpPQRL/dOQ4svecjvsQBahwcbCodH8wAAAABJRU5ErkJggg==), é o produto de todos os números enteiros positivos desde 1 ata ![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAA4AAAAhCAMAAADebGoAAAAAAXNSR0IArs4c6QAAAF1QTFRFAAAAAAAAAAA6AABmADpmADqQAGa2OgAAOjoAOjo6Oma2OpDbZgAAZrbbZrb/kDoAkDo6kLbbkNv/tmYAtmY6tv//25A625Bm27Zm2////7Zm/9uQ/9u2//+2///bRw7NoAAAAAF0Uk5TAEDm2GYAAAAJcEhZcwAAFiUAABYlAUlSJPAAAAAZdEVYdFNvZnR3YXJlAE1pY3Jvc29mdCBPZmZpY2V/7TVxAAAAZUlEQVQoU91QSRKAIAxrccEVXBFE+f8zLVXHk3fHnJo26QbwA9gCMwdWYjrTNUvlDKqpBYP5edwoSgWwXjRoDm66N0l0jUgSgpexGLQYmBqsOUn9uROrXq2sIs3WPfM8rdV/5ckH3yQEgYT4/pUAAAAASUVORK5CYII=). Emprégase para calcular permutacións e combinacións, como o número de formas nas que se poden organizar obxectos. Por exemplo, ![](/files/LDFt9kburwCiuUkE8oMM). Dicimos que o problema está autocontenido, por que: 4! = 4 \* 3! = 4\*3\*2! = 4\*3\*2\*1! = 4\*3\*2\*1 = 24 Entonces en programación o que imos ter: ``` factorial(4) ↓ llama a factorial(3) factorial(3) ↓ llama a factorial(2) factorial(2) ↓ llama a factorial(1) factorial(1) → return 1 ← ¡CASO BASE! ↑ factorial(2) → return 2 * 1 = 2 ↑ factorial(3) → return 3 * 2 = 6 ↑ factorial(4) → return 4 * 6 = 24 ``` ```java public int factorial(int n){ if (n<0) return 0; else { if ((n==0)||(n==1)) //CASO BASE return 1; else //CASO RECURSIVO return n*factorial(n-1); } } ``` ## Contar cifras como problema recursivo Dado un número enteiro calquera, podese resolver o problema de contar cifras de forma recursiva: contarCifras (738) = 1 + contarCifras (73) = 1 + 1 + contarCifras(7) = 1 + 1 + 1 = 3 ```java public static int contarDigitos(int numero) throws Exception{ if (numero < 0) throw new Exception("Numero negativo"); if (numero < 10) return 1; else return 1 + contarDigitos(numero / 10); } ``` ## Cando usar a recursividade? {% hint style="warning" %} **Cando usar a recursividade** É especialmente útil cando: * O problema se define a si mesmo: factorial, fibbonacci, palíndromos, torres de Hanoi,... * A estrutura de datos empregada está definida como recursiva: * Á*rbores* * *Gráfos* * *Directorios* * Algoritmos de divide e vencerás (Quicksort, Mergesort) * Problemas de combinatoria ou backtracking (Laberintos, 8 Raiñas,.. ) {% endhint %} {% hint style="warning" %} **Cando NON é a mellor opción** * Hai moitas chamadas recursivas (pode causar *stack overflow*). * O problema é sinxelo de resolver cun bucle (`for` ou `while`). * A complexidade penaliza o rendemento (Fibbonacci complexidade O(2ⁿ) ⇒ Para n = 40 ⇒ 1.099.511.627.776 chamadas na pila) ``` int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } ``` * O código iterativo é máis eficiente e igual de claro {% endhint %} --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://educacion.gitbook.io/programacion/ud3-introducion-a-programacion-orientada-a-obxectos/recursividade.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.