Changing Code to Recursion

Question

Can anyone help me convert this code to make it run recursively? I'm not exactly sure how. The goal of the code is to count the amount of numbers in an array are divisible by k.

int[] a = {1,2,3,4,5,6,9}
int k = 3;
int count;
for (int i = 0;i <a.length; i ++){
    if (a[i] % 3 == 0){
        count ++;
    }
}

return count;

For reference, this is not a good fit for recursion. At least not in Java. A recursive solution wouldn't be any simpler or less error-prone than an iterative one. — cHao
– cHao, Commented Oct 13, 2011 at 2:23

user684934 · Accepted Answer · 2011-10-13 02:07:39Z

1

The trick is to find what's changing with each loop iteration, and passing that into the recursive method:

int count(int[] array, int k, int i){
    if(i>=array.length)
        return 0;
    boolean divisible = array[i] % k == 0;
    return count(array, k, i+1) + (divisible?1:0);
}

answered Oct 13, 2011 at 2:07

user684934

Sign up to request clarification or add additional context in comments.

2 Comments

John Smith Over a year ago

Hi, I was wondering what that ? mark in the return statement meant. Also, just checking, the Big O for this is O(n) right? It depends on the size of the array.

user684934 Over a year ago

Showing that it's O(n) is easy if you show that it is called exactly n times by setting and using a loop invariant. a?b:c is shorthand for if a {b;} else {c;}

DavidC · Accepted Answer · 2011-10-13 02:25:16Z

1

No need to use recursion. You can simply check whether each member of the list is divisible by 3. Then count the number of Trues. In Mathematica this is straightforward.

a = {1, 2, 3, 4, 5, 6, 9};
Count[Divisible[#, 3] & /@ a, True]

This returns: 3

answered Oct 13, 2011 at 2:25

DavidC

3,0661 gold badge22 silver badges30 bronze badges

Collectives™ on Stack Overflow

Changing Code to Recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related