469,581 Members | 1,916 Online

# recursion 1
hi, i need a recursion program. i am very poor in programmin so i want to learn from the examples.
Apr 21 '08 #1
7 1177 Banfa
9,064 Expert Mod 8TB
Recursion is just a function that calls itself either directly or indirectly. There must be a condition that stops the recursion otherwise you end up with an infinite recursion which will ultimately destroy the program stack and cause a crash.

I have seen it written that any formula that can be implemented as a for loop can be implemented as a recursive function and vice versa but I have not put any effort into trying to verify this.

Expand|Select|Wrap|Line Numbers
1. void RecursiveFunction(unsigned x, unsigned max)
2. {
3.     if (x >= max)
4.     {
5.         return;
6.     }
7.
8.     // Do something here
9.
10.     RecursiveFunction(x+1, max);
11. }
12.
13. int main()
14. {
15.     RecursiveFunction(0, 20);
16. }
17.
Apr 21 '08 #2
JosAH
11,448 Expert 8TB
I have seen it written that any formula that can be implemented as a for loop can be implemented as a recursive function and vice versa but I have not put any effort into trying to verify this.
That's only true for the 'primitive recursive functions'; for the 'total recursive functions
or partial recursive functions' you need an explicit stack. e.g. try to implement
the Ackerman function without using a stack:

Expand|Select|Wrap|Line Numbers
1. int Ack(int n, int m) {
2.    if (n == 0) return m+1;
3.    if (m == 0) return Ack(n-1, 1);
4.    return Ack(n-1, Ack(n, m-1));
5. }
6.
a terrible little monster that is ;-)

kind regards,

Jos
Apr 21 '08 #3
Nepomuk
3,112 Expert 2GB
A very common example for recursion is the calculation of the factorial of a number.
In case you don't know, the factorial of a positive integer n is:
n! = n * (n - 1) * ... * 2 * 1
and 0! = 1 per definition.

In pseudo code, that is:
Expand|Select|Wrap|Line Numbers
1. fac(int x)
2. {
3.         if( x is 0 or 1 ) return 1
4.         else return x * fac( x - 1 )
5. }
6.
A very nice form of recursion (at least, if you want to transform your method to a loop or vice verca) is endrecursive recursion. Here's an example:
Expand|Select|Wrap|Line Numbers
1. endrecursive_fac(int x, int y = 1)
2. {
3.         if( x is 0 or 1 ) return y
4.         else return endrecursive_fac( x - 1 ,  y * x )
5. }
6.
As you may see, the last thing that is done in the method is the recursive call. (While in the first example, the last thing done was the multiplikation x * fac( x - 1 ).)
As Jos pointed out, you can't do every translation between loops and recursions and in many cases loops are more difficult to write, but much more effective in terms of time it takes to calculate, memory used etc. But recursion often looks much more elegant. ^^

Hope you understand recursion a little better now.

Greetings,
Nepomuk
Apr 21 '08 #4
gsi
51 Hi Jos,
This question is a bit irrelevant to the OP's post but just curious, the Ackermann function that you have posted is supposed to return the result when m is towered n times exponentially ....(i.e ) for Ack(3,3) the result should be 3 raised to 3 raised to 3 ? . Please advice.

Gsi.
Apr 22 '08 #5
Nepomuk
3,112 Expert 2GB
Hi Jos,
This question is a bit irrelevant to the OP's post but just curious, the Ackermann function that you have posted is supposed to return the result when m is towered n times exponentially ....(i.e ) for Ack(3,3) the result should be 3 raised to 3 raised to 3 ? . Please advice.

Gsi.
Actually, the Ackermann function is quite an evil thing, when entering even small values. On Wikipeida you can find an article with a table of some values - according to them Ack(3,3) is 61. Here's a little calculation:
Ack(3,3)
=Ack(2,Ack(3,2))
=Ack(2,Ack(2,Ack(3,1)))
=Ack(2,Ack(2,Ack(2,Ack(3,0))))
=Ack(2,Ack(2,Ack(2,Ack(2,1))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(2,0)))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(1,1)))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(1,Ack(1,0))))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(1,Ack(0,1))))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(1,2)))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(0,Ack(1,1))))))
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(0,Ack(0,Ack(1,0)))))) )
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(0,Ack(0,Ack(0,1)))))) )
=Ack(2,Ack(2,Ack(2,Ack(1,Ack(0,Ack(0,2))))))
=...
As you see, it gets pretty extreme - much more extreme than just exponential growth! There are some more examples on that Wikipedia page.

Greetings,
Nepomuk
Apr 22 '08 #6
JosAH
11,448 Expert 8TB
Hi Jos,
This question is a bit irrelevant to the OP's post but just curious, the Ackermann function that you have posted is supposed to return the result when m is towered n times exponentially ....(i.e ) for Ack(3,3) the result should be 3 raised to 3 raised to 3 ? . Please advice.

Gsi.
According to my quick implementation Ack(3, 3) == 61 != 27. Have a look here.

kind regards,

Jos
Apr 22 '08 #7
gsi
51 Thanks guys for the info.

Gsi.
Apr 22 '08 #8

 5 posts views Thread by Peri | last post: by 12 posts views Thread by da Vinci | last post: by 43 posts views Thread by Lorenzo Villari | last post: by 2 posts views Thread by Csaba Gabor | last post: by 75 posts views Thread by Sathyaish | last post: by 19 posts views Thread by Kay Schluehr | last post: by 18 posts views Thread by MTD | last post: by 13 posts views Thread by robert | last post: by 20 posts views Thread by athar.mirchi | last post: by 35 posts views Thread by Muzammil | last post: by reply views Thread by suresh191 | last post: by reply views Thread by Trystan | last post: by reply views Thread by Marketing QM | last post: by 11 posts views Thread by MGadAllah | last post: by reply views Thread by PitrL | last post: by 1 post views Thread by tbutler | last post: by 1 post views Thread by Samuh | last post: by reply views Thread by hefaz | last post: by reply views Thread by billypeterson | last post: by