Question

For the following recursive program, how many lines will func(123456) print out? What about in general, say func(N) where N is a really large integer? (Hint: Recall the time complexity for when we are "keep dividing by 2".)

int func(int n) {
if (n 0) ==
return 0;
else {
System.out.println("calculating ..."); return (n%10)+func((int) n/10);
}

Answer 1

The recursive function divides the number by 10 iteratively and prints a line for each digit, with a time complexity of O(log N). Thus, it will produce as many lines as there are digits in the input number.

Step-by-step explanation:

The question is asking about a recursive function that prints out a message before it divides a number by 10 and adds the remainder to the result of the next recursive call. We are dealing with a process that is analogous to breaking down the number into its individual digits. So, for example, func(123456) will print a line for each of its digits, which is 6 lines in total. In general, the count is equivalent to the number of digits in the integer provided. The time complexity is O(log N) since the function recursively divides the number by 10 until it becomes 0, which is a characteristic of logarithmic time complexity.