Power using recursion

Question

Well, I’m doing a basic code in C, I’m not very good with this language, I’m learning it, although I’ve seen it not used much. It consists of doing the power operation through recursion. The problem lies in the output when the power is greater than 10

//Input: //6 20

//Output: //-1190133760

The code:

#include <stdio.h>


int potencia(A, N){
    int x;
    if(N == 0){
    return 1;
    }

    return A*potencia(A, N-1);

}

int main(){
    int A, N;
    scanf("%d %d", &A &N);
    printf("%d\n", potencia(A, N));

}

as can be seen, the output is a totally absurd number, but I do not why and how it happens anyone can explain to me and if possible explain what I have to do to generate the right output?

Answer 1

Your problem here is the type of variables you are using. In C, the native type int accepts values at most until 2147483647, That’s why when you try to calculate 6 ^ 15 the result makes no sense.

One solution is to use the type unsigned long long int, which accepts values between 0 and 18446744073709551615. Your algorithm would look like this:

# include <stdio.h>

unsigned long long int potencia(unsigned long long A, unsigned long long N){
    if(N == 0){
        return 1;
    }
    return A*potencia(A, N-1);
}

int main(){
    unsigned long long int A, N;
    scanf("%llu %llu", &A, &N);
    printf("%llu\n", potencia(A, N));
}

Execution of him:

$ gcc main.c && ./a.out
6 20
3656158440062976

Remarks: the guy unsigned long long exists only from the specification C99 ^en. If you are running this code in an earlier version of C, worth taking a look in that question how to deal with gigantic numbers, and in that library of gigantic numbers for C.