Cálculo de una raíz anidada en C

Me pidieron que calcule la siguiente expresión de raíz anidada usando solo recursión .

Escribí el siguiente código que funciona, pero nos permitieron usar solo una función y 1 entrada npara el propósito y no 2 como usé. ¿Alguien puede ayudarme a transformar este código en una función que calcule la expresión? No puedo usar ninguna biblioteca excepto las funciones de <math.h>.

salida para n = 10: 1.757932

double rec_sqrt_series(int n, int m) {
    if (n <= 0)
        return 0;
    if (m > n)
        return 0;
    return sqrt(m + rec_sqrt_series(n, m + 1));
}

double helper(int n) {
    return rec_sqrt_series(n, 1);
}

Use los bits superiores de ncomo contador:

double rec_sqrt_series(int n)
{
    static const int R = 0x10000;
    return n/R < n%R ? sqrt(n/R+1 + rec_sqrt_series(n+R)) : 0;
}

Naturalmente, eso funciona mal cuando la inicial nes Ro mayor. Aquí hay una versión más complicada que funciona para cualquier valor positivo de n. Funciona:

• Cuando nes negativo, funciona como la versión anterior, utilizando los bits superiores para contar.
• Cuando nes positivo, si es menor que R, se llama a sí mismo -npara evaluar la función como se indicó anteriormente. De lo contrario, se llama a sí mismo con R-1negado. Esto evalúa la función como si se llamara con R-1. Esto produce el resultado correcto porque la serie deja de cambiar en el formato de punto flotante después de unas pocas docenas de iteraciones: las raíces cuadradas de los números más profundos se diluyen tanto que no tienen ningún efecto. Por lo tanto, la función tiene el mismo valor para todos nen un umbral pequeño.

double rec_sqrt_series(int n)
{
    static const int R = 0x100;
    return
        0 < n ? n < R ? rec_sqrt_series(-n) : rec_sqrt_series(1-R)
              : n/R > n%R ? sqrt(-n/R+1 + rec_sqrt_series(n-R)) : 0;
}

Sin transformar matemáticamente la fórmula (no sé si es posible), no puede usar realmente un solo parámetro, ya que para cada elemento necesita dos informaciones: el paso actual y el original n. Sin embargo, puedes hacer trampa . Una forma es codificar los dos números en el intparámetro (como lo muestra Eric ).

Otra forma es almacenar el original nen una variable local estática. En la primera llamada que guardamos nen esta variable estática, comenzamos la recursión y en el último paso la restablecemos al valor centinela:

// fn(i) = sqrt(n + 1 - i + fn(i - 1))
// fn(1) = sqrt(n)
//
// note: has global state
double f(int i)
{
    static const int sentinel = -1;
    static int n = sentinel;

    // outside call
    if (n == sentinel)
    {
        n = i;
        return f(n);
    }

    // last step
    if (i == 1)
    {
        double r = sqrt(n);
        n = sentinel;
        return r;
    }

    return sqrt(n + 1 - i + f(i - 1));
}

Aparentemente static int n = sentinelno es C estándar porque sentinelno es una constante de tiempo de compilación en C (es extraño porque tanto gcc como clang no se quejan, incluso con -pedantic)

Puedes hacer esto en su lugar:

enum Special { Sentinel = -1 };
static int n = Sentinel;

Este problema pide soluciones retorcidas.

Aquí hay uno que usa una sola función tomando uno o dos intargumentos:

• si el primer argumento es positivo, calcula la expresión para ese valor
• Si el primer argumento es negativo, debe ser seguido por un segundo argumento y realiza un solo paso en el cálculo, recurriendo al paso anterior.
• utiliza lo <stdarg.h>que podría o no estar permitido.

Aquí está el código:

#include <math.h>
#include <stdarg.h>

double rec_sqrt_series(int n, ...) {
    if (n < 0) {
        va_arg ap;
        va_start(ap, n);
        int m = va_arg(ap, int);
        va_end(ap);
        if (m > -n) {
            return 0.0;
        } else {
            return sqrt(m + rec_sqrt_series(n, m + 1));
        }
    } else {
        return rec_sqrt_series(-n, 1);
    }
}

Aquí hay otra solución con una sola función, usando solo <math.h>, pero abusando de las reglas de una manera diferente: usando una macro.

#include <math.h>

#define rec_sqrt_series(n)  (rec_sqrt_series)(n, 1)
double (rec_sqrt_series)(int n, int m) {
    if (m > n) {
        return 0.0;
    } else {
        return sqrt(m + (rec_sqrt_series)(n, m + 1));
    }
}

Otro más, estrictamente hablando recursivo , pero con un solo nivel de recursión y sin otros trucos. Como Eric comentó, usa un forbucle que podría ser inválido bajo las restricciones del OP:

double rec_sqrt_series(int n) {
    if (n > 0) {
        return rec_sqrt_series(-n);
    } else {
        double x = 0.0;
        for (int i = -n; i > 0; i--) {
            x = sqrt(i + x);
        }
        return x;
    }
}

Aquí hay otro enfoque.

Se basa en intser de 32 bits. La idea es utilizar los 32 bits superiores de 64 bits intpara

1) Vea si la llamada fue recursiva (o una llamada desde el "exterior")

2) Guarde el valor objetivo en los 32 bits superiores durante la recursividad

// Calling convention:
// when calling this function 'n' must be a positive 32 bit integer value
// If 'n' is zero or less than zero the function have undefined behavior
double rec_sqrt_series(uint64_t n)
{
  if ((n >> 32) == 0)
  {
    // Not called by a recursive call
    // so start the recursion
    return rec_sqrt_series((n << 32) + 1);
  }

  // Called by a recursive call

  uint64_t rn = n & 0xffffffffU;

  if (rn == (n >> 32)) return sqrt(rn);      // Done - target reached

  return sqrt (rn + rec_sqrt_series(n+1));   // Do the recursive call
}