C program recursive function

Question

I have a small problem I want to build a function that returns with recursive function the nⁿ expression with one parameter in the calling function. Can someone help me? My thought so far :

int powerThroughRecursion(int n) {      
    if (n == 0) {
        return 1;
    }
    if (n <= 1) {
        return n;
    }
    return n * powerThroughRecursion(n - 1);
}

Answer 1

Yes, you are actually computing n! there. One way to do it is the following:

#include <iostream>
#include <string>

int powerThroughRecusion(int n, int step) {   
    if (step < 1)
        return 1;

    return n * powerThroughRecusion(n, step - 1);
}

int main()
{
  std::cout << powerThroughRecusion(4, 4);
}

You multiply by n, but a step will tell you how much multiplications to be done.

[edit] using a single parameter function

#include <iostream>
#include <string>

int powerThroughRecusionInternal(int n, int step) {   
    if (step < 1)
        return 1;

    return n * powerThroughRecusionInternal(n, step - 1);
}

int powerThroughRecusion(int n)
{
   return powerThroughRecusionInternal(n, n);
}

int main()
{
  std::cout << powerThroughRecusion(2) << "\n";
  std::cout << powerThroughRecusion(4);
}

Answer 2

If you want a one parameter function. just hide and wrap the two parameter implementation version with another function call.

static int powerThroughRecusionImpl(int n, int power) {       
    if (power == 0) {
        return 1;
    }
    if (power == 1) {
        return n;
    }
    return n * powerThroughRecusionImpl(n ,power - 1);
}

int powerThroughRecusion(int n) {       
    return powerThroughRecusionImpl(n ,n);
}

Or if you want to be non thread-safe.

int powerThroughRecusion(int n) {       
    static int base = 0;

    if (!base) {
      base = n;
      n = powerThroughRecusion(n);
      base = 0;
      return n;
    } else {
      if (n == 0) {
        return 1;
      } else if (n == 1) {
        return base;
      }
      return base * powerThroughRecusion(n - 1);
    }
}