CODEWITHSUNDEEP
c++recursion
Lilith Ho
Lilith Ho

Reputation: 13

Recursion program doesn't work for big inputs

I tried to write an answer to the question from this site - https://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/kro/

It's addition to lesson about recursion so I came up with a code that uses it. It should show (a+1)^b modulo-10000 remainder. Unfortunately, for small numbers my program works, but when it reaches bigger numbers it just... doesn't - for example:


a = 1
b = 4
output is 16, which is correct.


a = 2
b = 3
output is 27, which is correct.

a = 2
b = 100
it gives me output -8495, which is completely incorrect.

I tried searching for it, but I didn't find proper solution to my problem, 'cause I don't really know what happened. I was thinking that maybe it's because of too small data type but changing int to long int, didn't change anything.

Here is my code:

#include <iostream>
using namespace std;

int pot(int a, int b){
    if (b == 1)
        return a;
    if (b % 2 == 0) //test for even number
        return pot(a, b / 2) * pot(a, b / 2);
    else //make it even number
        return a * pot(a, b - 1);
}

main(){
    int a, b;
    int P;
    cin>>P;
    for(int i = 1; i<=P; i++){
        a = 0;
        b = 0;
        cin>>a;
        cin>>b;
        cout<<endl<<(pot(a+1, b))%10000;
    }
}

Upvotes: 1

Views: 240

Answers (1)

Tom Karzes
Tom Karzes

Reputation: 24062

Instead of taking the remainder only of the final result, you should take it every time pot returns a value. The result should be correct, since you're just multiplying the results by things, and (x*y) % m should equal ((x % m) * (y % m)) % m for positive x, y, and m.

Try this:

int pot(int a, int b){
    int r;
    if (b == 1)
        r = a;
    else if (b % 2 == 0) //test for even number
        r = pot(a, b / 2) * pot(a, b / 2);
    else //make it even number
        r = a * pot(a, b - 1);
    return r % 10000;
}

Also, you're replicating the computation of pot(a, b / 2) in the second case, which will slow it down tremendously. You should change:

r = pot(a, b / 2) * pot(a, b / 2);

to:

r = pot(a, b / 2);
r *= r;

(And of course add curly braces.) That should be much faster.

Update: I just corrected my answer to include an else for the second case that was not present in the original code. It was not needed in the original code, but was needed after my changes.

Upvotes: 5

Related Questions