Recursive method that calculates a^b

[slappy]

Hey everyone!
First time poster here.
I need some help with a exercise I found in a test.
The question might be very simple but its kinda hard for me, becouse we have never done exercises before.
"Write a class in C++ which implements a recursive method in which way , given 2 intigers a and b, the method calculates the function a^b.This is how far I got.I guess this does the job but its not recursive.I think I need something to loop.
Thank you.

Header class C1{
public:
C1(); //I guess this constructor does nothing but the teachers asks for it in every exercise.
int m(int a,int b);
}
Source 
#include C1.h
C1::C1()
int C1::m(int a, int b)
{
return a^b;
}

[Peter87]

Note that ^ in C++ is the bitwise XOR operator. Your teacher probably want you to compute a raised to the power of b.

[keskiverto]

The C++ operator^ for integers is not power, but a bitwise operation. You have to use multiplication (operator*).

How would you write the power as a loop?


PS. The is no apparent reason for having a class (except practice, practice, practice); standalone functions can recurse perfectly fine. Line 8 has a syntax error.

[slappy]

Thanks for the help.
@Peter87 I didnt knew that ^ was the XOR operator.Yeah the teacher wants to compute a raised to the power of b.
@keskiverto
I didnt knew that standalone functions can recurse so my first thought was to use a loop(so the function becomes recursive).
At line 8 do I need to open and close curly brackets?
Do I need to add this too?
1.Include math.h. (After source)
2.Return pow (a, b); instead of return a^b?

[keskiverto]

Iteration is not recursion.
Use of standard library function pow() is not recursion.
The point of the homework is clearly to learn to write a recursive function.

Advance in baby steps. Write first a function that computes the "a raised to the power of b" with a loop. (An iterative solution.) Standalone, no class.

Once you have that, we'll look at the recursion.

[slappy]

Thanks again for the help.
Here is my code

int a; int b;int p=1;int i;
for (i=1;i<=b;i++)
p=p*a;
return p;

[keskiverto]

That does not look like a function; merely a fragment of code.


Anyway, the effective calculation in that code does:

result = 1*a*a*..*a    where a repeats b times

Multiplication is commutative, so we can write:

result = a*a*..*a*1    where a repeats b times

Lets try to have something function-like in it:

power(a, b) = a*a*..*a*1    where a repeats b times

What if we have one less a?

power(a, b-1) = a*a*..*a*1    where a repeats b-1 times

Lets substitute that to the previous:

power(a, b) = a * power(a, b-1)

If power(a, b) can be calculated by calculating first the power(a, b-1) then
surely the power(a, b-1) can be calculated by calculating first the power(a, b-2)
and so forth?

Almost. What if the b <= 0? You don't want to calculate power(a, 0) with a*power(a,-1)

[slappy]

Thanks again for the detailed explanation.
I supposed that both numbers were positive.

[keskiverto]

I supposed that both numbers were positive.

That is only a minor issue. In recursion every input will face that same problem.

For example, 2^4
==2 * 2^3
==2 * 2 * 2^2
==2 * 2 * 2 * 2^1
==2 * 2 * 2 * 2 * 2^0
==2 * 2 * 2 * 2 * 2 * 2^-1 // is it?
==2 * 2 * 2 * 2 * 2 * 2 * 2^-2 // is it, really?
==2 * 2 * 2 * 2 * 2 * 2 * 2 * 2^-3 // will this ever end?

A recursive function has to have a condition that will prevent further recursion.

[Precious roy]

keskiverto: i don't mean to but in your doing a pretty good job of explaining things, other than i don't think he understands what recursion is so let me help you out a bit.

Recursion is when a function calls its self multiple times to do some thing. its kind of like looping but you use the call stack to do it and you don't have infinite times to call it(your stack is a finite recourse). so to help you out here is some skeleton code,try making your assignment work with this.

#include <iostream>

int PowerOf(int a, int b)
{
	// your code here
	
	return PowerOf(a, b--); // the actual recursion part Note:b-- part is part of the condition that keskiverto mentioned 
}


int main()
{
	float pow = PowerOf(5, 2);

	std::cout << pow << "\n";

	float pow2 = PowerOf(11, 2);

	std::cout << pow2 << "\n";

	std::cin.get(); //pause

	return 0;
}

also go here for some extra info on recursion.
http://www.cplusplus.com/articles/D2N36Up4/

Edit: video on call stack and recursion: https://www.youtube.com/watch?v=k0bb7UYy0pY

[slappy]

@Keskiverto thanks a lot for your patience and your replies.
I feel so stupid becouse you are explaning this like im 5(thank you ) and I still didn't understood it.So basically you are saying that I need a condition to stop the recursion.Edit: I guess the condition is b=0 ?
I thought that using the <= operator would work becouse
i starts at 1
i<=b means that i dosent get greater than b
so it calculates p=p*a b times.
But anyways I thought recursive means using the loop ( for) as we have never done something else besides "for" and "while"(we have never talked about recursive functions or call stack). @Precious roy , thanks a lot for the reply and for giving me a general idea about recursion and call stack.Also the code was working perfectly and helped me a lot.

[Precious roy]

slappy: no problem. um just wondering can you post the code you have we might still be able to give you some more advice if you want it ;}

[slappy]

Yeah of course.
Sorry I totally forgot to update the post.
Anyways here is the code.I tested it few times with different numbers and it was working fine.Hopefully its is right way to do it.

#include <iostream>                 
int Powerof (int a , int b )
{ 
     int x=1,i;
for (i=1;i<=b;i++)
if (b==0)
return Powerof (a,b--);
else 
     x=x*a;
     return x;
}
int main ()
{
    float pow = Powerof (5,2);
    std::cout << pow << "\n";
    float pow2 = Powerof (11,0);
    std::cout << pow2 << "\n";
    std::cin.get();
    return 0;
}

[keskiverto]

No. This recursion does not require any loop structure. Sadly, the skeleton by Precious roy is misleading in several ways.

Remember, the Powerof(a, b) should return a * Powerof(a, b-1) or 1, if b<1.

Here are some examples of recursion:

#include <iostream>

void foo( const int * arr, size_t n ) {
    if ( 0 < n ) {
        std::cout << ' ' << arr[n-1];
        foo( arr, n-1 );
    }
}

void bar( const int * arr, size_t n ) {
    if ( 0 < n ) {
        bar( arr, n-1 );
        std::cout << ' ' << arr[n-1];
    }
}

int gaz( const int * arr, size_t n ) {
    if ( 0 < n ) {
        return arr[n-1] + gaz( arr, n-1 );
    }
    else {
        return 0;
    }
}

int main()
{
    constexpr size_t Size = 4;
    constexpr int array[Size] { 42, 7, 3, 66 };

    foo( array, Size );
    std::cout << '\n';

    bar( array, Size );
    std::cout << '\n';

    std::cout << "Sum = " << gaz( array, Size ) << '\n';

    return 0;
}

[Precious roy]

keskiverto: your right it does not require any loops. although i don't know why it is misleading? can you explain why? i removed the return condition that's all, i wanted him to do it.

slappy: as for your code let me give you some rules.
- your not allowed to use loops
- the function should call itself

start off with thinking what would be a condition to return from the function.
also b-- decrements b http://en.wikipedia.org/wiki/Increment_and_decrement_operators

also you dont seem to understand recursion to well, try reading through
http://www.cplusplus.com/articles/D2N36Up4/ again

[keskiverto]

@Precious roy:
* The pow and pow2 in your main() are floats, even though the PowerOf() returns int. That is a legal conversion, but does not serve any purpose in this program.

* The return PowerOf( a, b-- ); does same as:

int temp = PowerOf( a, b );
--b;
return temp;

Post-decrement returns a copy of the old value.

Writing:

int PowerOf(int a, int b)
{
	// your code here
	
	return PowerOf(a, b--); // the actual recursion part
}

... creates impression that line 5 is as it should be and should stay unchanged.

Lets take again a=2, b=2. Lets ignore the effect of post-decrement and pretend that
PowerOf(2,2) effectively has line:
return PowerOf(2,1);
Similarly, PowerOf(2,1) has line:
return PowerOf(2,0);

Furthermore, assume that slappy has added a condition on line 3 so that PowerOf(2,0) returns value 1.
Therefore, PowerOf(2,1) returns the value returned by PowerOf(2,0), i.e. 1.
Therefore, PowerOf(2,2) returns the value returned by PowerOf(2,1), i.e. 1.

This would be closer to what is needed.

int PowerOf(int a, int b)
{
	// your code here
	int sub = PowerOf(a, b--); // the actual recursion part
	// your code here
}

@slappy:
This is a test program that uses your iterative (loop) "powerof" code.

#include <iostream>
#include <iomanip>
using std::setw;
using std::cout;

int Powerof( int a, int b ) {
  int p=1;
  int i;
  for (i=1;i<=b;i++)
    p=p*a;
  return p;
}

int main()
{
  cout << "   ";
  for ( int col = 1; col < 8; ++col ) {
    cout << setw(1+col) << col << ' ';
  }
    cout << '\n';
  for ( int row = 2; row < 10; ++row ) {
    cout << row << ": ";
    for ( int col = 1; col < 8; ++col ) {
      cout << setw(1+col) << Powerof( row, col ) << ' ';
    }
    cout << '\n';
  }
  return 0;
}

Replace the code of Powerof with a recursive version.

[Precious roy]

keskiverto : You are indeed right, i just deleted my code from the function and i did have the return at the end as fall through. when he has it working i will post the way i did it. its probably not the most elegant way of doing it but it works ;}. thanks for explaining i will dependently be more clear next time when i help some one.