Vlad Ivanov

Greenhorn

Posts: 7

posted 7 years ago

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?

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: 3090

14

posted 7 years ago

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.

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.

posted 7 years ago

Recursion

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".

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

*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.An IDE is no substitute for an Intelligent Developer.

Vlad Ivanov

Greenhorn

Posts: 7

posted 7 years ago

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.

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.

An IDE is no substitute for an Intelligent Developer.

posted 7 years ago

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

Thank you.

Thank you.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 7 years ago

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

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

posted 7 years ago

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

Владимир Иванов 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