Various types of recursion

[Petr Schreiber]

Learning for exam,

I had to create example on different kinds of recursion to really see they behave as described.
Could serve as some kind of test whether recursion works ok:


' -- Various types of recursion

Uses "Console"

PrintL "Ackermann function"
PrintL ack(3, 4)
PrintL

PrintL "Fibonacci"
PrintL fib(5)
PrintL

PrintL "Factorial"
PrintL fact(5)
PrintL

PrintL "Greatest common divisor"
PrintL gcd(513, 27)
PrintL

WaitKey

' -- Nested recursion: Recursive call to function contains recursive call to itself in the arguments
' -- Ackermann function
Function ack(x As Number, y As Number) As Number
If x = 0 Then Return y+1
If y = 0 Then Return ack(x-1, 1)
Return ack(x-1, ack(x, y-1))
End Function

' -- Cascade (tree) recursion: Multiple occuriences of recursive call appear in one expression, but without any nesting
' -- Fibonacci
Function fib(n As Number) As Number
If n <= 1 Then Return 1
Return fib(n-2)+fib(n-1)
End Function

' -- Linear recursion: Each alternative of definition contains 1 recursive call at max.
' -- Factorial
Function fact(n As Number) As Number
If n = 0 Then Return 1
Return n * fact(n-1)
End Function

' -- End recursion: Special case of linear recursion, where recursive call is the last operation of specific alternative of definition
' -- Greatest common divisor
Function gcd(x As Number, y As Number) As Number
If x = y Then Return x
If x > y Then Return gcd(x-y, y)
Return gcd(x, y-x)
End Function


You can take a walk through the code using debugger, to watch it call itself.


Petr

[danbaron]

[font=courier new]How about, composition of recursive functions?

:oops:
Dan :x :P


Uses "console"

'This script runs OK.
'But, it is easy to cause "stack" overflow in the function gcd().
'For me, gcd(2585, 1), results in Windows saying the program has stopped working.

Function TBMain()
Console_WriteLine(gcd(fib(fact(ack(1, 1))), 13))
Console_WriteLine
Console_WriteLine("Done. Press a key.")
WaitKey
End Function


' -- Nested recursion: Recursive call to function contains recursive call to itself in the arguments
' -- Ackermann function
Function ack(x As Number, y As Number) As Number
If x = 0 Then Return y+1
If y = 0 Then Return ack(x-1, 1)
Return ack(x-1, ack(x, y-1))
End Function

' -- Cascade (tree) recursion: Multiple occurrences of recursive call appear in one expression, but without any nesting
' -- Fibonacci
Function fib(n As Number) As Number
If n <= 1 Then Return 1
Return fib(n-2)+fib(n-1)
End Function

' -- Linear recursion: Each alternative of definition contains 1 recursive call at max.
' -- Factorial
Function fact(n As Number) As Number
If n = 0 Then Return 1
Return n * fact(n-1)
End Function

' -- End recursion: Special case of linear recursion, where recursive call is the last operation of specific alternative of definition
' -- Greatest common divisor
Function gcd(x As Number, y As Number) As Number
If x = y Then Return x
If x > y Then Return gcd(x-y, y)
Return gcd(x, y-x)
End Function

[Petr Schreiber]

That is recursion festival what you posted here :)

I do not use recursion very much in my programs, as it is usually slower than other methods.
I was learning for LISP exam, but as the debugger in LispWorks did not became my friend, I coded it in TB to see what it does.


Petr

[Charles Pegge]

I found it is almost impossible to do without recursion in certain situations: when compiling BASIC statements expressions may occur in the arguments of function calls. These expressions may contain further functions ...

The only practical way to resolve these nested structures which involve quite complicated parsing - is to use recursion. But it is not my first choice of strategy and it can be avoided most of the time, using iteration and array indexing instead.

Charles

[Petr Schreiber]

You are right,

in some cases you simply need to use recursion.
I just wanted to say it is not the best solution in some situations, like the calculation of fibbonacci sequence.


Petr

[danbaron]

[font=courier new]I looked, and you can define the Ackermann Function non-recursively, using Knuth's up-arrow
notation.

^ (m-2)
A(m,n) = 2 | (n+3) - 3

Dan

http://en.wikipedia.org/wiki/Ackermann_function

http://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

http://www.daviddarling.info/encyclopedia/A/Ackermann_function.html

[danbaron]

[font=courier new]I posted this last year at Ionic Wind.
But, since it demonstrates recursion, I'll post it here.

:oops:
Dan :x :P

We're Proud to Announce to One and All
(S.Howard, D.Baron)

We're proud to announce,
to one and all.
We've been inducted into,
the Poets' Hall.

The committee chose the best poem,
of all time.
And we modestly acknowledge,
they selected this rhyme.

We received two blue ribbon awards,
and two bronze statues too.
That show Shakespeare astride,
his famous pet kangaroo.

They made a beautiful plaque,
with our names engraved.
And through the entire event,
we were wonderfully behaved.

The plaque will hang for eternity,
in the Poets' Hall.
Reading as follows,
on the Honors' Wall.
"The best poem ever either small or tall,
'We're Proud to Announce to One and All'".

They rolled out the red carpet,
and had a parade.
They presented us each with,
ten pretty young maids.

They announced on loudspeakers,
"Hail the kings of the poem !".
And when the parade finished,
they graciously took us both hoem ...