So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came up with:

  int Power (int a, int n)
 { if ( n == 0 )
  return 1;
   if ( n % 2 == 0)
  return Power(Power(a, n/2), 2);
   else return Power(Power(a, n/2), 2)*a;

The code compiles well, but leads to a segmentation fault. On debugging, I came to the conclusion that recursive call within the argument list is not acceptable. That is, something like

  return Power(Power(a, n/2), 2)


  int m = Power(a, n/2);
  return Power(m, 2);

is not allowed but

  int m = Power(a, n/2);
  return m*m;

is allowed. Why is this the case? Is this true only in C++, or is it a general phenomenon?

  • $\begingroup$ ex falso… How is Power(2, 2) supposed to be evaluated? Can you do it using pen&paper? $\endgroup$
    – greybeard
    Nov 23 '19 at 9:48
  • $\begingroup$ Ah! I get your point. Thanks. $\endgroup$ Nov 23 '19 at 10:05
  • $\begingroup$ Refer this for correct algorithm. $\endgroup$
    – kiner_shah
    Nov 23 '19 at 11:28

So I did a dry run of the algorithm as suggested by greybeard in the comments. It turns out that for any a and n, after a certain number of recursions, one ends up getting Power(1, 2). This leads to an infinite recursion because Power(1, 2) also leads to Power (1, 2) after a certain number of recursions.


Not the answer you're looking for? Browse other questions tagged or ask your own question.