recursion problem

i am trying to figure our how a side would look if to find the the amount a number can by raised to without exceeding y. this is part of a big program and this is the only part i am having a lot of problem with. thank!!
double maxRaiseAmount = y - aNumber;
this is what i have so far. it is only printing 62 for the result

int maxpower(int x , int y){
int temp =1;
double maxRaiseAmount = y - temp;
//geting the power or x raised to a number
temp *= x ;
//if the temp is greater than y returns 0 because it exceeds the y amount entered
if (temp > y){
return 0;
}
//retruns the max power a number can be raised to without exceeding y
else if (temp < y){
return maxRaiseAmount;
}
else{
return maxpower(x,y-1);//recursive statement
}
}
Remember your basic algebra!
To find p such that x^p = y, take the natural logarithm:
x^p = y ⇒ log(x^p) = log(y) ⇒ log(x)p = log(y) ⇒ p = log(y) / log(x)

The natural logarithm yields a real result in this case, so take the least-trailing-integer of the result.
In C++:
1
2
3
# include <cmath>
...
std::floor(std::log(y) / std::log(x))


To follow through on your algorithm:
I don't think this problem is a good fit for a recursive solution, but we'll do it anyways for the sake of demonstration.

Given that the goal of recursion is to to break the problem down into something smaller, you're going to need some extra state besides the base, x and the maximum, y. You can avoid adding an extra parameter by manipulating the result and exponent, but that requires manipulating logarithms which defeats the point. (Edit: actually, you can divide.)

It looks like you're getting confused about what y is in your attempt. It is the result of the exponentation x^p; you're looking for the greatest exponent p which doesn't exceed y. Here is one way to do this in an accumulative-recursive style:
1
2
3
4
5
6
7
8
9
10
11
12
int ilogx_impl(int const x, int const y, int const acc) { 
  if ((acc * x) > y) return 0;
  else return ilogx_impl(x, y, acc * x) + 1;
}
int ilogx(int const x, int const y) { 
  return ilogx_impl(x, y, 1);
}
# include <iostream>
int main() { 
  std::cout << "as integers, the greatest power that 2 can be raised to "
             << "without exceeding 1023 is " << ilogx(2, 1023) << ".\n";
}
Last edited on
If you use floating-point numbers then you will require logs.

Otherwise ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

int maxpower(int x , int y)
{
   int power = 0, temp = 1;
   while( true )
   {
      temp *= x;
      if ( temp > y ) break;
      power++;  
   }
   return power;
}


// To test
int main() {int x, y;   cout << "Input integers x, y (with 1 < x < y ) : ";   cin >> x >> y;  cout << "Power is " << maxpower( x, y );}
1
2
3
4
5
6
// invariant: n, max_value are non-zero
unsigned int max_pow_not_above( unsigned int n, unsigned long long max_value )
{
    if( n > max_value ) return 0 ;
    else return 1 + max_pow_not_above( n, max_value/n ) ;
}
Topic archived. No new replies allowed.