Small Basic: Fibonacci Function

  • Article

We'll discuss two possible approaches to make the Fibonacci function:

First approach

This section makes use of Simulating Parameters and Simulating Local Variables. By Kenny Kasajian

http://kasajian.com

' Call Fib( 13 )
Stack.PushValue( "p", 13 )
Fib()
TextWindow.WriteLine( Stack.PopValue( "p" ) )

Sub Fib ' n
Fib_Locals = Fib_Locals + 1

'Set up params:
Array.SetValue( Text.Append( "Fib", Fib_Locals), "n", Stack.PopValue( "p" ) )

If Array.GetValue( Text.Append( "Fib", Fib_Locals), "n") < 2 Then
' Return n
Stack.PushValue( "p", Array.GetValue( Text.Append( "Fib", Fib_Locals), "n") )
Goto Fib_Exit
Else
'n1 = Fib( n - 1 )
Stack.PushValue( "p", Array.GetValue( Text.Append( "Fib", Fib_Locals), "n") - 1 )
Fib()
Array.SetValue( Text.Append( "Fib", Fib_Locals), "n1", Stack.PopValue( "p" ) )

'n2 = Fib( n - 2 )
Stack.PushValue( "p", Array.GetValue( Text.Append( "Fib", Fib_Locals), "n") - 2 )
Fib()
Array.SetValue( Text.Append( "Fib", Fib_Locals), "n2", Stack.PopValue( "p" ) )

'Return n1 + n2
Stack.PushValue( "p", Array.GetValue( Text.Append( "Fib", Fib_Locals), "n1") + Array.GetValue( Text.Append( "Fib", Fib_Locals), "n2") )
Goto Fib_Exit
EndIf

Fib_Exit:
Fib_Locals = Fib_Locals - 1
EndSub

Second approach (program XSZ737)

By Alexandre

http://linux.ime.usp.br/~alemart , alemartfATgmailDOTcom

' The goal of this program is to learn how to create
' recursive functions using Small Basic.
' We don't care about Iterative Fibonacci here.


'
' Fib(x)
' Returns the x-th Fibonacci Number using a recursive approach
'
' Fib(0) = 1
' Fib(1) = 1
' Fib(x) = Fib(x-1) + Fib(x-2), for all x >= 2
'
Sub Fib
' retrieving the parameters of this function
parameter = Stack.PopValue("parameter")

' declaring local variables
local["n"] = parameter
local["n1"] = 0
local["n2"] = 0

' calculating Fib(x) ...
If local["n"] = 0 Or local["n"] = 1 Then
'
' BASE
'

' return 1
Stack.PushValue("return", 1)
ElseIf local["n"] >= 2 Then
'
' INDUCTION
'

' n1 = Fib(n-1)
Stack.PushValue("parameter", local["n"]-1) ' setting the parameters
Stack.PushValue("local", local) ' preserving local variables
Fib() ' recursive call
local = Stack.PopValue("local") ' restoring local variables
local["n1"] = Stack.PopValue("return") ' getting the return value

' n2 = Fib(n-2)
Stack.PushValue("parameter", local["n"]-2)
Stack.PushValue("local", local)
Fib()
local = Stack.PopValue("local")
local["n2"] = Stack.PopValue("return")

' return n1 + n2
Stack.PushValue("return", local["n1"] + local["n2"])
Else
' error: return 0
Stack.PushValue("return", 0)
EndIf
EndSub


TextWindow.WriteLine("===========================")
TextWindow.WriteLine("Recursive Fibonacci Numbers")
TextWindow.WriteLine("===========================")
While x >= 0
' Input
TextWindow.Write("Please enter a non-negative number: ")
x = TextWindow.ReadNumber()
If(x >= 0) Then
' Processing: fib_x = Fib(x)
Stack.PushValue("parameter", x)
Fib()
fib_x = Stack.PopValue("return")

' Output
TextWindow.WriteLine("Fib(" + x + ") = " + fib_x)
EndIf
EndWhile
TextWindow.WriteLine("bye!")

Reference
This content originally came from the Small Basic Wiki.