hi, i need a recursion program. i am very poor in programmin so i want to learn from the examples.
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. 
void RecursiveFunction(unsigned x, unsigned max)

{

if (x >= max)

{

return;

}


// Do something here


RecursiveFunction(x+1, max);

}


int main()

{

RecursiveFunction(0, 20);

}

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: 
int Ack(int n, int m) {

if (n == 0) return m+1;

if (m == 0) return Ack(n1, 1);

return Ack(n1, Ack(n, m1));

}

a terrible little monster that is ;)
kind regards,
Jos
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: 
fac(int x)

{

if( x is 0 or 1 ) return 1

else return x * fac( x  1 )

}

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: 
endrecursive_fac(int x, int y = 1)

{

if( x is 0 or 1 ) return y

else return endrecursive_fac( x  1 , y * x )

}

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
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.
thanks in advance,
Gsi.
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.
thanks in advance,
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
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.
thanks in advance,
Gsi.
According to my quick implementation Ack(3, 3) == 61 != 27. Have a look here.
kind regards,
Jos
Thanks guys for the info.
Gsi.
Post your reply Sign in to post your reply or Sign up for a free account.
Similar topics
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
          