Going through my tutorial book on C++ I was reading about Function Recursion. It went in-depth explaining it, giving a couple of examples that were slightly confusing. It ended up saying that while it is a tool that''s available it''s not widely used in C++ for the most part My question is this: I don''t really understand exactly how it works except that the function calls itself or another function that in turn calls the original again. The syntax in the example didn''t make a lot of sense to me. Is this something that I should attempt to find more information on, or is it used so rarely that it''s something I can ignore until I get more proficient with the basics? Thanks for any help, Anaton Flying Tigers CFSG

Recursion is a useful tool, and is the basis of a number of algorithm (though there is usually a way to express them in non-recursive form).


How it works. As you figured out, you write a function that calls itself, until some condition is fulfilled.

For example n! = 1*2*3*...n thus n!=n*(n-1)! with 0!=1
Therefore, if you know the value of (n-1)!, you can compute the value of n!. So, we are going to write the function in a way that, when asked to compute n!, it will first compute n-1 (by calling itself), and multiply the result by n

unsigned int Fact( unsigned int n ) // Note: this code is wrong !{   return n*Fact(n-1)}  

The problem with the code above is that the recursion never ends : we need to add a case where Factorial doesn't call itself. Well, for the factorial, the basic case is 0!=1, so we add a test for it.

unsigned int Fact( unsigned int n ) // Note: this code is wrong !{   if( n == 0 ) return 1;   return n*Fact(n-1)}  

Now, if I call Fact(3), what happens is as follow

Fact(3)| if( 3 == 0 ) return 1; // ignore| return 3*Fact(2)           | if( 2 == 0 ) return 1; // ignore           | return 2*Fact(1);                      | if( 1 == 0 ) return 1; // ignore                      | return 1*Fact(0);                                 | if( 0 == 0 ) return 1 // 1                      | <----- 1*1 // 1           | <----- 2*1 // 2| <----- 3*2 // 6  

Factorial is a trivial examples, but there are algorithms that are more easily expressed in recursive form than in non-recursive form.

Example : tree traversal. A tree is composed of nodes which hold a value and two pointers (left and right) to the children of the node. A (in-order) tree traversal would be (pseudo code):

Visit( Node* n ){  if ( n == NULL ) return;  Visit( n->left );  Print( n->data );  Visit( n->right);}  

Similarly, sorting routines, binary search ... all kind of Divide and Conquer algorithms (do a search on that) are easy to express (and code, even if it can be inefficient) in recursive form.

Hope it helped a bit.

[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI's STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

[edited by - Fruny on May 1, 2002 9:06:48 PM]

Ok your diagram helps make some sense of recursion. In the book (C++ in 21 days) they used a bunch of boxes with interconnecting arrows that made as much sense as mud to the uninitiated (me!).

Am I correct in understanding that recursions are useful in algorithms? What about normal programming (ie making a MOD that does NOT change the AI in a game)?




This is the Example in the book. I see where you are testing to see if n is less than 3 and if so, return 1. If not, then it goes through the else portion of the code. I guess what I don't understand here is why should n < 3? Why not 4 or 7 or any number? Also am I correct in interpreting that in the else block it's taking the input number and subtracting 2 from it then 1 from it, the adding the result together, testing it again to see if it is < 3, if not repeat, if so return 1?

Thanks for your help Fruny, I do appreciate it.

Anaton
Flying Tigers CFSG

[edited by - Anaton on May 1, 2002 11:06:03 PM]

Recursion is just one technique you have to be aware of. Mods are all just programming (just like anything else! They have nothing special). It is up to you, when designing your program, to decide whether you need recursive routines or not. There is no hard and fast rule, it is a matter of experience.

In the Fibonacci example, the special case is n<3 because the Fibonacci sequence is defined by Fib(1)=Fib(2)=1 and Fib(n)=Fib(n-1)+Fib(n-2) for n>=3.

[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Thanks again Fruny. I have a better idea about it now but I think for the immediate I won''t use it unless it''s the only solution to my problem at hand.