Calcul d'une racine imbriquée en C

On m'a demandé de calculer l'expression racine imbriquée suivante en utilisant la récursivité uniquement.

J'ai écrit le code ci-dessous qui fonctionne, mais ils nous ont permis d' utiliser une seule fonction et 1 entrée nà cet effet et non 2 comme je l'ai utilisé. Quelqu'un peut-il m'aider à transformer ce code en une fonction qui calculera l'expression? ne peut pas utiliser n'importe quelle bibliothèque, sauf les fonctions de <math.h>.

sortie pour 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);
}

Utilisez les bits supérieurs de ncomme compteur:

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

Naturellement, cela fonctionne mal lorsque l'initiale nest Rou plus. Voici une version plus compliquée qui fonctionne pour toute valeur positive de n. Ça marche:

• Quand nest négatif, cela fonctionne comme la version ci-dessus, en utilisant les bits supérieurs pour compter.
• Quand nest positif, s'il est inférieur à R, il s'appelle avec -npour évaluer la fonction comme ci-dessus. Sinon, il s'appelle avec R-1nié. Cela évalue la fonction comme si elle était appelée avec R-1. Cela produit le résultat correct car la série cesse de changer au format à virgule flottante après seulement quelques dizaines d'itérations - les racines carrées des nombres plus profonds sont tellement diluées qu'elles n'ont aucun effet. Ainsi, la fonction a la même valeur pour tous nsur un petit seuil.

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

Sans transformer mathématiquement la formule (je ne sais pas si c'est possible), vous ne pouvez pas vraiment utiliser un seul paramètre, car pour chaque élément, vous avez besoin de deux informations: l'étape en cours et l'original n. Cependant, vous pouvez tricher . Une façon consiste à coder les deux nombres dans le intparamètre (comme indiqué par Eric ).

Une autre façon consiste à stocker l'original ndans une variable locale statique. Au premier appel, nous enregistrons ndans cette variable statique, nous démarrons la récursivité et à la dernière étape, nous la réinitialisons à la valeur sentinelle:

// 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));
}

Apparemment, ce static int n = sentineln'est pas du C standard car ce sentineln'est pas une constante de temps de compilation en C (c'est bizarre parce que gcc et clang ne se plaignent pas, même avec -pedantic)

Vous pouvez le faire à la place:

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

Ce problème demande des solutions déformées.

En voici une qui utilise une seule fonction prenant un ou deux intarguments:

• si le premier argument est positif, il calcule l'expression de cette valeur
• si le premier argument est négatif, il doit être suivi d'un deuxième argument et effectue une seule étape du calcul, récursif pour l'étape précédente.
• il utilise <stdarg.h>ce qui pourrait ou non être autorisé.

Voici le code:

#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);
    }
}

Voici une autre solution avec une seule fonction, utilisant uniquement <math.h>, mais abusant des règles d'une manière différente: en utilisant une 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));
    }
}

Encore un autre, à proprement parler récursif , mais avec un seul niveau de récursivité et sans autres astuces. Comme Eric l'a commenté, il utilise une forboucle qui pourrait être invalide sous les contraintes de l'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;
    }
}

Voici une autre approche.

Il repose sur int32 bits. L'idée est d'utiliser les 32 bits supérieurs d'un 64 bits intpour

1) Voir si l'appel était un appel récursif (ou un appel de "l'extérieur")

2) Enregistrez la valeur cible dans les 32 bits supérieurs pendant la récursivité

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