• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursion Efficiency

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

 
Saloon Keeper
Posts: 27763
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Vlad Ivanov
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 27763
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"Vladimir", please check your private messages regarding an important administrative matter.

Thank you.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the link Mike! That may give me the nudge I need to raise my efficiency!
 
Rancher
Posts: 4803
7
Mac OS X VI Editor Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Владимир Иванов 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
 
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"Владимир Иванов", please check your private messages for an important administrative matter.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic