Finding the Base 2 Logarithm of a number using Recursion in java

I’m trying to write a recursive method in Java to find the base 2 log for multiples of 2.

I’ve successfully computed the log using this recursive method.

import java.util.*;

class temp
{
    static int log(int number)
    {
        if(number==1)
            return 0;
        return log(number/2)+1;
    }   
    public static void main(String s[])
    {
        Scanner input=new Scanner(System.in);
        System.out.println("Enter Multiple of 2:");
        System.out.println("Log is:"+log(input.nextInt())); //calling log with return value of nextInt()
    }
}   

Where I’ve run aground is trying to implement the same program using a different method , a method where i start multiplying from 2 in recursive calls until it becomes equal to the given number. Here’s what i’ve tried:

class logarithmrecursion
    {
        static int step=1;
        static int log(int number)
        {
            final int temp=number;
            if(number>=temp && step!=1)
                return 0;
            step++;
            return log(number*2)+1;
            
        }
    }

During the first call, number is equal to temp so i use a step variable to prevent the execution of the termination condition.If i don’t use “number” variable in the recursive call, i don’t have a way to accumulate the previous product but number variable is already equal to temp and will trigger the termination condition in the next recursive call , thus always giving output 1.

What can i do to make this program work?

Answer

The first, reducing, version has a fixed termination value of 1.

But the second version’s termination depends on the number, so you have to pass that into the recursive call. So, your main function calls a private recursive version:

static int log(int number) {
    return log(number, 1);
}

private static int log(int number, int current) {
    return current < number ? log(number, current * 2) + 1 : 0;
}

Note: Your algorithm rounds the value up. To give the (more expected) rounded down result, which agrees with (int)(Math.log(i) / Math.log(2)), use this variation:

private static int log(int number, int current) {
    return current <= number / 2 ? log(number, current * 2) + 1 : 0;
}

This kind of pattern – using a wrapper function – is common where initial state of the recursion needs to setup once, but we don’t want to burden the caller with having to know about what is an implementation choice.

---

Your first method may also be coded as one line:

static int log(int number) {
    return number == 1 ? 0 log(number/2) + 1;
}