banner


Recursividad?
 

Joel Spolsky en uno de sus últimos artículos dejó un simple test para saber si eres o no un buen programador, según él hay dos clases de programadores: aquellos que entienden punteros y recursion y el resto. El problema original esta planteado en SCHEME, pero tiene una variante en Javascript que pongo a continuación:

 

Usando la función accumulate: 

			  
function accumulate (combiner, nullValue, list)
{
    if (list.length == 0)
        return nullValue;
    var first = list.shift ();
    return combiner (first, accumulate (combiner, nullValue, list));
}

Implementar la función sumOfSquares, la cual debe calcular la suma de cuadrados de una lista, por ejemplo:

			  
    sumOfSquares([1,2,3,4,5])

debe dar como resultado 55.

 

Me pareció un problema interesante y pensé ¿Porque no plantearla en C++? De esa forma mezclamos punteros y recursividad en un solo problema:

 

			 
#include <vector>
#include <iostream>

using namespace std;

typedef vector <int> VCT_INT;
typedef int (*PFUNC) (int, int);

int accumulate( PFUNC combiner, VCT_INT &input )
{
    if( input.size() <= 0 ) { return 0; }
    int first = input[0];
    input.erase( input.begin() );
    return combiner( first, accumulate( combiner, input ) );
}

int function( int x, int y )
{
    return( /** usar x e y aqui **/ ); 
}

int sumOfSquares( VCT_INT &input )
{
    accumulate( /** usar function e input aqui **/ );
}

int main()
{
    VCT_INT test;
    for( int k = 1; k <= 5; test.push_back( k++ ) );
    cout << sumOfSquares( test ) << endl;
    return 0;
}

La respuesta es bien sencilla (dos lineas) y la dejo como ejercicio. Si necesitas una ayuda te puede servir la respuesta en Javascript:

 

 

Tuve que activar el intérprete JScript de mi programa R_porter y añadirle las funciones que no están definidas: alert, prompt y confirm. Todo porque no quería incrustar el código dentro de una página HTML.

 

Nota: este es un problema de recursividad y no, no estoy olvidando que existen otros formas de resolver el problema en C++ como:

 

La común y silvestre:

		 
#include <iostream>

int main ()
{
    int lst[5] = { 1, 2, 3, 4, 5 };

    int sum = 0;
    for(int k = 0; k < 5; k++)
    {
        sum += lst[k] * lst[k];
    }

    std::cout << sum << std::endl;
    return 0;
}

La estándar:

		 
#include <iostream>
#include <numeric>

int function (int x, int y)
{
    return x + y * y;
}

int main ()
{
    int lst[5] = { 1, 2, 3, 4, 5 };
    std::cout << std::accumulate (lst, lst + 5, 0, function) << std::endl;
}

La esotérica:

		 
#include <iostream>
#include <boost/bind.hpp>
#include <numeric>

int main ()
{
    int lst[5] = { 1, 2, 3, 4, 5 };
    std::cout = std::accumulate (lst, lst + 5, 0,
                                 boost::bind (std::plus(), _1,
                                 boost::bind (std::multiplies(), _2, _2)));
}

O la super-cool:

		 
#include <iostream>
#include <boost/lambda/lambda.hpp>
#include <numeric>

int main ()
{
    using namespace boost::lambda;

    int lst[5] = { 1, 2, 3, 4, 5 };
    std::cout << std::accumulate (lst, lst + 5, 0, _1 + _2 * _2) << std::endl;
}

 

El problema original planteado en SCHEME:

		 
(define (accumulate combiner nullvalue lst) 
   (if (null? lst)
       nullvalue
       (combiner (car lst)
                 (accumulate combiner
                             nullvalue
                             (cdr lst)))))

(define (sumOfSquares lst)
   (accumulate (lambda (x y) (+ (* x x) y))
               0
               lst))

(sumOfSquares '(1 2 3 4 5))

 

Que traducido a LISP es:

		 
(defun accumulate (combiner nullvalue lst)
    (if (null  lst)
        nullvalue
        (funcall combiner (car lst)
            (accumulate combiner nullvalue (cdr lst)))))

(defun sumOfSquares (lst)
    (accumulate (lambda (x y) (+ (* x x) y))
                0
                lst))

(sumOfSquares '(1 2 3 4 5))

 
 

 

Diseño y coordinación : Esaú Rodriguez Oscanoa - Lima - Per�

Esta página se ve mejor en Mozilla Firefox a 1024x768
Hosted by www.Geocities.ws

1