Функция рекурсии, чтобы найти силу числа

Question

Я пишу функцию рекурсии, чтобы найти мощность числа и, кажется, компилируется, но ничего не выводит.

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

Я попытался ее отладки, и он говорит, что проблема находится на этой линии: return n * stepem(n, k-1);

к, кажется, получаю некоторые странные значения, но я не могу понять, почему?

Answer 1

Вы должны проверить показатель k, а не номер, который никогда не изменяется.

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

Ваш к получает странные значения, потому что вы будете держать вычисление, пока вы бежите из памяти в основном, вы будете создавать много фреймов стеки с к собирается «-Infinity» (гипотетический).

При этом теоретически возможно, чтобы компилятор дал вам предупреждение о том, что он никогда не завершится - в этом конкретном сценарии. Однако, естественно, этого вообще не решить (посмотрите проблему с остановкой).

Answer 2

Ваш алгоритм является неправильным:

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

Если вы вызываете его с stepem(2, 3) (к примеру), вы получите 2 * 2 * 1 вместо 2 * 2 * 2 * 1. Вы не необходимо условие else-if:

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

Answer 3

Не тестировал его, но я думаю, он должен дать вам то, что вы хотите, и это хвост рекурсивный.

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

Большая разница между этой частью кода, а другой, например, что моя версия может получить оптимизированный для хвостовых рекурсивных вызовов. Это означает, что когда вы вызываете stepemi рекурсивно, ему не нужно ничего хранить в памяти. Как вы можете видеть, он может заменить переменную в текущем стеке стека, не создавая новую. Нет переменной, чтобы оставаться в памяти, чтобы вычислить следующую рекурсию.

Если вы можете оптимизировать хвостовые рекурсивные вызовы, это также означает, что функция будет использовать фиксированный объем памяти. Ему никогда не понадобится больше 3 тс.

С другой стороны, код, который вы написали, сначала создает дерево стоп-кадра, ожидающее возврата. Каждая рекурсия будет складываться до следующей.

Answer 4

Ну, просто чтобы отправить ответ в соответствии с моим комментарием (кажется, я пропустил добавление комментария, а не ответ: -D). Я думаю, в основном, у вас есть две ошибки: вы проверяете n вместо k, и вы возвращаете 1, когда мощность 1, вместо того, чтобы возвращать n.Я думаю, что stepem функция должна выглядеть следующим образом:

Edit: Обновление для поддержки отрицательных показателей по @ZacHowland предложению

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

Answer 5

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

Answer 6

вашей программа не так, и он не поддерживает отрицательное значение, заданное пользователем, проверить это один

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

Answer 7

жаль, что я изменил свои имена переменных , но я надеюсь, что вы поймете;

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

Answer 8

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