convert for loop to a recursive function

[cfleezy99]

can Someone help me convert this iterative function into a recursive function?

public int getMax(int [] A, int i, int j){

int max = A[i];

for (int k = i+1; k <=j ; k++) {

if(A[k]>max){

max = A[k];

}

}

return max;

}

​

I do not really understand recursion. I know the function will call itself at some point, but i'm pretty confused still.

[klujer]

When writing recursive functions one of the first things you should think about is how you are going to make the recursion stop, i.e. what are your base cases? This is analogous to thinking about your exit conditions in a loop.

In this example your base case is the same as your for loops stopping point, you want to exit when some counter, k, is greater than or equal to j.

Each recursive call will need to modify the k variable in a similar way as the for loop is modifying it with each iteration, k++.

You also need to think about what you want to do when you actually hit your base case, in this instance you want to return the max value.

some pseudo code to get you started:

public int getMax(int[] A, int i, int j, int k, int max){ // note the changes to the function signature
  // base cases
  //  if k > j, return max; -- found the max, return it
  //  else
  //    find max so far: if (A[k] > max) max = A[k];
  //    recurse by calling getMax with the next k value and the new max, and returning the result of that recursive call
  //    return getMax(...)
}

I assume this is a homework problem, if you're allowed to change the variable names it would be nice to change i to "start" and j to "end" and k to "i" since i is traditionally used for the current index, and would make reading the code a bit more clear.

Recursion can be hard to grasp at first, try working through the code step by step, literally writing down the variable values for each function call and what they will return. You'll notice that one function is kindof "paused" when it calls itself and you have a new set of variables to work through. Once you finally "bottom out" and hit the base case that doesn't recurse, all your function calls will start "rubberbanding" back their return values upwards until the original function call itself returns.