Page 1 of 1
Double recursion query
Posted: Sun Aug 10, 2025 11:57 am
by JimB007
This code (Fibonacci sequence) when run appears to get stuck. That is, no output occurs. Is it because of the double recursive call to the
fib procedure?
Code: Select all
Procedure fib(n)
If n<=2
ProcedureReturn n
Else
ProcedureReturn (fib(n-2) + fib(n-1))
EndIf
EndProcedure
Debug fib(10)
Re: Double recursion query
Posted: Sun Aug 10, 2025 12:27 pm
by Peter
I can't reproduce that. I get a result: 89
Re: Double recursion query
Posted: Sun Aug 10, 2025 6:02 pm
by JimB007
Can you try changing the fib call to:
See what happens then. For me I get the "compilation in progress" dialog then it closes. No output results.
Re: Double recursion query
Posted: Sun Aug 10, 2025 7:45 pm
by Peter
What do you expect? With fib(100), the procedure is run billions of times. It's understandable that the browser then crashes.
Here is a small code provided by ChatGPT:
Code: Select all
EnableExplicit
Global Dim memo.q(100) ; Cache for memoization
Global naiveCount.q = 0 ; Counter for naive recursion calls
Global memoCount.q = 0 ; Counter for memoized recursion calls
Global iterCount.q = 0 ; Counter for iteration loop steps
; -----------------------------
; Naive recursive Fibonacci
; -----------------------------
Procedure.q fib_naive(n)
naiveCount + 1
If n <= 2
ProcedureReturn n
Else
ProcedureReturn fib_naive(n - 2) + fib_naive(n - 1)
EndIf
EndProcedure
; -----------------------------
; Memoized recursive Fibonacci
; -----------------------------
Procedure.q fib_memo(n)
memoCount + 1
If memo(n) <> 0
ProcedureReturn memo(n)
EndIf
If n <= 2
memo(n) = n
Else
memo(n) = fib_memo(n - 2) + fib_memo(n - 1)
EndIf
ProcedureReturn memo(n)
EndProcedure
; -----------------------------
; Iterative Fibonacci
; -----------------------------
Procedure.q fib_iter(n)
Protected a.q = 1, b.q = 2, temp.q
Protected i
iterCount = n ; Count each loop step
If n <= 2
ProcedureReturn n
EndIf
For i = 3 To n
temp = a + b
a = b
b = temp
Next
ProcedureReturn b
EndProcedure
; -----------------------------
; Run tests
; -----------------------------
Define n = 30 ; Keep small for naive recursion
Define result.q
; Naive recursion
naiveCount = 0
result = fib_naive(n)
Debug "Naive recursion fib(" + Str(n) + ") = " + Str(result)
Debug "Naive recursion calls: " + Str(naiveCount)
; Memoized recursion
memoCount = 0
result = fib_memo(n)
Debug "Memoized recursion fib(" + Str(n) + ") = " + Str(result)
Debug "Memoized recursion calls: " + Str(memoCount)
; Iteration
iterCount = 0
result = fib_iter(n)
Debug "Iteration fib(" + Str(n) + ") = " + Str(result)
Debug "Iteration loop steps: " + Str(iterCount)
Example output for n = 30:
Naive recursion fib(30) = 1346269
Naive recursion calls: 2692537 (!)
Memoized recursion fib(30) = 1346269
Memoized recursion calls: 57
Iteration fib(30) = 1346269
Iteration loop steps: 30
Re: Double recursion query
Posted: Mon Aug 11, 2025 5:56 am
by JimB007
Thanks for the detailed reply and explanation. Now I feel silly.