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

Question

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

Aprendió el problema teóricamente, pero tiene problemas para comprender cómo resolver 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

This article explica la recursividad y tiene algunos ejemplos sencillos C para atravesar lista enlazada y árbol binario

Answer 2

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

Por lo tanto, la búsqueda de problemas recursivos se puede reducir a la búsqueda de algunos problemas y respuestas relacionadas con los lenguajes de programación funcionales. Aquí hay un ejemplo 99 lisp problems.

Realmente solo toma 5 minutos aprender Scheme o Lisp para que pueda comenzar con ejemplos de inmediato para la prueba que mencionó mañana.

Otra gran manera de aprender la recursión es practicando pruebas matemáticas con inducción.

---

conceptos clave relacionados con la recursividad:

Con la recursividad no es necesario 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.

Equivalentemente, solo tiene que tener en cuenta que necesita: 1) una funda y 2) una funda recursiva.

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 averiguar. Simplemente tiene que existir. Aquí es 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 3

Esto va a sonar como una respuesta muy escaso, pero la repetición es un paradigma que es a menudo muy difícil de captar en la primera 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 lea Project Euler para una posible dirección de estudio.

Answer 4

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, que realmente sólo necesita 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 (que es, seamos sinceros, difícil) - pero hacer algunos de los conceptos básicos ciertamente le ayuda a pensar en la recursión.

Answer 5

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

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 C/C++ lenguaje de una función puede llamar en sí mismo y este caso se llama Recursion. Principalmente recursion tiene dos casos:

1. Funda de base.
2. caso recursivo.

y tenemos algunas categorías como recursivos como ...

1. Liner recursividad
2. recursividad binario
3. recursividad anidada
4. recursión mutua
5. cola recursividad

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 
    } 
}