Home > Software design >  What is the meaning of adding another parameter to recursive function
What is the meaning of adding another parameter to recursive function

Time:10-20

public static int min2(Stack <Integer> st, int min) {
        if(st.isEmpty()) {
            return min;
        }
        int num= st.pop();
        if(num<min) {
            min=num;
        }
        return min2(st,min);

I wrote this code for finding min value in stack and I used another parameter->int min which I'd like to get rid of & don't understand what I should ask from the user to enter to the parameter.

CodePudding user response:

Your code can be brought down to this iterative approach:

public static min3(Stack<Integer> st) {
    int min = Integer.MAX_VALUE;
    while(!stack.isEmpty()) {
        int current = stack.pop();
        if(current < min)
            min = current;
    }
    return min;
}

This gets rid of the parameter, but if you want to keep it recursive, you have to somehow store the current minimum. Either, passed as a parameter, or stored in a static variable.

Also: Because parameter-objects get passed as references, you will destroy your stack in the process.

CodePudding user response:

Recursion deals with a partial result in every call, and an extra termination condition. This will result in at least one extra parameter in general.

Here the parameter is the minium of the popped elements.

public static int min(Stack <Integer> st) {
    return minRecursively(st, Integer.MAX_VALUE);
}
private static int minRecursively(Stack <Integer> st, int min) {
    if (st.isEmpty()) {
        return min;
    }
    int num = st.pop();
    if (num < min) {
        min = num;
    }
    return minRecursively(st, min);
}

Your implementation emptied the entire stack. Better would be:

private static int minRecursively(Stack <Integer> st, int min) {
    if (st.isEmpty()) {
        return min;
    }
    int num = st.pop();
    if (num < min) {
        min = num;
    }
    min = minRecursively(st, min);
    stack.push(num); // Leave the stack unchanged.
    return min;
}
  • Related