recursivos - recursividad java

Algoritmo de ejecución buscando recursivamente un número menor, es muy lento

Question

Hola, tengo el siguiente código

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define min(x, y)(x < y)?(x):(y)
#define SIZE 1000

int valormenor(int a[], int n)
{
    if(n == 1)
        return a[0];
    else
        return min(a[0], valormenor(a + 1, n - 1));
}

int main(void)
{
    int arr[SIZE] = {0}, i;
    srand (time (NULL));
    for(i = 0; i < SIZE; i++)
        arr[i] = rand() % SIZE;
    arr[5] = -1;
    printf("%d/n", valormenor(arr, SIZE));

    return 0;
}

El punto es que no entiendo porque lleva demasiado tiempo encontrar el número más pequeño, mi teoría es que esta función recursiva está mal implementada, ¿quién reclama?

Answer 1

Ampliemos la macro min aquí:

return min(a[0], valormenor(a + 1, n - 1));

Eso se convierte

return (a[0] < valormenor(a + 1, n - 1))?(a[0]):(valormenor(a + 1, n - 1));

Como puede ver, valormenor se llama dos veces. Esas dos llamadas recursivas hacen cuatro llamadas recursivas, que hacen ocho llamadas recursivas, y así sucesivamente. Es un clásico error de evaluación doble.

No use macros como este. Simplemente no valen la pena los dolores de cabeza.