FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Recursive functions in java





davidv
Hi, I made a simple recursive function in Java to finds the maximum value in a given int[] array. Im wondering if theres a simpler solution to the given problem. Heres what it looks like:

Code:
public static int max(int[] x, int n, int e){
      if (n == x.length-1){
         e = x[n];
      }
      if (n == 0){
         return e;
      } else {
         if (e < x[n-1]){
            e = x[n-1];
         }
         return max(x, n-1, e);
      }
}


The x is the int[] array, n is the highest index and e is the highest value in the array. Alternatively a simple loop can be used but Im trying to practice using recursion so bare with me i.e. i wont respond nicely to those that suggest a loop instead Razz
Peterssidan
First of all I would remove the parameter e because we can use the return value of max to pass this information instead.
Code:
public static int max(int[] x, int n)
{
   if (n == 0)
   {
      return x[0];
   }
   return Math.max(max(x, n - 1), x[n]);
}


We can make it into one line if we want to. Not sure if it's more readable or not.
Code:
public static int max(int[] x, int n)
{
   return (n == 0 ? x[0] : Math.max(max(x, n - 1), x[n]));
}


It's not very nice to call this max function because you have to call it like max(array, array.length-1); One way to fix this is to declare another function called max that only takes the array and calls the recursive max function with the correct starting arguments.
Code:
public static int max(int[] x)
{
   return max(x, x.length - 1);
}
Now we can call it like max(array); much nicer! We can even make the 2 parameter max function private to make sure the user never calls it, but only uses our 1 parameter max function.
Fire Boar
A simpler to understand, non-recursive solution that only takes one parameter: the array itself.

Code:
public static int max(int[] x)
{
  if (x.length < 1)
  {
    throw new IllegalArgumentException("Empty input array, need at least one element.");
  }

  int highest = x[0];
  for (int i = 1; i < x.length; i++)
  {
    if (x[i] > highest)
    {
      highest = x[i];
    }
  }

  return highest;
}
davidv
Peterssidan wrote:
First of all I would remove the parameter e because we can use the return value of max to pass this information instead.
Code:
public static int max(int[] x, int n)
{
   if (n == 0)
   {
      return x[0];
   }
   return Math.max(max(x, n - 1), x[n]);
}


We can make it into one line if we want to. Not sure if it's more readable or not.
Code:
public static int max(int[] x, int n)
{
   return (n == 0 ? x[0] : Math.max(max(x, n - 1), x[n]));
}


It's not very nice to call this max function because you have to call it like max(array, array.length-1); One way to fix this is to declare another function called max that only takes the array and calls the recursive max function with the correct starting arguments.
Code:
public static int max(int[] x)
{
   return max(x, x.length - 1);
}
Now we can call it like max(array); much nicer! We can even make the 2 parameter max function private to make sure the user never calls it, but only uses our 1 parameter max function.


Ooooh. I like your solution. Using the Math API to return the max of n-1 and n. That's smart! I didn't think of using an API. Cool

Quote:
A simpler to understand, non-recursive solution that only takes one parameter: the array itself.


Loops are boring. Evil or Very Mad
Fire Boar
davidv wrote:
Loops are boring. Evil or Very Mad


They're also efficient. It's like a car journey: you should really want it to be boring. Simple code is maintainable and easy to prove for correctness.

A recursive version of this method is much better suited to a language with better list capabilities, especially a functional language. For example, a Haskell version of the code might be: (note: "max" is a Haskell builtin, as is "maximum", but I'm (re)defining maximum here)

Code:
maximum :: Ord a => [a] -> a -- Type signature: input list of a, output a, where a is any ordered type.
maximum [] = error "List cannot be empty!"
maximum (x:[]) = x
maximum (x:y:xs) = max x (maximum (y:xs))


Actually, this generalizes to any "list fold" function... Haskell in fact has a bunch of fold functions to make this sort of thing extremely easy indeed. foldl1 for instance takes a function and a list, then applies that function to the first and second elements, then to the result and the third element, then to the result and the forth element and so on. See below for an example. Anyway, "maximum" reduces to this in Haskell:

Code:
maximum :: Ord a => [a] -> a
maximum = foldl1 max


Java doesn't really have any good list folding features, so passing indices around is the only way to properly do a recursive method. However, Java and other imperative/OO languages have something that functional languages such as Haskell don't: loops. For list processing in Java, usually simple loops work best.



Aside: How foldl1 works in Haskell. The fold functions are the most general list recursion functions. Here's how foldl1 is defined (by convention, "xs" is a list so "x:xs" is a list whose first element is x):

Code:
foldl1 :: (a -> a -> a) -> [a] -> a -- Type signature: input a function of type (a -> a -> a) and a list of a, output a, where a is any type.
foldl1 f (x:xs) = foldl f x xs

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs


As an example, here's how foldl (+) [2,3,6,1,4] expands:

Code:
foldl1 (+) [2,3,6,1,4] = foldl (+) 2 [3,6,1,4]
                       = foldl (+) (2 + 3) [6,1,4]
                       = foldl (+) ((2 + 3) + 6) [1,4]
                       = foldl (+) (((2 + 3) + 6) + 1) [4]
                       = foldl (+) ((((2 + 3) + 6) + 1) + 4) []
                       = ((((2 + 3) + 6) + 1) + 4)
                       = (((5 + 6) + 1) + 4)
                       = ((11 + 1) + 4)
                       = (12 + 4)
                       = 16
Peterssidan
I think davidv was just practicing recursion. Sometimes recursion is the easiest way to solve things, even in Java.

And just for the fun of it I give a shorter version of Fire Boar's first maximum function, because I think he made it unnecessary complicated.
Code:
maximum :: Ord a => [a] -> a
maximum [] = error "List cannot be empty!"
maximum [x] = x
maximum (x:xs) = max x (maximum xs)


but yea, ... the maximum with foldl1 is shorter (and nicer?).
davidv
For trivial tasks like finding the max and min it's much simpler to use a loop, I agree. But think about more complicated problems like the Tower of Henoi. It's much simpler and neater to write a piece of code that's using recursion for that particular problem (not to say all complex problems are better using recursion, just some).

Yes, there are languages suited to certain problems like you said Haskell for recursion or say unix tools to find the most common word in file but right now I'm learning Java and that will be the language I'll learn up until the end of this semester. Sure, I might learn some other major languages during my summer holidays but right now, Java. I'm just trying to say, even though Java isn't as suited towards recursion as other languages, it won't stop me from trying it, learning it and practicing it, using Java.

Also,

Quote:
a simple loop can be used but Im trying to practice using recursion


Quote:
I think davidv was just practicing recursion.


And of course to get better with anything you typically have to start from the basics and go upwards from there. Hence not using a loop and playing with recursive statements. Very Happy

PS: I hate Java so if I wasn't instructed to learn this language, I'd probably be learning some other language, like say... C. I still think learning Java as a first year language is stupid. OO can get quite confusing when you've only just starting programming opposed to just scripts like Python. Not to mention, Java is seriously verbose. You're spending way too much time on syntax when you should be focusing on the logic. Another reason why I reckon Python is a much better language to start off with than Java.

: > {} !!! yeeaaahhhhhh Cool
Fire Boar
Peterssidan wrote:
I think davidv was just practicing recursion. Sometimes recursion is the easiest way to solve things, even in Java.

And just for the fun of it I give a shorter version of Fire Boar's first maximum function, because I think he made it unnecessary complicated.
Code:
maximum :: Ord a => [a] -> a
maximum [] = error "List cannot be empty!"
maximum [x] = x
maximum (x:xs) = max x (maximum xs)


but yea, ... the maximum with foldl1 is shorter (and nicer?).


Yeah, it's equivalent - I just tend to prefer to have unambiguous definitions where possible rather than the fallthrough ([1] matches both [x] and x:xs, but not x:y:xs). Tom-ay-to tom-ah-to.

Also, tower of Hanoi!

Code:
hanoi :: Integer -> [(Integer, Integer)]
hanoi n = toh n 1 3 2
  where toh 0 _ _ _ = []
        toh n x y z = (toh (n-1) x z y) ++ [(x, y)] ++ (toh (n-1) z y x)


To the point, this problem is slightly different in that recursion happens twice per call, not once. Optimization is still possible, naturally.
gcca
Current Java compilers do not implement tail-call optimization, apparently because it would interfere with the Java security implementation, and would alter the behaviour of applications that introspect on the call stack for various purposes.

References:

Does the JVM prevent tail call optimizations? http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations
This Sun bug requesting tail-call support ... still open. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4726340
This page (and the referenced paper) suggest that perhaps it wouldn't be that hard after all ... http://lambda-the-ultimate.org/node/1333

There are hints that tail-call optimization might make it into Java 8.[/url]
Related topics
Java Game
Java
Add to favorites script - Java
C/C++
Whos is the FUTURE.... JAVA or .NET
JAVA queries
what do you recommend for intranet system using java N OODB
java not working properly
The many Differences between Java and JavaScript
function that calls itself
Java Arithmetic Help Please
Custom Operating System in C#, C++, or Java
What can recursive function do?
Javascript: Memoization - Real world example?
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.