Recursión:
en términos de programación, una función recursiva se puede definir como una rutina que se llama a sí misma directa o indirectamente.
Usando el algoritmo recursivo, ciertos problemas se pueden resolver con bastante facilidad. Towers of Hanoi (TOH) es uno de esos ejercicios de programación. Intente escribir un algoritmo iterativo para TOH. Además, todo programa recursivo se puede escribir usando métodos iterativos.
Matemáticamente, la recursividad ayuda a resolver algunos acertijos con facilidad.
Por ejemplo, una pregunta de entrevista de rutina,
en un grupo de N personas, cada persona estrechará su mano con otra persona solo una vez. En total, ¿cuántos apretones de manos se darían?
Solución:
Se puede resolver de diferentes formas; grafos, recursiones, etc. Veamos cómo se puede resolver recursivamente.
Hay N personas. Cada persona se da la mano entre sí una sola vez. Teniendo en cuenta a la N-ésima persona, tiene que darle la mano a (N-1) la persona. Ahora el problema se reduce a pequeños casos de (N-1) personas. Suponiendo que T N es un apretón de manos total, se puede formular recursivamente.
T N = (N-1) + T N-1 [T 1 = 0, es decir, la última persona ya les ha dado la mano a todos]
Resolviéndolo recursivamente se obtiene una serie aritmética, que se puede evaluar en N(N-1 )/2.
Ejercicio: En un grupo de N parejas, solo un género (ya sea masculino o femenino) puede dar la mano a todos. ¿Cuántos apretones de manos pasarían?
Por lo general, los programas recursivos dan como resultado una complejidad temporal deficiente. Un ejemplo es una serie de Fibonacci. La complejidad temporal de calcular el n-ésimo número de Fibonacci mediante la recursividad es de aproximadamente 1,6 n . Significa que la misma computadora toma casi un 60% más de tiempo para el siguiente número de Fibonacci. El algoritmo recursivo de Fibonacci tiene subproblemas superpuestos. Existen otras técnicas como la programación dinámica para mejorar dichos algoritmos superpuestos.
Sin embargo, algunos algoritmos (p. ej., ordenación por fusión, ordenación rápida, etc.) dan como resultado una complejidad de tiempo óptima utilizando la recursividad.
Caso base:
un requisito crítico de las funciones recursivas es el punto de terminación o caso base. Cada programa recursivo debe tener un caso base para asegurarse de que la función terminará. El caso base faltante da como resultado un comportamiento inesperado.
Diferentes formas de escribir funciones recursivas La
mayoría de nosotros conocemos al menos dos formas diferentes de escribir programas recursivos. A continuación se muestran las torres del código de Hanoi. Es un ejemplo de llamada directa.
C++
#include <bits/stdc++.h>
using namespace std;
// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole,
char destinationPole, char auxiliaryPole)
{
// Base case (termination condition)
if(0 == n)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
cout << "Move the disk "<< n << " from " <<
sourcePole <<" to "<< destinationPole << endl;
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n - 1, auxiliaryPole, destinationPole,
sourcePole);
}
// Driver code
int main()
{
tower(3, 'S', 'D', 'A');
return 0;
}
// This code is contributed by SHUBHAMSINGH10
C
#include<stdio.h>
// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole, char destinationPole, char auxiliaryPole)
{
// Base case (termination condition)
if(0 == n)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n-1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
printf("Move the disk %d from %c to %c\n",
n,sourcePole, destinationPole);
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n-1, auxiliaryPole, destinationPole,
sourcePole);
}
int main()
{
tower(3, 'S', 'D', 'A');
return 0;
}
Java
// Assuming n-th disk is
// bottom disk (count down)
class GFG {
static void tower(int n, char sourcePole,
char destinationPole, char auxiliaryPole)
{
// Base case (termination condition)
if (0 == n)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
System.out.printf("Move the disk %d from %c to %c\n",
n, sourcePole, destinationPole);
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
}
public static void main(String[] args)
{
tower(3, 'S', 'D', 'A');
}
}
// This code is contributed by Smitha Dinesh Semwal.
Python3
# Assuming n-th disk is
# bottom disk (count down)
def tower(n, sourcePole, destinationPole, auxiliaryPole):
# Base case (termination condition)
if(0 == n):
return
# Move first n-1 disks
# from source pole
# to auxiliary pole
# using destination as
# temporary pole
tower(n-1, sourcePole, auxiliaryPole, destinationPole)
# Move the remaining
# disk from source
# pole to destination pole
print("Move the disk",sourcePole,"from",sourcePole,"to",destinationPole)
# Move the n-1 disks from
# auxiliary (now source)
# pole to destination pole
# using source pole as
# temporary (auxiliary) pole
tower(n-1, auxiliaryPole, destinationPole,sourcePole)
# Driver code
tower(3, 'S', 'D', 'A')
C#
// Assuming n-th disk is bottom disk
// (count down)
using System;
class GFG {
static void tower(int n, char sourcePole,
char destinationPole,
char auxiliaryPole)
{
// Base case (termination condition)
if (0 == n)
return;
// Move first n-1 disks from source
// pole to auxiliary pole using
// destination as temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
Console.WriteLine("Move the disk " + n
+ "from " + sourcePole + "to "
+ destinationPole);
// Move the n-1 disks from auxiliary
// (now source) pole to destination
// pole using source pole as temporary
// (auxiliary) pole
tower(n - 1, auxiliaryPole,
destinationPole, sourcePole);
}
// Driver code
public static void Main()
{
tower(3, 'S', 'D', 'A');
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// Assuming n-th disk is
// bottom disk (count down)
function tower($n, $sourcePole,
$destinationPole,
$auxiliaryPole)
{
// Base case
// (termination condition)
if(0 == $n)
return;
// Move first n-1 disks
// from source pole to
// auxiliary pole using
// destination as temporary
// pole
tower($n - 1, $sourcePole,
$auxiliaryPole,
$destinationPole);
// Move the remaining
// disk from source
// pole to destination pole
echo "Move the disk ", $n,
" from ", $sourcePole,
" to ", $destinationPole,
"\n";
// Move the n-1 disks from
// auxiliary (now source)
// pole to destination pole
// using source pole as
// temporary (auxiliary) pole
tower($n - 1, $auxiliaryPole,
$destinationPole,
$sourcePole);
}
// Driver Code
tower(3, 'S', 'D', 'A');
// This code is contributed by Ajit.
?>
Javascript
<script>
// Assuming n-th disk is bottom disk (count down)
function tower(n, sourcePole,
destinationPole, auxiliaryPole)
{
// Base case (termination condition)
if(0 == n)
return;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
document.write("Move the disk " + n + " from " +
sourcePole + n + " to " + destinationPole + "<br>");
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n - 1, auxiliaryPole, destinationPole,
sourcePole);
}
// Driver code
tower(3, 'S', 'D', 'A');
// This code is contributed by Manoj
</script>
Producción:
Move the disk 1 from S to D Move the disk 2 from S to A Move the disk 1 from D to A Move the disk 3 from S to D Move the disk 1 from A to S Move the disk 2 from A to D Move the disk 1 from S to D
La complejidad temporal de TOH se puede calcular formulando el número de movimientos.
Necesitamos mover los primeros discos N-1 de Origen a Auxiliar y de Auxiliar a Destino, es decir, el primer disco N-1 requiere dos movimientos. Un movimiento más del último disco de Origen a Destino. Matemáticamente, se puede definir recursivamente.
M N = 2M N-1 + 1.
Podemos resolver fácilmente la relación recursiva anterior (2 N -1), que es exponencial.
Llamada indirecta. Aunque menos práctico, una función [funA()] puede llamar a otra función [funB()] que a su vez llama a [funA()] la función anterior. En este caso, ambas funciones deben tener el caso base.
Programación defensiva:
podemos combinar técnicas de codificación defensivas con recursividad para la funcionalidad elegante de la aplicación. Por lo general, la programación recursiva no está permitida en aplicaciones críticas para la seguridad, como controles de vuelo, monitoreo de salud, etc. Sin embargo, se puede usar una técnica de conteo estático para evitar llamadas no controladas (NO en sistemas críticos para la seguridad, pero se puede usar en soft). sistemas en tiempo real).
C++
void recursive(int data)
{
static callDepth;
if(callDepth > MAX_DEPTH)
return;
// Increase call depth
callDepth++;
// do other processing
recursive(data);
// do other processing
// Decrease call depth
callDepth--;
}
// This code is contributed by rutvik_56
C
void recursive(int data)
{
static callDepth;
if(callDepth > MAX_DEPTH)
return;
// Increase call depth
callDepth++;
// do other processing
recursive(data);
// do other processing
// Decrease call depth
callDepth--;
}
Java
static void recursive(int data)
{
static callDepth;
if(callDepth > MAX_DEPTH)
return;
// Increase call depth
callDepth++;
// do other processing
recursive(data);
// do other processing
// Decrease call depth
callDepth--;
}
// This code is contributed by divyeh072019
Python3
def recursive(data): callDepth = 0 if(callDepth > MAX_DEPTH): return; # Increase call depth callDepth+=1 # do other processing recursive(data); # do other processing # Decrease call depth callDepth -= 1 # This code is contributed by Pratham76
C#
static void recursive(int data)
{
static callDepth;
if(callDepth > MAX_DEPTH)
return;
// Increase call depth
callDepth++;
// do other processing
recursive(data);
// do other processing
// Decrease call depth
callDepth--;
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
//Javascript Implementation
function recursive(data)
{
const callDepth = 0;
if(callDepth > MAX_DEPTH)
return;
// Increase call depth
callDepth++;
// do other processing
recursive(data);
// do other processing
// Decrease call depth
callDepth--;
}
// This code is contributed by shubhamsingh10
</script>
La profundidad de callDepth depende del tamaño del marco de la pila de funciones y del tamaño máximo de la pila.
La recursividad también se puede implementar con punteros de función. Un ejemplo es un controlador de señal en sistemas compatibles con POSIX. Si el controlador hace que se active el mismo evento debido al cual se llama al controlador, la función volverá a ingresar.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA