recursividad - Un buen banco de soluciones de recursión en C/C++/Java/C#

recursividad programacion ats

Question

Vi esta pregunta , pero las respuestas allí no son muy relevantes. Un amigo necesita un banco de problemas de recursión para ayudarlo a estudiar para una prueba mañana .

Aprendió el problema teóricamente, pero tiene problemas para comprender cómo resolver realmente los problemas de recursión. ¿Conoces una buena fuente de problemas de recursión resueltos (preferiblemente en C, pero también en un lenguaje de estilo C) disponibles en la red?

Nota: los ejemplos en lenguajes funcionales no ayudarán mucho aquí. Mi amigo está en una carrera de estudio para pasar su examen mañana, y estoy seguro de que cambiar de idioma lo confundirá en este punto (podría ser educativo en otros momentos menos estresados).

Answer 1

Creo que la sintaxis de Haskell es genial para pensar recursivamente, porque la construcción de coincidencia de patrones hace que el caso base y el caso recursivo sean tan obvios. Traducir esto a otro idioma es bastante sencillo.

sumAll [] = 0
sumAll (x:xs) = x + sumAll xs

Para entender esto, solo necesitas saber que

• [] representa una lista vacía,
• (x: xs) divide una lista en una cabeza (x) y una cola (xs)

No es necesario que aprenda todo Haskell (es decir, seamos sinceros, difícil), pero hacer algunos de los conceptos básicos sin duda le ayuda a pensar en la recursión.

Answer 2

Esto va a sonar como una respuesta muy poco convincente, pero la recursividad es un paradigma que a menudo es muy difícil de entender al principio para los principiantes. Tomará más de un día de meditación sobre el tema para que su amigo capte firmemente el concepto.

Es posible que desee que examine el Proyecto Euler para obtener una posible orientación para estudiar.

Answer 3

Leer SICP (Estructura e Interpretación de Programas de Computación)

Answer 4

Una de las mejores formas de aprender recursividad es obtener experiencia en un lenguaje de programación funcional como Haskell o Lisp o Scheme.

Entonces, encontrar problemas recursivos puede reducirse a encontrar algunos problemas y respuestas relacionados con los lenguajes de programación funcionales. Aquí hay un ejemplo de 99 problemas de ceceo .

En realidad, solo lleva 5 minutos aprender Scheme o Lisp para que pueda comenzar con ejemplos de inmediato para la prueba que mencionó mañana.

Otra excelente forma de aprender recursividad es practicando pruebas matemáticas que involucren la inducción.

Conceptos clave relacionados con la recursión:

Con recursión no necesita saber cómo resolver el problema. Solo necesitas saber 2 cosas. 1) cómo resolver la instancia más pequeña del problema, y ​​2) cómo dividirla en partes más pequeñas.

De manera equivalente, solo debe tener en cuenta que necesita: 1) un caso base y 2) un caso recursivo.

El caso base maneja 1 instancia única de lo que quiere hacer con la entrada más pequeña.

El caso recursivo divide el problema en un subproblema. Eventualmente, este subproblema se reducirá al caso base.

Ejemplo:

//1+...+n = n*n(+1)/2 = sumAll(n):

int sumAll(int x)
{
  if(x == 0) //base case
    return 0; 
  else
    return sumAll(x-1) + x; //recursive case
}

Es importante entender que el caso base no es difícil de entender. Simplemente tiene que existir. Aquí hay una solución equivalente para x> 0:

//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
  if(x == 1) //base case
    return 1; 
  else
    return sumAll(x-1) + x; //recursive case
}

Answer 5

Este artículo explica la recursión y tiene algunos ejemplos simples de C para atravesar la lista vinculada y el árbol binario

Answer 6

#include<iostream>
using namesspace std;
int E(int x);
int main()
{
    int x;
    cout << E(x) << endl;
    return 0;
}

int E(int x)
{
    return x ? (x % 10 + E(x/10)) : 0;
}

Answer 7

En lenguaje c / c ++, una función puede llamarse a sí misma y este caso se llama Recursion. Principalmente la recursividad tiene dos casos:

1. Caso base.
2. caso recursivo.

y tenemos algunas categorías recursivas como ...

1. Recursividad del trazador de líneas
2. Recursión binaria
3. Recursión anidada
4. Recursión mutua
5. Recursividad de la cola

Aquí toma un ejemplo para discutir la recursión ...

// a recursive program to calculate NcR  //
#include <stdio.h> 
int ncr(int x,int y)
{
    if(y>x)
    {
        printf("!sorry,the operation can''t processed.");
        getch();
        exit(1);
    }
    else if(y==0 ||y==x)   //base case
    {
        return(1);
    }
    else
    {
        return(ncr(x-1,y-1)+ncr(x-1,y));  //recursive case
    }
}