hi, i need a recursion program. i am very poor in programmin so i want to learn from the examples.
7 1345 Banfa 9,065
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.
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Peri 
last post by:
I'm trying to create Python parser/interpreter using ANTLR.
Reading grammar from language refference I found:
or_expr::= xor_expr  or_expr "" xor_expr
For me it looks like infinite recursion....

by: da Vinci 
last post by:
Greetings.
I want to get everyone's opinion on the use of recursion.
We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted...

by: Lorenzo Villari 
last post by:
I've tried to transform this into a not recursive version but without
luck...
#include <stdio.h>
void countdown(int p)
{
int x;

by: Csaba Gabor 
last post by:
I suppose spring fever has hit at alt.math.undergrad since I didn't get
any rise from
them when I posted this a week ago, so I am reposting this to some of
my favorite
programming groups:
I'm...

by: Sathyaish 
last post by:
Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
I tried one example, and am in the process of trying out more examples,
increasing their...

by: Kay Schluehr 
last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691

by: MTD 
last post by:
Hello all,
I've been messing about for fun creating a trial division factorizing
function and I'm naturally interested in optimising it as much as
possible.
I've been told that iteration in...

by: robert 
last post by:
My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception.
What...

by: athar.mirchi 
last post by:
..plz define it.

by: Muzammil 
last post by:
int harmonic(int n) {
if (n=1) {
return 1;
}
else {
return harmonic(n1)+1/n;
}
}
can any help me ??

by: Kemmylinns12 
last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and efficiency. While initially associated with cryptocurrencies...

by: antdb 
last post by:
Ⅰ. Advantage of AntDB: hyperconvergence + streaming processing engine
In the overall architecture, a new "hyperconvergence" concept was proposed, which integrated multiple engines and...

by: Matthew3360 
last post by:
Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function.
Here is my code.
header("Location:".$urlback);
Is this the right layout the...

by: Matthew3360 
last post by:
Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it so the python app could use a http request to get...

by: AndyPSV 
last post by:
HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and...

by: Carina712 
last post by:
Setting background colors for Excel documents can help to improve the visual appeal of the document and make it easier to read and understand. Background colors can be used to highlight important...

by: BLUEPANDA 
last post by:
At BluePanda Dev, we're passionate about building highquality software and sharing our knowledge with the community. That's why we've created a SaaS starter kit that's not only easy to use but also...

by: Rahul1995seven 
last post by:
Introduction:
In the realm of programming languages, Python has emerged as a powerhouse. With its simplicity, versatility, and robustness, Python has gained popularity among beginners and experts...

by: Ricardo de Mila 
last post by:
Dear people, good afternoon...
I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control.
Than I need to discover what...
 