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

Tags: , ,



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;
}   


Source: stackoverflow