# Refactor this recursive method?

I'm pretty new to the idea of recursion and this is actually my first attempt at writing a recursive method.

I tried to implement a recursive function Max that passes an array, along with a variable that holds the array's size in order to print the largest element.

It works, but it just doesn't feel right!

I have also noticed that I seem to use the static modifier much more than my classmates in general...

Can anybody please provide any general tips as well as feedback as to how I can improve my code?

``````public class RecursiveTry{

static int[] n = new int[] {1,2,4,3,3,32,100};
static int current = 0;
static int maxValue = 0;
static int SIZE = n.length;

public static void main(String[] args){
System.out.println(Max(n, SIZE));
}

public static int Max(int[] n, int SIZE) {
if(current <= SIZE - 1){
if (maxValue <= n[current]) {
maxValue = n[current];
current++;
Max(n, SIZE);
}
else {
current++;
Max(n, SIZE);
}
}
return maxValue;
}
``````

}

Asked by: Sophia858 | Posted: 21-01-2022

Your use of static variables for holding state outside the function will be a source of difficulty.

An example of a recursive implementation of a max() function in pseudocode might be:

``````function Max(data, size) {
assert(size > 0)
if (size == 1) {
return data
}
maxtail = Max(data[1..size], size-1)
if (data > maxtail) {
return data
} else {
return maxtail
}
}
``````

The key here is the recursive call to Max(), where you pass everything except the first element, and one less than the size. The general idea is this function says "the maximum value in this data is either the first element, or the maximum of the values in the rest of the array, whichever is larger".

This implementation requires no static data outside the function definition.

One of the hallmarks of recursive implementations is a so-called "termination condition" which prevents the recursion from going on forever (or, until you get a stack overflow). In the above case, the test for `size == 1` is the termination condition.

Answered by: Alfred444 | Posted: 22-02-2022

Making your function dependent on static variables is not a good idea. Here is possible implementation of recursive Max function:

``````int Max(int[] array, int currentPos, int maxValue) {
// Ouch!
if (currentPos < 0) {
raise some error
}
// We reached the end of the array, return latest maxValue
if (currentPos >= array.length) {
return maxValue;
}
// Is current value greater then latest maxValue ?
int currentValue = array[currentPos];
if (currentValue > maxValue) {
// currentValue is a new maxValue
return Max(array, currentPos + 1, currentValue);
} else {
// maxValue is still a max value
return Max(array, currentPos + 1, maxValue);
}
}
...

int[] array = new int[] {...};
int currentPos = 0;
int maxValue = array[currentPos] or minimum int value;
maxValue = Max(array, currentPos, maxValue);
``````

Answered by: Lana113 | Posted: 22-02-2022

A "max" function is the wrong type of thing to write a recursive function for -- and the fact you're using static values for "current" and "maxValue" makes your function not really a recursive function.

Why not do something a little more amenable to a recursive algorithm, like factorial?

Answered by: Walter214 | Posted: 22-02-2022

"not-homework"?

Anyway. First things first. The

``````static int[] n = new int[] {1,2,4,3,3,32,100};
static int SIZE = n.length;
``````

have nothing to do with the parameters of Max() with which they share their names. Move these over to main and lose the "static" specifiers. They are used only once, when calling the first instance of Max() from inside main(). Their scope shouldn't extend beyond main().

There is no reason for all invocations of Max() to share a single "current" index. "current" should be local to Max(). But then how would successive recurrences of Max() know what value of "current" to use? (Hint: Max() is already passing other Max()'s lower down the line some data. Add "current" to this data.)

The same thing goes for maxValue, though the situation here is a bit more complex. Not only do you need to pass a current "maxValue" down the line, but when the recursion finishes, you have to pass it back up all the way to the first Max() function, which will return it to main(). You may need to look at some other examples of recursion and spend some time with this one.

Finally, Max() itself is static. Once you've eliminated the need to refer to external data (the static variables) however; it doesn't really matter. It just means that you can call Max() without having to instantiate an object.

Answered by: Blake611 | Posted: 22-02-2022

As others have observed, there is no need for recursion to implement a Max function, but it can be instructive to use a familiar algorithm to experiment with a new concept. So, here is the simplified code, with an explanation below:

``````public class RecursiveTry
{
public static void main(String[] args)
{
System.out.println(Max(new int[] {1,2,4,3,3,32,100}, 0, 0));
}

public static int Max(int[] n, int current, int maxValue)
{
if(current < n.Length)
{
if (maxValue <= n[current] || current == 0))
{
return Max(n, current+1, n[current]);
}
return Max(n, current+1, maxValue);
}
return maxValue;
}
}
``````

all of the static state is gone as unnecessary; instead everything is passed on the stack. the internal logic of the Max function is streamlined, and we recurse in two different ways just for fun

Answered by: Abigail972 | Posted: 22-02-2022

Here's a Java version for you.

``````public class Recursion {

public static void main(String[] args) {
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
System.out.println("Max: " + max(0, data));
}

public static int max(int i, int[] arr) {
if(i == arr.length-1) {
return arr[i];
}

int memo = max(i+1, arr);
if(arr[i] > memo) {
return arr[i];
}
return memo;
}
}
``````

The recurrence relation is that the maximum element of an array is either the first element, or the maximum of the rest of the array. The stop condition is reached when you reach the end of the array. Note the use of memoization to reduce the recursive calls (roughly) in half.

Answered by: Sydney565 | Posted: 22-02-2022

You are essentially writing an iterative version but using tail recursion for the looping. Also, by making so many variables static, you are essentially using global variables instead of objects. Here is an attempt at something closer to a typical recursive implementation. Of course, in real life if you were using a language like Java that doesn't optimize tail calls, you would implement a "Max" function using a loop.

``````public class RecursiveTry{
static int[] n;

public static void main(String[] args){
RecursiveTry t = new RecursiveTry(new int[] {1,2,4,3,3,32,100});
System.out.println(t.Max());
}

RecursiveTry(int[] arg) {
n = arg;
}

public int Max() {
return MaxHelper(0);
}

private int MaxHelper(int index) {
if(index == n.length-1) {
return n[index];
} else {
int maxrest = MaxHelper(index+1);
int current = n[index];
if(current > maxrest)
return current;
else
return maxrest;
}
}
}
``````

Answered by: Dexter210 | Posted: 22-02-2022

In Scheme this can be written very concisely:

``````(define (max l)
(if (= (length l) 1)
(first l)
(local ([define maxRest (max (rest l))])
(if (> (first l) maxRest)
(first l)
maxRest))))
``````

Granted, this uses linked lists and not arrays, which is why I didn't pass it a size element, but I feel this distills the problem to its essence. This is the pseudocode definition:

``````define max of a list as:
if the list has one element, return that element
otherwise, the max of the list will be the max between the first element and the max of the rest of the list
``````

Answered by: Audrey555 | Posted: 22-02-2022

A nicer way of getting the max value of an array recursively would be to implement quicksort (which is a nice, recursive sorting algorithm), and then just return the first value.

Here is some Java code for quicksort.

Smallest codesize I could get:

``````public class RecursiveTry {
public static void main(String[] args) {
int[] x = new int[] {1,2,4,3,3,32,100};
System.out.println(Max(x, 0));
}

public static int Max(int[] arr, int currPos) {
if (arr.length == 0) return -1;
if (currPos == arr.length) return arr;
int len = Max (arr, currPos + 1);
if (len < arr[currPos]) return arr[currPos];
return len;
}
}
``````

A few things:

1/ If the array is zero-size, it returns a max of -1 (you could have another marker value, say, -MAX_INT, or throw an exception). I've made the assumption for code clarity here to assume all values are zero or more. Otherwise I would have peppered the code with all sorts of unnecessary stuff (in regards to answering the question).

2/ Most recursions are 'cleaner' in my opinion if the terminating case is no-data rather than last-data, hence I return a value guaranteed to be less than or equal to the max when we've finished the array. Others may differ in their opinion but it wouldn't be the first or last time that they've been wrong :-).

3/ The recursive call just gets the max of the rest of the list and compares it to the current element, returning the maximum of the two.

4/ The 'ideal' solution would have been to pass a modified array on each recursive call so that you're only comparing the first element with the rest of the list, removing the need for currPos. But that would have been inefficient and would have bought down the wrath of SO.

5/ This may not necessarily be the best solution. It may be that by gray matter has been compromised from too much use of LISP with its CAR, CDR and those interminable parentheses.

Answered by: Walter697 | Posted: 22-02-2022

First, let's take care of the static scope issue ... Your class is defining an object, but never actually instantiating one. Since main is statically scoped, the first thing to do is get an object, then execute it's methods like this:

``````public class RecursiveTry{

private int[] n = {1,2,4,3,3,32,100};

public static void main(String[] args){
RecursiveTry maxObject = new RecursiveTry();
System.out.println(maxObject.Max(maxObject.n, 0));
}

public int Max(int[] n, int start) {
if(start == n.length - 1) {
return n[start];
} else {
int maxRest = Max(n, start + 1);
if(n[start] > maxRest) {
return n[start];
}
return maxRest;
}
}

}
``````

So now we have a RecursiveTry object named maxObject that does not require the static scope. I'm not sure that finding a maximum is effective using recursion as the number of iterations in the traditional looping method is roughly equivalent, but the amount of stack used is larger using recursion. But for this example, I'd pare it down a lot.

One of the advantages of recursion is that your state doesn't generally need to be persisted during the repeated tests like it does in iteration. Here, I've conceded to the use of a variable to hold the starting point, because it's less CPU intensive that passing a new int[] that contains all the items except for the first one.

Answered by: Kimberly230 | Posted: 22-02-2022

# Similar questions

java - Recursive Array Traversal Problems

I am having some stackoverflow issues and hopefully someone can give me some insight into a non/less-recursive solution. Ident[][] map = ... private int explore(Ident item, int xcoord, int ycoord) { if ((map[xcoord][ycoord] == null) || !map[xcoord][ycoord].equals(item)) return 0; map[xcoord][ycoord] = null; int sumX, sumY, counter = 1; item.translate(xcoord, ycoord); for ...

java - Make a recursive method pause in every recurse and continue with click

I have a recursive method that changes the value of a variable in every recursion, then it shows that value on the JPanel, and then I would like to pause (here is my problem) until I click (it pauses in every new recurse). Then when I click this method continues to do the next recursion. The following code is just the structure of how my real program looks like and how I tried to implement that. ...

java - How to collect the result of a recursive method

I iterate through a tree structure to collect the paths of the leaf nodes. Which way do you prefer to collect the result of the operation: a) merge the results of the children and return this private Collection&lt;String&gt; extractPaths(final Element element, final IPath parentPath) { final IPath path = parentPath.append(element.getLabel()); final Collection&lt;Element&gt; children = getEle...

java - convert a recursive structure to xml with jsp

Let's say I have a recursive data structure class Tree { private Tree right; private Tree left; private int data; .... } I want to convert it to xml with jsp, so my ui tree widget can load the xml page with Ajax and construct a tree (with expandable/collapsable nodes, etc). The xml would look something like this: &lt;tree&gt; &lt;tree&gt...

java - How can I make a recursive version of my iterative method?

I am trying to write a recursive function in Java that prints the numbers one through n. (n being the parameter that you send the function.) An iterative solution is pretty straightforward: public static void printNumbers(int n){ for(int i = 1; i &lt;= n; i++){ System.out.println(i); i++; } As a new programmer, I'm having troubles figuring out how a recursive vers...

binary search tree recursive subtree in java

Can anyone point me to a code example (java preferably) or psuedocode that uses recursion to return a subtree that contains all nodes with keys between fromKey and toKey. So if I was to call Tree.subtree(5,10) it should return all nodes in the BST that have keys between 5 and 10 inclusive - but I can't use loops or helper methods...only recursive calls to the subtree method, which takes fromKey and toKey as paramet...

java - Basic recursive method - factorial

I am practicing recursion and I can't see why this method does not seem to work. Any ideas? public void fact() { fact(5); } public int fact(int n) { if(n == 1){ return 1; } return n * (fact(n-1)); } } Thanks

java - TrueZip Recursive Unzipping?

Does anyone have experience with the TrueZip java library? I'm trying to do what should be a simple task, unzipping an archive that contains subfolders, and I've so far been unable to get it to work. (The reason I'm using TrueZip is because of the encoding foreign character bug in the java.util.zip methods) L...

java - Recursive function to match a string against a wildcard pattern

So I've been trying to solve this assignment whole day, just can't get it. The following function accepts 2 strings, the 2nd (not 1st) possibly containing *'s (asterisks). An * is a replacement for a string (empty, 1 char or more), it can appear appear (only in s2) once, twice, more or not at all, it cannot be adjacent to another * (ab**c), no need to check th...

java - recursive method calls

String url = getUrl(); try{ Connection con = getConnection(url, username, pwd); }catch(ConnectionException e){ cleanUpUrl(url); url = getUrl(); con = getConnection(url, username, pwd); } I've to do something like above. if I don't get Connection with one URL then I'll be trying with another URL. Likewise there are 10URLs which I've to try one after the other. How will I write the me...

# Still can't find your answer? Check out these amazing Java communities for help...

Java Reddit Community | Java Help Reddit Community | Dev.to Java Community | Java Discord | Java Programmers (Facebook) | Java developers (Facebook)