'Implementing the recursive method for Factorial and Fibonacci
'
'Iterate is Human, Recursion is Divine
'
'This example helps to understand recursion and management
'of parameters and return a result in the calling of functions
'and in general the working mechanism of the memory heap
'
'In General
'Every time we have to call a function which can overwrite our
'local variable, we have to push them into a stack. If the function
'needs parameters, after the local variable, we push into the stack
'the parameters. After a function call, we have to remove all the
'element from the Stack. If the function return a value we need a
'pop to get that value, and then a pop for each local variable we saved.
'In the called function we have to pop the parameters and finally
'push the resulting value.
'
'In this example n is a local variabile into Main(), Fact() and Fib()
'subroutines but I never lost the local value. In addition the subroutine
'Fact() and Fib() accept a parameter and it returns a value
'
'One final note ... I hate "Goto"... I love the structured programming... Small Basic is very cute
'Main - User Interface
Sub Main 'Main Program
n = 1 'An initial value for n
sel = 1 'An initial value for sel
While(sel<>0)
TextWindow.WriteLine("0) Exit") 'A menu
TextWindow.WriteLine("1) Factorial")
TextWindow.WriteLine("2) Fobonacci")
TextWindow.Write("Make your choice: ")
sel=TextWindow.ReadNumber() 'What would you like to do?
If(sel>0 And sel<3)Then 'When I have a good choice
TextWindow.Write("Insert a number: ")
n=TextWindow.ReadNumber() 'Which number?
EndIf
Stack.PushValue("Heap",n) 'Save local variable n
Stack.PushValue("Heap",n) 'Set the paramenter for the Fact() or Fib() function
If(sel=1)Then 'Calculating factorial
Fact()
ElseIf(sel=2)Then 'Calculating Fibonacci
Fib() 'Even if no function will be executed, push e pop are right
EndIf 'and the Stack will be cleared!
ret = Stack.PopValue("Heap")'Get the returned value
n = Stack.PopValue("Heap")'Restore local variable
TextWindow.WriteLine("")
If(sel=0)Then
TextWindow.WriteLine("Exiting...")
ElseIf(sel=1)Then 'Factorial result
TextWindow.WriteLine(n + "! = " + ret)
ElseIf(sel=2)Then 'Fibonacci result
TextWindow.WriteLine("Fib(" + n + ")=" + ret)
Else 'Wrong Choice
TextWindow.WriteLine("Wrong choice!")
EndIf
TextWindow.WriteLine("")
TextWindow.WriteLine("")
EndWhile
EndSub
'Fact - Factorial calculating
Sub Fact
n=Stack.PopValue("Heap") 'Get Parameter
If(n<0)Then 'The Parameter must be positive
TextWindow.WriteLine("There is an error, the number is negative!")
Stack.PushValue("Heap",0)
ElseIf(n=0)Then 'n! where n=0 is 1
Stack.PushValue("Heap",1) 'Set the return value to 1
Else
Stack.PushValue("Heap",n) 'Save Local Variable
Stack.PushValue("Heap",n-1) 'Set Parameter for new Fact() call
Fact() 'Recursion for (n-1)!
'Set return value with n * (n-1)!
Stack.PushValue("Heap",Stack.PopValue("Heap")*Stack.PopValue("Heap"))
EndIf
EndSub
'Fib - Fibonacci calculating
Sub Fib
n = Stack.PopValue("Heap") 'Get parameter
If(n=0)Then
Stack.PushValue("Heap",0) 'Return value for n=0
ElseIf(n=1)Then
Stack.PushValue("Heap",1) 'Return value for n=1
Else
Stack.PushValue("Heap",n) 'Save local variable n
Stack.PushValue("Heap",n-1)'Set Parameter for Fib()
Fib() 'Recursion... WOW! Get Fib(n-1)
ret=Stack.PopValue("Heap") 'Get Result
n=Stack.PopValue("Heap") 'Restore local variable n
Stack.PushValue("Heap",ret)'Save local Variable Ret, n is no more necessary
Stack.PushValue("Heap",n-2)'Set Parameter for Fib()
Fib() 'Recursion...I'm so glad. Get Fib(n-2)
'Return value Fib(n-1)+Fib(n-2)
Stack.PushValue("Heap",Stack.PopValue("Heap")+Stack.PopValue("Heap"))
EndIf
EndSub
Program Listing: BPB749