Question

Give the output of the following program. Then explain what the foo() method does, in general, for a given input. Is foo() a tail-recursive method? Why or why not?

class SomeThing {

    public static void main(String args[]) {

        System.out.println(foo(6));

    }

    private static int foo(int input) {

        if (input <= 0) {

            throw new RuntimeException("invalid input");

        }

        else if (input == 1) {

            return 1;

        }

        else if (input % 2 == 0) {

            return foo(input - 1);

        }

        else {

            return input * foo(input-2);

        }

    }

}

Answer 1

OUTPUT:

15

Explaination:

5 * 3 * 1 = 15

The above program gives the multiplication of all odd numbers less than the number passed while initially calling the function.

Tracing:

Step 1: foo(6)

Step 2: foo(6-1) [since (6%2) == 0, so, this function is going to call recursively passing input-1]

Step 3: 5 * foo(5-2) [Here, else part runs, It is going to multiply the input with foo(input -2)]

Step 4: 5 * 3 * foo(1) [Here, foo(1) is going to return 1]

Step 5: 5 * 3 * 1 [The final value is returned]

Step 6: 15 [Output]

This function is not a tail-recursive function.

The function is not tail recursive because the value returned by foo(input-2) from Step3 is used in computation in the further steps.