Double recursion query

[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)

[Peter]

I can't reproduce that. I get a result: 89

[JimB007]

Can you try changing the fib call to:

Code: Select all

Debug fib(100)

See what happens then. For me I get the "compilation in progress" dialog then it closes. No output results.

[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

[JimB007]

Thanks for the detailed reply and explanation. Now I feel silly.