CODEWITHSUNDEEP
c++crecursion
Azad Omer
Azad Omer

Reputation: 49

Finding greatest power devisor using recursion?

The question asks me to find the greatest power devisor of (number, d) I found that the function will be like that:

number % d^x ==0

I've done so far using for loop:

int gratestDevisor(int num, int d){
    int p = 0;
    for(int i=0; i<=num; i++){
        //num % d^i ==0
        if( (num % (int)pow(d,i))==0 )
            p=i;
    }
    
    return p;
}

I've tried so much converting my code to recursion, I can't imagine how to do it and I'm totally confused with recursion. could you give me a tip please, I'm not asking you to solve it for me, just some tip on how to convert it to recursion would be fine.

Upvotes: 0

Views: 85

Answers (3)

user9706
user9706

Reputation:

A recursive function consist of one (or more) base case(es) and one (or more) calls to the function itself. The key insight is that each recursive call reduces the problem to something smaller till the base case(es) are reached. State (like partial solutions) are either carried in arguments and return value.

You asked for a hint so I am explicitly not providing a solution. Others have.

Upvotes: 1

Marek R
Marek R

Reputation: 37657

Recursive version (which sucks):

int powerDividing(int x, int y)
{
    if (x % y) return 0;
    return 1 + powerDividing(x/y, y);
}

Upvotes: 0

Damien
Damien

Reputation: 4864

Here is a simple method with recursion. If ddivides num, you simply have to add 1 to the count, and divide num by d.

#include <stdio.h>

int greatestDevisor(int num, int d){
    if (num%d) return 0;
    return 1 + greatestDevisor (num/d, d);
}

int main() {
    int num = 48;
    int d = 2;
    int ans = greatestDevisor (num, d);
    printf ("%d\n", ans);
    return 0;
}

Upvotes: 1

Related Questions