aspose file tools*
The moose likes Performance and the fly likes Recursion Efficiency Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Recursion Efficiency" Watch "Recursion Efficiency" New topic
Author

Recursion Efficiency

Vlad Ivanov
Greenhorn

Joined: Mar 02, 2010
Posts: 7
To whomever is kind enough to help:
I was debating if I should post this in the beginners forum or here, but I opted for here. So just be aware it's an efficiency/perfomance question at a basic level... Anyway, I just finished coding an assignment for my intro to Java class where we have to make a recursive method to solve an "n choose k" problem. Here's what I produced:



My question is this: is there a more efficient way to do this? I think I have O(2^n), which is less than ideal. Any suggestions?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
Drac: correct, this isn't the most efficient implementation possible. But it may well be the best implementation for your assignment - depending on its parameters, and how advanced you want to get.

Are you required to use recursion? An iterative method may be faster. Consider starting from n = 1 and increasing from there, filling in each row in order.

Or if you need to use recursion - can you create a data structure to save previously-computed values? That way you can avoid re-computing the same thing unnecessarily. You can look into "memoization" for more information.

Tim Holloway
Saloon Keeper

Joined: Jun 25, 2001
Posts: 16011
    
  19

Recursion versus iteration is a classic example of an optimization that you should only do after making measurements.

The IBM System/360-370 mainframes had no recursive hardware capabilities whatsoever. So on that platform, use of recursion required not only full function call overhead, but a considerable amount of prologue/epilogue code to simulate a stack architecture.

Virtually all microprocessors have hardware recursion support, from the 8-bit Intel 8080 and 6502 (Commodore/Apple) CPUs on up to the present day. A recursive call requires minimal code.

Number of instructions isn't everything, since the underlying firmware and circuitry may have a greater or lesser impact on how fast those instructions run, but it does tend to be indicative.

On top of that, one of the oldest compiler optimizations in the book is the detection of Tail Recursions and the process of unrolling them into iterative loops.

So don't "know". Measure.

Incidentally, I believe the current zSeries IBM mainframes do have recursive capabilities. Then again, half the C standard library is encoded into single machine instructions on that platform, including many of the string functions and even sort. These are quite definitely not RISC machines.


Customer surveys are for companies who didn't pay proper attention to begin with.
Vlad Ivanov
Greenhorn

Joined: Mar 02, 2010
Posts: 7
The assignment does call for recursion, but past that we have free reign. Our professor mentioned that the problem could be solved with a linear big O, though I cannot figure out how...
Tim Holloway
Saloon Keeper

Joined: Jun 25, 2001
Posts: 16011
    
  19

Actually, the term is "free rein". It has to do with horsemanship and means basically letting the horses run without control. But considering the context, a lot of people make that mistake, especially since the horses "reign" in that case. And there are worse mistakes one can make. My spellchecker just notified me that I've been mis-pronouncing and therefore mis-spelling a fairly common word for years.

Mathematical efficiency is theoretical efficiency. As I've noted, in the real world, other factors may interfere.

For your specific problem, I have a suspicion that there's a way to collapse it. Kind of like the way you can collapse adding the numbers in the series 1..n into a single add-plus-divide operation. But I haven't picked it apart to be sure.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

"Vladimir", please check your private messages regarding an important administrative matter.

Thank you.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
Using memoization here would be O(N^2) I believe. Better than O(2^N) certainly, but it would also use O(N^2) memory.

Ah, looks like there is a simple O(N) technique. A substantial hint can be found in Identities involving binomial coefficients.



Vlad Ivanov
Greenhorn

Joined: Mar 02, 2010
Posts: 7
Thanks for the link Mike! That may give me the nudge I need to raise my efficiency!
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4646
    
    5

Владимир Иванов wrote:efficiency!

As a general rule, all rules have exceptions.

Recursion is rarely an efficient technique in general. Its elegant, and great for teaching new programmers how to approach a problem from a different view point.

Nearly all production applications of serious size are converted from recursion to a simpler implementation, for suitably large values of N
Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 60975
    
  65

"Владимир Иванов", please check your private messages for an important administrative matter.

[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion Efficiency