Transformer fonction itérative en récursive un - C

Question

EDIT: NON DEVOIRS, je suis en train de résoudre un test par rapport aux années passées, tout apprentissage.

J'ai cette fonction, et je voudrais savoir quelles mesures à prendre afin de le transformer en une récursive.

C'est ma fonction, il résume les N premiers nombres impairs:

4^2 = 1+3+5+7 = 16; 

int quadIT(int n){ 

    int x=0; 
    int z=1; 
    int y=n; 

    while(y>0){ 
     x+=z; 
     z+=2; 
     y--; 
    } 

    return x; 
} 

Probablement la fonction ci-dessus n'est pas la meilleure approche.

Je vous serais reconnaissant toute aide ici.

Answer 1

Je ne veux pas vous donner une réponse directe, mais plutôt de vous montrer à peu près comment le faire. Ces deux sont équivalentes:

int foo(int n){ 
    if (n == 0){ 
     return something 
    } else { 
     do something 
     return foo(n-1); 
    } 
} 

while(n > 0){ 
    do something 
    n--; 
} 

Answer 2

Vous devez décomposer le problème en utilisant une version réduite d'elle-même, plus un peu peu plus. Dans ce cas, la somme des N premiers nombres impairs est la somme des N premiers nombres impairs plus une quantité que vous pouvez calculer.

Alors

int sum_odd(int n) 
{ 
    if (!n) return 0; 
    return sum_odd(n-1) + some_calculation_here; 
} 

Answer 3

int quadIT(int n) 
{ 
    if (n == 1) 
    { 
     return 1; 
    } 
    else 
    { 
     return ((2*n)-1 + quadIT(n-1)); 
    } 
} 

Answer 4

Lorsque vous convertissez une itération à récursivité, regardez la variable de la boucle. Dans ce cas, c'est votre variable y. Faites-en un paramètre de votre fonction récursive. Ensuite, regardez les autres variables qui changent pendant que vous itérez votre boucle, et faites-en les paramètres aussi. À ce stade, vous devriez avoir votre déclaration de fonction vers le bas:

int quatItRecursive(int y, int x, int z) { 
    ... 
} 

Maintenant vous êtes prêt à travailler sur le corps de votre fonction. Commencez avec le cas de base en considérant le résultat obtenu lorsque la boucle ne démarre pas (c'est-à-dire lorsque n est égal à zéro). Dans ce cas, votre fonction renvoie x. Alors maintenant, vous avez votre cas de base:

int quatItRecursive(int y, int x, int z) { 
    if (y == 0) { 
     return x; 
    } 
    ... 
} 

Pour terminer le corps, ajoutez l'étape récursive, à savoir un appel qui effectue l'étape de la boucle. Il est un appel récursif maintenant, avec des paramètres qui égalent ce que les variables seraient dans la prochaine itération de la boucle:

int quatItRecursive(int y, int x, int z) { 
    if (y == 0) { 
     return x; 
    } 
    return quatItRecursive(y-1, x + z, z + 2); 
} 

Enfin, ajoutez une enveloppe qui prend un seul paramètre, la façon dont votre fonction d'origine a fait:

int quantIT(int n) { 
    return quatItRecursive(n, 0, 1); 
} 

Answer 5

la fonction récursive peut être définie de la manière suivante

#include <iostream> 

unsigned long long quadIT(unsigned long long n) 
{ 
    return n == 0 ? 0 : 2 * n - 1 + quadIT(n - 1); 
} 

int main() 
{ 
    for (unsigned long long i = 0; i < 10; i++) 
    { 
     std::cout << quadIT(i) << std::endl; 
    } 
} 

la sortie est

0 
1 
4 
9 
16 
25 
36 
49 
64 
81 

prendre en compte que le paramètre de fonction doit être définie comme un certain type d'entiers non signés. Sinon, la fonction sera plus composée.