CODEWITHSUNDEEP
javarecursion
Tack
Tack

Reputation: 121

How an outer method executes on an inner recursive method?

I've been exploring recursion and started by looking through some simple examples online, this one returns the max or min of an unsorted array.

I understand the idea that recursive calls stack up (ha), then get to the base case and unravel backwards. In this case, the recursive method is called within a method that find the minimum of two numbers, and I don't understand how the min() method executes on each of the recursive methods in a way that links the results of the recursive methods together to produce the correct result.

I've stepped through the code, but it has made me more confused.

Here's a java MCVE of the recursive function and sample main: 

public static int min(int a, int b){
    if (a<b)
        return a;
    return b;
}
public static int minValue(int arr[], int n){
    if(n == 0)
        return arr[0];
    return min(minValue(arr,n-1),arr[n-1]);
}
 public static void main(String[] args)
    int[] arr = {30,20,21,5,3};
    int minVal = minValue(arr,5);
    System.out.printf("%d", minVal);
}

The way I am tracing this code execution:

first call, in main: minValue(arr,5) n is 5
goes to the recursive method: return min(minValue(arr,4),arr{4}), n is 4
starts to execute min, looks at the first arg
minValue executes again: return min(minValue(arr,3),arr{3}) n is 3

...(does this until n==0 is reached)

then return arr[0] executes and sends "30" back to the int minVal in Main.

Clearly going straight from the return back to main like this is ignoring the build up of calls on the stack which are waiting to be executed, and that makes no sense. I feel like I'm missing how min() works on minVal().

TL;DR Can anyone help me trace the execution of min() on the minVal() calls?

Upvotes: 0

Views: 585

Answers (1)

John Kugelman
John Kugelman

Reputation: 361655

then return arr[0] executes and sends "30" back to the int minVal in Main.

This is where the mistake is. It doesn't immediately return to main(). It returns it back to the previous recursive call, where n is 1.

Then that call is able to evaluate min(minValue(arr,0),arr[0]) because the minValue(arr,0) call has returned 30. It calls min(30,30) and returns that value back to the previous recursive call where n is 2.

Now that minValue(arr,1) has returned 30, this call is able to evaluate min(minValue(arr,1),arr[1]) == min(30,20) == 20 and return that back to the previous recursive call where n is 3.

And so on back through the stack in reverse until all of the calls have unwound.

Upvotes: 1

Related Questions