recursion

[kandola47]

hi, i need a recursion program. i am very poor in programmin so i want to learn from the examples.

[Banfa]

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.

[code=c]
void RecursiveFuncti on(unsigned x, unsigned max)
{
if (x >= max)
{
return;
}

// Do something here

RecursiveFuncti on(x+1, max);
}

int main()
{
RecursiveFuncti on(0, 20);
}
[/code]

[JosAH]

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:

[code=c]
int Ack(int n, int m) {
if (n == 0) return m+1;
if (m == 0) return Ack(n-1, 1);
return Ack(n-1, Ack(n, m-1));
}
[/code]

a terrible little monster that is ;-)

kind regards,

Jos

[Nepomuk]

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

[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.

[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.

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,Ac k(3,1)))
=Ack(2,Ack(2,Ac k(2,Ack(3,0))))
=Ack(2,Ack(2,Ac k(2,Ack(2,1))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(2 ,0)))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(1 ,1)))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(1 ,Ack(1,0))))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(1 ,Ack(0,1))))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(1 ,2)))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(0 ,Ack(1,1))))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(0 ,Ack(0,Ack(1,0) ))))))
=Ack(2,Ack(2,Ac k(2,Ack(1,Ack(0 ,Ack(0,Ack(0,1) ))))))
=Ack(2,Ack(2,Ac k(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

[JosAH]

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

[gsi]

Thanks guys for the info.

Gsi.