La récursivité de la fonction pour trouver la puissance d'un nombre

Je suis en train d'écrire une récursivité de la fonction pour trouver la puissance d'un nombre et il semble être de la compilation, mais ne pas afficher quoi que ce soit.

#include <iostream>

using namespace std;

int stepem(int n, int k);

int main()
{
    int x, y;

    cin >> x >> y;

    cout << stepem(x, y) << endl;

    return 0;
}

int stepem(int n, int k)
{
    if (n == 0)
        return 1;
    else if (n == 1)
        return 1;
    else
        return n * stepem(n, k-1);
}

J'ai essayé de débogage, et il dit que le problème est sur cette ligne :
return n * stepem(n, k-1);

k semble un peu bizarre, mais je ne peux pas comprendre pourquoi?

Eh bien la vérité est que votre n n'est jamais en train de changer. C'est probablement le fait d'une récursion infinie jusqu'à ce que vos piles se remplir.
N'est-ce pas une boucle infinie?
Eh bien, il ne faut pas changer, pourquoi devrait-il? Je veux multiplier le nombre n pour k fois.
Je pense que vous voulez vérifier k et pas n, je me trompe?
non, parce que la récursivité n'est pas la queue récursive

InformationsquelleAutor user3002211 | 2013-11-17

c++function recursion

4

Vous devriez vérifier l'exposant k, pas le nombre lui-même qui ne change jamais.
```
int rPow(int n, int k) {
    if (k <= 0) return 1;
    return n * rPow(n, --k);
}
```
Votre k est d'obtenir des valeurs étranges parce que vous allez garder le calcul jusqu'à ce que vous manquez de mémoire, fondamentalement, vous permettra de créer de nombreux pile d'images avec k allant à "l'infini" (hypothétiquement).

Cela dit, il est théoriquement possible que le compilateur de vous donner un avertissement qu'il n'aura jamais de fin - dans ce scénario particulier. Toutefois, il est naturellement impossible de résoudre cette question de manière générale (rechercher le problème de l'Arrêt).
- Si la fonction est queue récursive, il pourrait être en mesure de répéter idefinitely sans utiliser plus de mémoire que la fonction vraiment besoin.
- Correct, vous pourriez éliminer l'appel et la réutilisation du cadre de pile, je voulais juste lui donner une idée de ce qui se passe si il n'y a pas de cas de base.
- Ouais, j'ai ajouté ma queue appel optimisable version. Tout en ayant k plus grand que MAX_INT pourrait pas créer un stackoverflow avec ma version, il devrait donner des résultats inattendus à certains points, si les chiffres sont trop élevés pour les services de renseignements.
- Je ne suis pas sûr de cela, et la flemme de me lever, mais je pense que le C++ n'est pas l'application effective de cette "optimisation" (à la différence de Haskell et probablement d'autres langages fonctionnels) - Afin de meh :). (Oui, il en est de même de la différence sémantique conséquences si une telle optimisation être prédéfinie, mais oui, meh.)
- Autant que je sache, la langue n'a pas l'appliquer, mais la plupart compilateur peut-être déjà fait ce genre d'optimisation pour un long moment. Je suis sûr que GCC ne sont, par défaut.
InformationsquelleAutor ScarletAmaranth
3

Votre algorithme est faux:
```
int stepem(int n, int k)
{
    if (k == 0) //should be k, not n!
        return 1;
    else if (k == 1) //this condition is wrong
        return 1;
    else
        return n * stepem(n, k-1);
}
```
Si vous l'appelez, avec stepem(2, 3) (par exemple), vous aurez 2 * 2 * 1 au lieu de 2 * 2 * 2 * 1. Vous n'avez pas besoin de else-if condition:
```
int stepem(int n, unsigned int k) //unless you want to deal with floating point numbers, make your power unsigned
{
    if (k == 0)
        return 1;
    return n * stepem(n, k-1);
}
```
- N'avez-vous pas besoin return n; quand k == 1 dans votre révision du code d'origine?
- Non, parce que l'instruction de retour il va la traiter: n * stepem(n, 0) équivaut à n * 1. La seule porte de sortie de la condition que vous avez besoin est de k == 0.
- Oh, si vous voulez dire que le premier bloc de code, j'ai juste corrigé le conditionnel contrôles de montrer comment l'algorithme est faux. Le code corrigé est dans le deuxième bloc (qui n'ont pas la k == 1 vérifier).
- Le premier bloc était ce que je faisais référence. Il est légitime de l'algorithme et fonctionne correctement si la deuxième return est changé à return n; — même si il serait également fonctionner correctement (mais un peu plus cher) si le else if (k == 1) return n; condition ont été supprimés, de même que dans la deuxième version du code. La différence est moins un appel de fonction vs un plus test — pas énorme.
- Je n'ai pas corrigé la partie dans le premier bloc de code parce que je voulais montrer que le retour 1 de ce bloc a été mathématiquement faux.
InformationsquelleAutor Zac Howland
1

N'ai pas tester, mais je suppose que cela devrait vous donner ce que vous voulez et c'est la queue récursive.
```
int stepemi(int result, int i int k) {
    if (k == 0 && result == i)
        return 1;
    else if (k == 0)
        return result;
    else
        return stepem(result * i, i, k-1);
}

int stepem(int n, int k) {
   return stepemi(n, n, k);
}
```
La grande différence entre ce morceau de code et l'autre exemple est que ma version pourrait obtenir optimisé pour queue d'appels récursifs. Cela signifie que lorsque vous appelez stepemi de manière récursive, il n'a pas à garder quelque chose en mémoire. Comme vous pouvez le voir, il pourrait remplacer la variable dans l'actuel cadre de la pile sans avoir à en créer un nouveau. Aucune variable à rester dans la mémoire pour calculer la suivante récursivité.

Si vous pouvez avoir optimisé la queue d'appels récursifs, cela signifie également que la fonction sera utilisée d'un montant fixe de la mémoire. Il n'aura jamais besoin de plus de 3 ints.

D'autre part, le code que vous avez écrit à la première crée un arbre de la structure de pile en attente de retour. Chaque récursion s'ajoutera jusqu'à la prochaine.
- pouvez-vous dire 3 int au lieu de 3 byte?
- À l'aide de deux fonctions semble un peu inutilement complexe.
- oui nous ne sommes pas à l'aide de 8bit jetons plus... 🙁
- ensuite, utilisez uniquement le premier avec 3 paramètres. La deuxième fonction est juste une abréviation, et n'est pas nécessaire. C'est le prix que vous aurez à payer pour avoir de la queue des fonctions récursives.
- Je vous donne un vote parce que nous avons proposé la solution dans les commentaires avant il était disponible comme une réelle réponse 🙁
InformationsquelleAutor Loïc Faure-Lacroix
1

Bien, juste pour poster une réponse en fonction de mon commentaire (il semble que j'ai manqué d'ajouter un commentaire et non une réponse :-D). Je pense que, surtout, vous avez deux erreurs: vous êtes à la vérification de n au lieu de k et vous êtes de retour 1 quand la puissance est de 1, au lieu de retourner n. Je pense que stepem fonction devrait ressembler à:

Edit: mis à Jour pour supporter les exposants négatifs par @ZacHowland suggestion
```
float stepem(int n, int k)
{
    if (k == 0)
        return 1;
    else
        return (k<0) ?((float) 1/n) * stepem(n, k+1)  :n * stepem(n, k-1);
}
```
- @LoïcFaure-Lacroix 😉
- Le seul problème que j'ai avec c'est le <=0 vérifier. Si k est négatif, la valeur de retour (mathématiquement) serait une fraction, pas 1. La plus sûre solution est de prévenir les nombres négatifs pour l'exposant, tout à fait (à moins que le désir est de manipuler des nombres à virgule flottante).
- Je suis d'accord que, être strict, l'utilisation exponentielle négative, serait de retour d'une fraction, mais, en tenant compte de la fonction proposée signature, je suppose que seules les valeurs positives sont attendues. Je voudrais le mettre à jour pour soutenir les exposants négatifs 😉
InformationsquelleAutor jcm

//Power.cpp : Defines the entry point for the console application.
//


#include <stream>

using namespace std;

int power(int n, int k);

void main()
{
    int x,y;

    cin >>x>>y;

    cout<<power(x,y)<<endl;


}

int power(int n, int k)
{
    if (k==0)
        return 1;
    else if(k==1) //This condition is working :) //
        return n;
    else
        return n*power(n,k-1);
}

InformationsquelleAutor

0

votre Programme est mauvais et qu'il Ne prend pas en charge négative de la valeur donnée par l'utilisateur,
vérifier celui-ci
```
int power(int n, int k){
'if(k==0)
 return 1;
 else if(k<0)
 return ((x*power(x,y+1))*(-1));
 else
 return n*power(n,k-1);
 }
```
InformationsquelleAutor Jamshaid Kamran

désolé, j'ai changé les noms de variables
mais j'espère que vous comprendrez;

#include <iostream>
using namespace std;

double  power(double , int);//it should be double because you also need to handle negative powers which may cause fractions

int main()
{
 cout<<"please enter the number to be powered up\n";
 double number;
 cin>>number;
 cout<<"please enter the number to be powered up\n";
 int pow;
 cin>>pow;
 double result = power(number, pow);
 cout<<"answer is "<<result <<endl;
}

 double power( double x, int n)
{

if (n==0)
    return 1;
if (n>=1)
    /*this will work OK even when n==1 no need to put additional condition as n==1
    according to calculation it will show x as previous condition will force it to be x;
    try to make pseudo code on your note book you will understand what i really mean*/
    if (n<0)
    return x*power(x, n-1);
   return 1/x*power(x, n+1);//this will handle negative power as you should know how negative powers are handled in maths
}

InformationsquelleAutor Muhammad Zubair

-1

int stepem(int n, int k)

{
    if (k == 0)   //not n cause you have to vary y i.e k if you want to find x^y
        return 1; 
    else if (k == 1)
        return n;  //x^1=x,so when k=1 it should be x i.e n
    else
        return n * stepem(n, k-1);
}

InformationsquelleAutor Roy

Vous devez vous connecter pour publier un commentaire.