Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Recursion Efficiency

Greenhorn
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
Posts: 3090
14
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
Posts: 18325
56
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.

Greenhorn
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
Posts: 18325
56
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
Posts: 21443
33

Thank you.

Mike Simmons
Ranch Hand
Posts: 3090
14
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.

Greenhorn
Posts: 7
Thanks for the link Mike! That may give me the nudge I need to raise my efficiency!

Pat Farrell
Rancher
Posts: 4678
7
Владимир Иванов 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
Posts: 65278
95