¿Qué es la recursividad ?
El proceso en el que una función se llama a sí misma directa o indirectamente se llama recursividad y la función correspondiente se llama función recursiva. Usando el algoritmo recursivo, ciertos problemas se pueden resolver con bastante facilidad. Ejemplos de tales problemas son Towers of Hanoi (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS of Graph , etc.
Tipos de recurrencias :
Las recurrencias son principalmente de dos tipos dependiendo de si una función se llama a sí misma desde dentro de sí misma o más de una función se llama entre sí. La primera se llama recursión directa y la otra se llama recursión indirecta . Así, los dos tipos de recursividad son:
1. Recursión directa : se pueden clasificar en cuatro tipos :
- Tail Recursion : si una función recursiva se llama a sí misma y esa llamada recursiva es la última declaración en la función, entonces se conoce como Tail Recursion. Después de esa llamada, la función recursiva no realiza nada. La función tiene que procesar o realizar alguna operación en el momento de la llamada y no hace nada en el momento de la devolución.
Ejemplo:
C++
// Code Showing Tail Recursion
#include <iostream>
using namespace std;
// Recursion function
void fun(int n)
{
if (n > 0) {
cout << n << " ";
// Last statement in the function
fun(n - 1);
}
}
// Driver Code
int main()
{
int x = 3;
fun(x);
return 0;
}
// This code is contributed by shubhamsingh10
C
// Code Showing Tail Recursion
#include <stdio.h>
// Recursion function
void fun(int n)
{
if (n > 0) {
printf("%d ", n);
// Last statement in the function
fun(n - 1);
}
}
// Driver Code
int main()
{
int x = 3;
fun(x);
return 0;
}
Java
// Java code Showing Tail Recursion
class GFG {
// Recursion function
static void fun(int n)
{
if (n > 0)
{
System.out.print(n + " ");
// Last statement in the function
fun(n - 1);
}
}
// Driver Code
public static void main(String[] args)
{
int x = 3;
fun(x);
}
}
// This code is contributed by pratham76.
Python3
# Code Showing Tail Recursion # Recursion function def fun(n): if (n > 0): print(n, end=" ") # Last statement in the function fun(n - 1) # Driver Code x = 3 fun(x) # This code is contributed by Shubhamsingh10
C#
// C# code Showing Tail Recursion
using System;
class GFG
{
// Recursion function
static void fun(int n)
{
if (n > 0)
{
Console.Write(n + " ");
// Last statement in the function
fun(n - 1);
}
}
// Driver Code
public static void Main(string[] args)
{
int x = 3;
fun(x);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript code Showing Tail Recursion
// Recursion function
function fun(n)
{
if (n > 0)
{
document.write(n + " ");
// Last statement in the function
fun(n - 1);
}
}
// Driver Code
var x = 3;
fun(x);
// This code is contributed by shivanisinghss2110
</script>
3 2 1
Entendamos el ejemplo rastreando el árbol de la función recursiva. Así es como se hacen las llamadas y así se producen las salidas.
Complejidad de tiempo para recurrencia de cola: O(n)
Complejidad de espacio para recurrencia de cola: O(n)
Nota: Complejidad de tiempo y espacio se proporciona para este ejemplo específico. Puede variar para otro ejemplo.
Ahora, convirtamos Tail Recursion en Loop y comparemos entre sí en términos de Complejidad de tiempo y espacio y decidamos cuál es más eficiente.
C++
// Converting Tail Recursion into Loop
#include <iostream>
using namespace std;
void fun(int y)
{
while (y > 0) {
cout << y << " ";
y--;
}
}
// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}
//This Code is contributed by Shubhamsingh10
C
// Converting Tail Recursion into Loop
#include <stdio.h>
void fun(int y)
{
while (y > 0) {
printf("%d ", y);
y--;
}
}
// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}
Java
// Converting Tail Recursion into Loop
import java.io.*;
class GFG
{
static void fun(int y)
{
while (y > 0) {
System.out.print(" "+ y);
y--;
}
}
// Driver code
public static void main(String[] args)
{
int x = 3;
fun(x);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Converting Tail Recursion into Loop def fun(y): while (y > 0): print(y , end = " ") y -= 1 # Driver code x = 3 fun(x) # This Code is contributed by shivanisinghss2110
C#
// Converting Tail Recursion into Loop
using System;
class GFG
{
static void fun(int y)
{
while (y > 0) {
Console.Write(" "+ y);
y--;
}
}
// Driver code
public static void Main(String[] args)
{
int x = 3;
fun(x);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
function fun(y)
{
while (y > 0) {
document.write(" "+ y);
y--;
}
}
// Driver code
var x = 3;
fun(x);
// This code is contributed by shivanisinghss2110
</script>
3 2 1
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)
Nota: Complejidad de tiempo y espacio se proporciona para este ejemplo específico. Puede variar para otro ejemplo.
Entonces, se vio que en el caso de bucle, la Complejidad espacial es O (1), por lo que era mejor escribir código en bucle en lugar de recurrir a la cola en términos de Complejidad espacial, que es más eficiente que la recursión a la cola.
¿Por qué la complejidad del espacio es menor en el caso del bucle?
Antes de explicar esto, supongo que está familiarizado con el conocimiento de cómo se almacenan los datos en la memoria principal durante la ejecución de un programa. En resumen, cuando se ejecuta el programa, la memoria principal se divide en tres partes. Una parte para la sección de código, la segunda es la memoria de montón y otra es la memoria de pila. Recuerde que el programa puede acceder directamente solo a la memoria de la pila, no puede acceder directamente a la memoria del montón, por lo que necesitamos la ayuda del puntero para acceder a la memoria del montón.
Ahora entendamos por qué la complejidad del espacio es menor en el caso del bucle.
En caso de bucle, cuando la función «(void fun(int y))» se ejecuta allí, solo se crea un registro de activación en la memoria de la pila (registro de activación creado solo para la variable ‘y’), por lo que solo se necesita ‘una’ unidad de memoria dentro de la pila, por lo que su complejidad de espacio es O (1) pero en el caso de la función recursiva cada vez que se llama a sí mismo para cada llamada, se crea un registro de activación separado en la pila. Entonces, si hay ‘n’ no de llamada, entonces toma ‘n’ unidad de memoria dentro de la pila entonces su complejidad espacial es O(n).
- Head Recursion : si una función recursiva se llama a sí misma y esa llamada recursiva es la primera declaración en la función, entonces se conoce como Head Recursion. No hay declaración, no hay operación antes de la llamada. La función no tiene que procesar ni realizar ninguna operación en el momento de la llamada y todas las operaciones se realizan en el momento de la devolución.
Ejemplo:
C++
// C++ program showing Head Recursion
#include <bits/stdc++.h>
using namespace std;
// Recursive function
void fun(int n)
{
if (n > 0) {
// First statement in the function
fun(n - 1);
cout << " "<< n;
}
}
// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// C program showing Head Recursion
#include <stdio.h>
// Recursive function
void fun(int n)
{
if (n > 0) {
// First statement in the function
fun(n - 1);
printf("%d ", n);
}
}
// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}
Java
// Java program showing Head Recursion
import java.io.*;
class GFG{
// Recursive function
static void fun(int n)
{
if (n > 0) {
// First statement in the function
fun(n - 1);
System.out.print(" "+ n);
}
}
// Driver code
public static void main(String[] args)
{
int x = 3;
fun(x);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python program showing Head Recursion # Recursive function def fun(n): if (n > 0): # First statement in the function fun(n - 1) print(n,end=" ") # Driver code x = 3 fun(x) # this code is contributed by shivanisinghss2110
C#
// Java program showing Head Recursion
using System;
class GFG{
// Recursive function
static void fun(int n)
{
if (n > 0) {
// First statement in the function
fun(n - 1);
Console.Write(" "+ n);
}
}
// Driver code
public static void Main(String[] args)
{
int x = 3;
fun(x);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program showing Head Recursion
// Recursive function
function fun(n)
{
if (n > 0) {
// First statement in the function
fun(n - 1);
document.write(" "+ n);
}
}
// Driver code
var x = 3;
fun(x);
// This code is contributed by shivanisinghss2110
</script>
1 2 3
Entendamos el ejemplo rastreando el árbol de la función recursiva. Así es como se hacen las llamadas y así se producen las salidas.
Complejidad de tiempo para la recurrencia principal: O(n)
Complejidad espacial para la recurrencia principal: O(n)
Nota: Complejidad de tiempo y espacio se proporciona para este ejemplo específico. Puede variar para otro ejemplo.
Nota: La recursividad principal no se puede convertir fácilmente en un bucle como recursividad de cola, pero puede hacerlo. Convirtamos el código anterior en el bucle.
C++
// Converting Head Recursion into Loop
#include <iostream>
using namespace std;
// Recursive function
void fun(int n)
{
int i = 1;
while (i <= n) {
cout <<" "<< i;
i++;
}
}
// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// Converting Head Recursion into Loop
#include <stdio.h>
// Recursive function
void fun(int n)
{
int i = 1;
while (i <= n) {
printf("%d ", i);
i++;
}
}
// Driver code
int main()
{
int x = 3;
fun(x);
return 0;
}
Java
// Converting Head Recursion into Loop
import java.util.*;
class GFG
{
// Recursive function
static void fun(int n)
{
int i = 1;
while (i <= n) {
System.out.print(" "+ i);
i++;
}
}
// Driver code
public static void main(String[] args)
{
int x = 3;
fun(x);
}
}
// this code is contributed by shivanisinghss2110
Python3
# Converting Head Recursion into Loop # Recursive function def fun(n): i = 1 while (i <= n): print(i,end=" ") i+=1 # Driver code x = 3 fun(x) # This code is contributed by shivanisinghss2110
C#
// Converting Head Recursion into Loop
using System;
class GFG
{
// Recursive function
static void fun(int n)
{
int i = 1;
while (i <= n) {
Console.Write(" "+ i);
i++;
}
}
// Driver code
public static void Main(String[] args)
{
int x = 3;
fun(x);
}
}
// this code is contributed by shivanisinghss2110
Javascript
<script>
// Converting Head Recursion into Loop
// Recursive function
function fun(n)
{
var i = 1;
while (i <= n) {
document.write(" "+ i);
i++;
}
}
// Driver code
var x = 3;
fun(x);
// this code is contributed by shivanisinghss2110
</script>
1 2 3
- Tree Recursion : Para entender Tree Recursion , primero entendamos Linear Recursion . Si una función recursiva se llama a sí misma por una vez, se conoce como recursividad lineal . De lo contrario, si una función recursiva se llama a sí misma más de una vez, se conoce como Tree Recursion .
Ejemplo:
Pseudo Código para recursividad lineal
fun(n)
{
// some code
if(n>0)
{
fun(n-1); // Calling itself only once
}
// some code
}
Programa para la recursividad del árbol
C++
// C++ program to show Tree Recursion
#include <iostream>
using namespace std;
// Recursive function
void fun(int n)
{
if (n > 0)
{
cout << " " << n;
// Calling once
fun(n - 1);
// Calling twice
fun(n - 1);
}
}
// Driver code
int main()
{
fun(3);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C program to show Tree Recursion
#include <stdio.h>
// Recursive function
void fun(int n)
{
if (n > 0) {
printf("%d ", n);
// Calling once
fun(n - 1);
// Calling twice
fun(n - 1);
}
}
// Driver code
int main()
{
fun(3);
return 0;
}
Java
// Java program to show Tree Recursion
class GFG
{
// Recursive function
static void fun(int n)
{
if (n > 0) {
System.out.print(" "+ n);
// Calling once
fun(n - 1);
// Calling twice
fun(n - 1);
}
}
// Driver code
public static void main(String[] args)
{
fun(3);
}
}
// This code is contributed by shivanisinghss2110
Python3
# C++ program to show Tree Recursion # Recursive function def fun(n): if (n > 0): print(n, end=" ") # Calling once fun(n - 1) # Calling twice fun(n - 1) # Driver code fun(3) # This code is contributed by shivanisinghss2110
C#
// C# program to show Tree Recursion
using System;
class GFG
{
// Recursive function
static void fun(int n)
{
if (n > 0) {
Console.Write(" "+ n);
// Calling once
fun(n - 1);
// Calling twice
fun(n - 1);
}
}
// Driver code
public static void Main(String[] args)
{
fun(3);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to show Tree Recursion
// Recursive function
function fun(n)
{
if (n > 0) {
document.write(" "+ n);
// Calling once
fun(n - 1);
// Calling twice
fun(n - 1);
}
}
// Driver code
fun(3);
// This code is contributed by shivanisinghss2110
</script>
3 2 1 1 2 1 1
Entendamos el ejemplo rastreando el árbol de la función recursiva. Así es como se hacen las llamadas y así se producen las salidas.
Complejidad de tiempo para recursión de árbol: O(2^n)
Complejidad de espacio para recursión de árbol: O(n)
Nota: Complejidad de tiempo y espacio se proporciona para este ejemplo específico. Puede variar para otro ejemplo.
- Recursión anidada : en esta recursión, una función recursiva pasará el parámetro como una llamada recursiva. Eso significa «recursión dentro de la recursión». Veamos el ejemplo para entender esta recursividad.
Ejemplo:
C++
// C++ program to show Nested Recursion
#include <iostream>
using namespace std;
int fun(int n)
{
if (n > 100)
return n - 10;
// A recursive function passing parameter
// as a recursive call or recursion inside
// the recursion
return fun(fun(n + 11));
}
// Driver code
int main()
{
int r;
r = fun(95);
cout << " " << r;
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C program to show Nested Recursion
#include <stdio.h>
int fun(int n)
{
if (n > 100)
return n - 10;
// A recursive function passing parameter
// as a recursive call or recursion
// inside the recursion
return fun(fun(n + 11));
}
// Driver code
int main()
{
int r;
r = fun(95);
printf("%d\n", r);
return 0;
}
Java
// Java program to show Nested Recursion
import java.util.*;
class GFG {
static int fun(int n)
{
if (n > 100)
return n - 10;
// A recursive function passing parameter
// as a recursive call or recursion
// inside the recursion
return fun(fun(n + 11));
}
// Driver code
public static void main(String args[])
{
int r;
r = fun(95);
System.out.print(" "+ r);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python program to show Nested Recursion
def fun(n):
if (n > 100):
return n - 10
# A recursive function passing parameter
# as a recursive call or recursion inside
# the recursion
return fun(fun(n + 11))
# Driver code
r = fun(95)
print("", r)
# This code is contributed by shivanisinghss2110
C#
// C# program to show Nested Recursion
using System;
class GFG {
static int fun(int n)
{
if (n > 100)
return n - 10;
// A recursive function passing parameter
// as a recursive call or recursion
// inside the recursion
return fun(fun(n + 11));
}
// Driver code
public static void Main(String []args)
{
int r;
r = fun(95);
Console.Write(" "+ r);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to show Nested Recursion
function fun( n)
{
if (n > 100)
return n - 10;
// A recursive function passing parameter
// as a recursive call or recursion
// inside the recursion
return fun(fun(n + 11));
}
// Driver code
var r;
r = fun(95);
document.write(" "+ r);
// This code is contributed by shivanisinghss2110
</script>
91
Entendamos el ejemplo rastreando el árbol de la función recursiva. Así es como se hacen las llamadas y así se producen las salidas.
2. Recursión indirecta : en esta recursión, puede haber más de una función y se llaman entre sí de manera circular.
Del diagrama anterior, diversión (A) está llamando a la diversión (B), diversión (B) está llamando a la diversión (C) y diversión (C) está llamando a la diversión (A) y, por lo tanto, hace un ciclo.
Ejemplo:
C++
// C++ program to show Indirect Recursion
#include <iostream>
using namespace std;
void funB(int n);
void funA(int n)
{
if (n > 0) {
cout <<" "<< n;
// fun(A) is calling fun(B)
funB(n - 1);
}
}
void funB(int n)
{
if (n > 1) {
cout <<" "<< n;
// fun(B) is calling fun(A)
funA(n / 2);
}
}
// Driver code
int main()
{
funA(20);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// C program to show Indirect Recursion
#include <stdio.h>
void funB(int n);
void funA(int n)
{
if (n > 0) {
printf("%d ", n);
// Fun(A) is calling fun(B)
funB(n - 1);
}
}
void funB(int n)
{
if (n > 1) {
printf("%d ", n);
// Fun(B) is calling fun(A)
funA(n / 2);
}
}
// Driver code
int main()
{
funA(20);
return 0;
}
Java
// Java program to show Indirect Recursion
import java.io.*;
class GFG{
static void funA(int n)
{
if (n > 0) {
System.out.print(" " +n);
// Fun(A) is calling fun(B)
funB(n - 1);
}
}
static void funB(int n)
{
if (n > 1) {
System.out.print(" " +n);
// Fun(B) is calling fun(A)
funA(n / 2);
}
}
// Driver code
public static void main (String[] args)
{
funA(20);
}
}
// This code is contributed by shivanisinghss2110
C#
// C# program to show Indirect Recursion
using System;
class GFG{
static void funA(int n)
{
if (n > 0) {
Console.Write(" " +n);
// Fun(A) is calling fun(B)
funB(n - 1);
}
}
static void funB(int n)
{
if (n > 1) {
Console.Write(" " +n);
// Fun(B) is calling fun(A)
funA(n / 2);
}
}
// Driver code
public static void Main (String[] args)
{
funA(20);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python program to show Indirect Recursion
def funA(n):
if (n > 0):
print("", n, end='')
# Fun(A) is calling fun(B)
funB(n - 1)
def funB( n):
if (n > 1):
print("", n, end='')
# Fun(B) is calling fun(A)
funA(n // 2)
# Driver code
funA(20)
# This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to show Indirect Recursion
function funA(n)
{
if (n > 0) {
document.write(n.toFixed(0) + "</br>");
// Fun(A) is calling fun(B)
funB(n - 1);
}
}
function funB(n)
{
if (n > 1) {
document.write(n.toFixed(0) + "</br>");
// Fun(B) is calling fun(A)
funA(n / 2);
}
}
// Driver code
funA(20);
// this code is contributed by shivanisinghss2110
</script>
20 19 9 8 4 3 1
Entendamos el ejemplo rastreando el árbol de la función recursiva. Así es como se hacen las llamadas y así se producen las salidas.
Este artículo es una contribución de AmiyaRanjanRout . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por AmiyaRanjanRout y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA