Write a recursive function named removeEvens that accepts a stack of integers and an integer K as parameters and removes the first K even numbers starting from the top of the stack, leaving all other elements present in the same relative order.
You should also return the number of elements that were removed.
For example, consider a stack variable named st that contains the following elements:
{8, 1, 4, 9, 5, 2, 6, 7, 12}
^ ^
bottom top
The call of removeEvens(st, 3) should remove the 3 even element values closest to the top of the stack, which are 12, 6, and 2.
The stack's contents after the call should be {8, 1, 4, 9, 5, 7} and the function should return 3 to indicate that three elements were removed.
If the stack does not contain K even values, remove as many evens as you can and return the number that were removed.
For example, if the call were removeEvens(stack, 7), there are not 7 even values in the stack, but you should remove all five even values, 12, 6, 2, 4, and 8, leaving the stack storing {1, 9, 5, 7}.
You would return 5 to indicate that five elements were removed.
If the stack does not contain any elements with even values, the stack should not be modified and you should return 0.
Constraints:
- Your solution must be recursive. Do not use any loops.
- Do not use any auxiliary collections or data structures to solve this problem, such as
stack, queue, vector, map, set, array, string, etc.
This includes making a "backup" of the stack passed as a parameter, or passing it by value to copy it.
- Do not declare any global variables.
