Recursion & Data Structures

Stacks power undo systems, expression evaluation (postfix calculators), backtracking, and iterative versions of recursive algorithms.

28.1 Recursion patterns

' Towers of Hanoi
Hanoi 3, "A", "C", "B"
END

SUB Hanoi (n AS INTEGER, from AS STRING, dest AS STRING, via AS STRING)
    IF n = 0 THEN EXIT SUB
    Hanoi n - 1, from, via, dest
    PRINT "Move disk"; n; "from "; from; " to "; dest
    Hanoi n - 1, via, dest, from
END SUB

' All permutations of a string
Permute "", "ABC"
END

SUB Permute (prefix AS STRING, rest AS STRING)
    DIM i AS INTEGER
    IF LEN(rest) = 0 THEN PRINT prefix: EXIT SUB
    FOR i = 1 TO LEN(rest)
        Permute prefix + MID$(rest, i, 1), LEFT$(rest, i - 1) + MID$(rest, i + 1)
    NEXT
END SUB

28.2 Memoization and iteration

DIM SHARED memo(0 TO 90) AS _INTEGER64
PRINT FibMemo&&(90)          ' instant, versus centuries for naive recursion
PRINT FibLoop&&(90)
END

FUNCTION FibMemo&& (n AS INTEGER)
    IF n < 2 THEN FibMemo&& = n: EXIT FUNCTION
    IF memo(n) = 0 THEN memo(n) = FibMemo&&(n - 1) + FibMemo&&(n - 2)
    FibMemo&& = memo(n)
END FUNCTION

FUNCTION FibLoop&& (n AS INTEGER)
    DIM a AS _INTEGER64, b AS _INTEGER64, t AS _INTEGER64, i AS INTEGER
    a = 0: b = 1
    FOR i = 1 TO n
        t = a + b: a = b: b = t
    NEXT
    FibLoop&& = a
END FUNCTION

28.3 Stack (LIFO) with an array

Stacks power undo systems, expression evaluation (postfix calculators), backtracking, and iterative versions of recursive algorithms.

CONST STACK_MAX = 100
DIM SHARED stack(1 TO STACK_MAX) AS LONG, sp AS LONG

Push 10: Push 20: Push 30
PRINT Pop&, Pop&, Pop&       ' 30 20 10
END

SUB Push (v AS LONG)
    IF sp = STACK_MAX THEN PRINT "Stack overflow": EXIT SUB
    sp = sp + 1: stack(sp) = v
END SUB

FUNCTION Pop&
    IF sp = 0 THEN PRINT "Stack underflow": EXIT FUNCTION
    Pop& = stack(sp): sp = sp - 1
END FUNCTION

28.4 Linked list using index "pointers"

Without pointers, store a nxt index in each node; 0 means "none":

FreeBASIC: real pointers make linked structures natural: Type Node: value As Long: nxt As Node Ptr: End Type, allocated with New Node and freed with Delete. VB.NET: use the collections library — Stack(Of T), Queue(Of T), LinkedList(Of T), Dictionary(Of TKey, TValue), SortedDictionary, HashSet(Of T).

TYPE Node
    value AS LONG
    nxt AS LONG
END TYPE
CONST MAXN = 100
DIM SHARED nodes(1 TO MAXN) AS Node, freeTop AS LONG, head AS LONG

InsertSorted 42: InsertSorted 7: InsertSorted 19: InsertSorted 3
p = head
DO WHILE p <> 0
    PRINT nodes(p).value;
    p = nodes(p).nxt
LOOP
END

SUB InsertSorted (v AS LONG)
    DIM n AS LONG, p AS LONG
    freeTop = freeTop + 1: n = freeTop          ' simple allocator (no deletion)
    nodes(n).value = v
    IF head = 0 THEN
        head = n: EXIT SUB
    END IF
    IF v < nodes(head).value THEN
        nodes(n).nxt = head: head = n: EXIT SUB
    END IF
    p = head
    DO WHILE nodes(p).nxt <> 0
        IF nodes(nodes(p).nxt).value > v THEN EXIT DO
        p = nodes(p).nxt
    LOOP
    nodes(n).nxt = nodes(p).nxt
    nodes(p).nxt = n
END SUB