What are the main problems with using recursion? Would memory constraints be one of the problems?

Main problems are:
- Memory
- Time

An iterative method will be the same thing faster and with less memory usually.

But don''t forget this:

FIRST, make it works,
THEN optimize it.

There are several techniques (it can be automated) for translate recursive methods to iterative. So never worry about one approach or another. ALWAYS use natural way. You will have time to optimize later (if REALLY needs). Focus on make it works.

it would be best to take a class or pick up a good book on algorithms (I have to do this myself) so that you can compute the cost of a certain algorithm compared to others (among other cool things). This will greatly help you decide whether an iterative or recursive process is better

_________________________________________________________________

Drew Sikora
A.K.A. Gaiiden

ICQ #: 70449988
AOLIM: DarkPylat

Blade Edge Software
Staff Member, GDNet
Public Relations, Game Institute

3-time Contributing author, Game Design Methods , Charles River Media (coming April/May 2002)
Online column - Design Corner at Pixelate

NJ IGDA Chapter - NJ developers unite!! [Chapter Home | Chapter Forum]

sometimes you do unnecessary calculations

a classic example is how to calculate the fibonacci sequence

  int fib(int n) {    return (n == 0 || n == 1) ? 0 : fib(n-1) + fib(n-2);}  

(the obove is in java btw)

here you are clearly calculating the same stuff more than once. solution, use a non-recursive algorithm or check what you have already calculated.

btw, i suck at recursion so i might be wrong

maybe it can be optomised - it just makes the best recursive example. *shrugs*

To understand recursion, you must first start with recursion.

Table look-up would optimize your fibonacci computing greatly.(a.k.a. dynamic programming in Algorithm-speak)

Gaiiden is definitely right. You ought to pick up a book on algorithms or take a class. Learning about this stuff is essential. I took an algorithms class last semester at school, and while it was certainly one of the most difficult courses I've ever taken, it was also the most rewarding and useful class I've taken thus far. The things you learn are applicable everywhere and I've used them on a regular basis to improve the performance of my code :-)

Just wanted to add my two cents :-)

Edited by - xelius on February 20, 2002 8:47:07 PM

The fibonacci sequence is a very bad example for recursion, and here''s why:

  const double sqrt5 = sqrt(5);double fib(int n) {    return floor(pow((sqrt5+1.0)/2.0,n)/sqrt5+0.5);}  

Calculating factorials recursively would be a better example...

The Fibonacci sequence is recursively *defined*. Just because there is a *direct computational* method for F(n) using the Golden Ratio doesn''t mean it''s a bad example of recursion. Numerous algorithms have recursive definitions but are nearly always implemented with an iterative or dynamic-programming method. As for computing factorials resurvely, look for the Gamma function in an intermediate or advanced Calculus or Real Analysis book. You could approximate the function directly, but would that make it a bad example of recursion? No.

It''s interesting to note that recursion is essential to C++ template metaprogramming techniques. The template expansion mechanism of C++ represents a Turing complete machine and, as such, there is an awful lot you can achieve at compile time. For example, to continue the Fibonacci theme, this is how you would compute Fibonacci numbers at compile time:

  template<int n>struct Fibonacci{	enum { RET = Fibonacci<n-1>::RET + Fibonacci<n-2>::RET };};template<>struct Fibonacci<1>{	enum { RET = 1 };};template<>struct Fibonacci<0>{	enum { RET = 0 };};  

On template instantiation, the general Fibonacci template is recursively expanded by the compiler until the recursion is terminated by one of the 2 specialisations. The question of recursion here no longer raises issues of performance or memory consumption. Or, rather, those concerns do not affect the runtime performance of the program, as you have precalculated the value as a constant.

Obviously, this example is fairly trivial as you could simply hardcode the Fibonacci constant into the program, but it should illustrate that recursion is the only way to make this sort of calculation at compile time.

--
The placement of a donkey''s eyes in its head enables it to see all four feet at all times.