What does the following recursive function do Give a highlev

What does the following recursive function do? Give a high-level description, don\'t just reword the code into English (e.g., \"if the number is one then it returns 0\").

SB] What does the following recursive function do? Give a high-level description, don\'t just reword the code into English (e.g., \"if the number is one then it returns 0\") // assume number is always greater than 1 public static int foo (int number) public static int foo (int number) f f (number 1) return 0 else retur 1 foo (number/2);

Solution

class Test
{
   public static void main (String[] args)
   {
       System.out.println(foo(2));
   }
  
   public static int foo(int number)
   {
       if(number == 1)
       return 0;
       else
       return 1+foo(number/2);
   }
}

output:

1

foo(2) = 1+ foo(1) = 1+0 =1

foo(4) = 1+foo(2) = 1+1+foo(1) = 1+1+0 =2

foo(8) = 1+ foo(4) = 1+2 =3

foo(16) = 1+ foo(8) = 1+3 = 4

it is a recursive function which calls itself by dividing the argument by 2 and adding one.

number = 2 ^{(foo(number))}

32 = 2⁵ foo(32) =5