This week's book giveaway is in the Design forum.
We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!
See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion Efficiency

 
Vlad Ivanov
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • 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?
 
Mike Simmons
Ranch Hand
Posts: 3039
10
  • Mark post as helpful
  • send pies
  • 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.

 
Tim Holloway
Saloon Keeper
Pie
Posts: 18094
48
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • 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
  • 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
Pie
Posts: 18094
48
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • 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.
 
Paul Clapham
Sheriff
Pie
Posts: 20958
31
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Vladimir", please check your private messages regarding an important administrative matter.

Thank you.
 
Mike Simmons
Ranch Hand
Posts: 3039
10
  • Mark post as helpful
  • send pies
  • 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
  • Quote
  • Report post to moderator
Thanks for the link Mike! That may give me the nudge I need to raise my efficiency!
 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • 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
 
Bear Bibeault
Author and ninkuma
Marshal
Pie
Posts: 64700
86
IntelliJ IDE Java jQuery Mac Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Владимир Иванов", please check your private messages for an important administrative matter.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic