 ### Author Topic: Very simple & small recursion example and other things...  (Read 1170 times)

• Guest ##### Very simple & small recursion example and other things...
« on: 2010-May-24 »
...with the new type system :

Code: GLBasic [Select]
TYPE Ta
FUNCTION recurse%:value%
IF value%<=1 THEN RETURN 1

RETURN value%*recurse(value%-1)
ENDFUNCTION
ENDTYPE

LOCAL t AS Ta

DEBUG "Final value : "+t.recurse(5)+"\n"
END

Recursion works fine.

Now, if you expand this to calculate how long it takes against a regular function :

Code: GLBasic [Select]
TYPE Ta
FUNCTION recurse%:value%
IF value%<=1 THEN RETURN 1

RETURN value%*recurse(value%-1)
ENDFUNCTION
ENDTYPE

LOCAL t AS Ta
LOCAL r,b

r=GETTIMERALL()
DEBUG "Final value : "+t.recurse(6)+"\n"
b=GETTIMERALL()-r
DEBUG "Time taken : "+b+"\n"

r=GETTIMERALL()
DEBUG "Final value : "+recurse2(6)+"\n"
b=GETTIMERALL()-r
DEBUG "Time taken : "+b+"\n"

END

FUNCTION recurse2%:value%
IF value%<=1 THEN RETURN 1

RETURN value%*recurse2(value%-1)
ENDFUNCTION

I get :

Final value : 720
Time taken : 3.857474154
Final value : 720
Time taken : 3.429867122

Increase the recursive value slightly :

Final value : 40320
Time taken : 3.979530566
Final value : 40320
Time taken : 4.035234164

And finally once more :

Final value : 479001600
Time taken : 3.064517054
Final value : 479001600
Time taken : 3.275043887

The first value is using a function in a TYPE, whilst the second isn't...

What is interesting to note is that with an iteration and a substantial initial value, using a function in TYPE is quicker than a standard function.

Which leads me to this :

Code: GLBasic [Select]
TYPE Ta
FUNCTION recurse%:value%
LOCAL a,b
LOCAL x%

a=GETTIMERALL()
FOR x%=1 TO 1000
NEXT
b=GETTIMERALL()-a

DEBUG "Result : "+b+"\n"

ENDFUNCTION
ENDTYPE

LOCAL t AS Ta
LOCAL r,b

t.recurse(12)
recurse2(12)
END

FUNCTION recurse2%:value%
LOCAL a,b
LOCAL x%

a=GETTIMERALL()
FOR x%=1 TO 1000
NEXT
b=GETTIMERALL()-a

DEBUG "Result : "+b+"\n"
ENDFUNCTION

Now, you may think that the results should be same, but they are not, with the TYPE function performing somewhat slower than the standard function :

Result : 2.293677535e-002
Result : 2.211760543e-002

This is to be somewhat expected as classes add a slight decrease to a functions performance.  However, the good news is that, like the first example, the bigger the loop, the function in the type produces a quicker result than a standard function.

Whilst the times are usually in the 100's of milliseconds, it shows that if you do as much work in a function in a type  as possible, its execution speed should be better than a standard function.