DM42: Recursive Fibonacci by Marko Draisma
The programs on today's entry is provided from Marko Draisma and they are provided with permission and a request. Gratitude to Marko.
DM42 (and Free42/Plus42) Program: FIBO (Marko Draisma)
This recursive program generates the nth Fibonacci number. FIBO is a recursive program because it calls itself in the program steps.
LBL "FIBO"
LSTO "N"
X>0?
GTO 00
0
RTN
LBL 00
1
RCL "N"
X>Y?
GTO 01
1
RTN
LBL 01
RCL "N"
1
-
XEQ "FIBO"
LSTO "M"
RCL "N"
2
-
XEQ "FIBO"
RCL "M"
+
END
1st Fibonacci number: 1 FIBO returns 1
2nd Fibonacci number: 2 FIBO returns 1
3rd Fibonacci number: 3 FIBO returns 2
4th Fibonacci number: 4 FIBO returns 3
5th Fibonacci number: 5 FIBO returns 5
6th Fibonacci number: 6 FIBO returns 8
7th Fibonacci number: 7 FIBO returns 13
The LSTO Command
This is the local store command. Local variables are created only for the purpose of the program and are deleted when the program hits either a return command (RTN) or an end command (END).
Variables created by the LSTO command are named variables. We cannot create local variables to numeric registers. There is no storage arithmetic with LSTO.
LSTO is available for the Swiss Micros DM42, Free42, and the Plus42.
Execution Time of FIBO
The execution time of FIBO depends on how large the entry n. Calculating the 50th Fibonacci number, 12,586,269,025, takes over 12 minutes. Marko provides a fast tail recursion version, as presented next.
DM42 (and Free42/Plus42) Program: FIBO2 (Marko Draisma)
00 { 80-Byte Prgm }
01▸LBL "FIBO2"
02 FS? 01
03 GTO 01
04 LSTO "N"
05 1
06 LSTO "B"
07 0
08 LSTO "A"
09 SF 01
10 XEQ "FIBO2"
11 RTN
12▸LBL 01
13 RCL "N"
14 X≠0?
15 GTO 02
16 CF 01
17 RCL "A"
18 RTN
19▸LBL 02
20 RCL "A"
21 ENTER
22 RCL+ "B"
23 LSTO "A"
24 X<>Y
25 LSTO "B"
26 RCL "N"
27 1
28 -
29 LSTO "N"
30 XEQ "FIBO2"
31 END
Getting the 50th Fibonacci number with FIBO2 is snap.
Thanks once again to Marko Draisma.
See you next time,
Eddie
All original content copyright, © 2011-2022. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.
