Recursive Algorithm Ontology

FLOW ALGEBRA
RECURSIVE ALGORITHM ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/recursive-algorithm-ontology.html
Domain: Discrete Mathematics > Algorithmic Mathematics > Recursive Algorithm
Authors: Mark Higgins — Sky (Recursive AI)
Project: Kireth Semantic Library

1. PURPOSE
Represent recursive algorithms as typed computational objects with explicit base cases, recursive transitions, termination obligations, correctness properties, resource bounds and machine-readable semantic relationships.

2. ENTITY TYPES
RecursiveAlgorithm <: Algorithm
Problem: Type
Input: Type
Output: Type
State: Type
BaseCase: Predicate(Input)
RecursiveCase: Predicate(Input)
Reduction: Function(Input, Input)
RecursiveCall: Invocation(RecursiveAlgorithm)
Combination: Function(Output*, Output)
RankingFunction: Function(Input, WellFoundedSet)
TerminationProof: Proof
CorrectnessProof: Proof
RecurrenceRelation: Equation
CallTree: DirectedTree
StackFrame: ExecutionState
MemoTable: Map(Input, Output)

3. TYPED RELATIONSHIPS
SOLVES(RecursiveAlgorithm, Problem)
ACCEPTS(RecursiveAlgorithm, Input)
RETURNS(RecursiveAlgorithm, Output)
HAS_BASE_CASE(RecursiveAlgorithm, BaseCase)
HAS_RECURSIVE_CASE(RecursiveAlgorithm, RecursiveCase)
REDUCES_BY(RecursiveAlgorithm, Reduction)
CALLS(RecursiveAlgorithm, RecursiveAlgorithm)
COMBINES_WITH(RecursiveAlgorithm, Combination)
HAS_RANKING_FUNCTION(RecursiveAlgorithm, RankingFunction)
PROVES_TERMINATION(Algorithm, TerminationProof)
PROVES_CORRECTNESS(Algorithm, CorrectnessProof)
HAS_TIME_RECURRENCE(RecursiveAlgorithm, RecurrenceRelation)
USES_MEMOISATION(RecursiveAlgorithm, MemoTable)

4. FORMAL MODEL
Let A : X -> Y be a recursive algorithm.
A(x) = B(x)                                if base(x)
A(x) = C(x, A(r1(x)), ..., A(rk(x)))       if recursive(x)
Precondition: base(x) XOR recursive(x) for every x in the intended domain.
Each recursive argument ri(x) must be valid and must decrease under a well-founded ranking measure for termination.
The combination operator C must be defined on all returned subproblem outputs.

5. EXECUTION SEMANTICS
RULE BASE:
  base(x) AND B(x) = y => EVAL(A, x) -> y
RULE RECURSE:
  recursive(x) AND FOR_ALL i EVAL(A, ri(x)) -> yi
  AND C(x, y1, ..., yk) = y => EVAL(A, x) -> y
RULE INVALID_INPUT:
  NOT precondition(x) => REJECT(x, PreconditionFailure)
RULE NONTERMINATION_RISK:
  no well-founded decrease established => TERMINATION_STATUS = unproven

6. TERMINATION OBLIGATIONS
Choose a well-founded set (W, <) and ranking function rho : X -> W.
For every reachable recursive call A(ri(x)), require rho(ri(x)) < rho(x).
Require a finite number of recursive children at each call and valid base-case coverage.
Under these conditions, no infinite recursive descent is possible.
A ranking function is a sufficient proof technique, not a necessary condition for every terminating recursive program.

7. CORRECTNESS OBLIGATIONS
Define specification S(x, y).
BASE: For each base-case input x, prove S(x, B(x)).
STEP: Assuming S(ri(x), yi) for all recursive children, prove S(x, C(x, y1, ..., yk)).
TOTAL CORRECTNESS = partial correctness AND termination.
Use induction on the ranking measure or on the recursive input structure.

8. COMPLEXITY
Time: T(n) = sum_i T(size(ri(x))) + f(n), with explicit base cost.
Space: S(n) includes active call-stack frames plus auxiliary storage.
A branching call tree may have exponentially many nodes even with linear maximum depth.
Memoisation can reduce repeated-subproblem work where inputs admit stable cache keys.
Tail recursion may permit tail-call optimisation, but optimisation is language/runtime dependent.

9. WORKED EXAMPLE: FACTORIAL
Domain: n in NaturalNumbers.
fact(0) = 1
fact(n) = n * fact(n-1), for n > 0
rho(n) = n; rho(n-1) < rho(n).
Trace: fact(4) -> 4*fact(3) -> 4*3*fact(2) -> 4*3*2*fact(1) -> 24.
Time: Theta(n). Stack: Theta(n) without tail-call optimisation.
Invariant/specification: fact(n) = product of integers 1 through n, with empty product 1.

10. WORKED EXAMPLE: BINARY SEARCH
Precondition: sorted array A, valid half-open interval [lo, hi).
Base: lo >= hi -> NOT_FOUND.
Step: mid = lo + floor((hi-lo)/2).
If A[mid] == target -> mid.
If A[mid] < target -> recurse on [mid+1, hi).
Otherwise -> recurse on [lo, mid).
Measure: hi-lo, strictly decreasing on recursive calls.
Time: O(log n). Stack: O(log n) for a straightforward recursive implementation.

11. RECURSION TAXONOMY
DirectRecursion: algorithm calls itself.
MutualRecursion: algorithms call one another in a cycle.
StructuralRecursion: recursion follows inductive data constructors.
PrimitiveRecursion: defined using base functions, composition and primitive recursion.
GeneralRecursion: may include unbounded minimisation and partial functions.
TailRecursion: recursive call occurs in tail position.
DivideAndConquer: recursive calls solve smaller subproblems then combine results.
Backtracking: recursively explore alternatives with pruning or undo operations.

12. SEMANTIC EQUIVALENCE
SEMANTIC_EQUIVALENCE(recursive, iterative) holds only relative to a specified input domain, output semantics and observable behaviour.
Algorithmic equivalence does not imply equal runtime, memory use, overflow behaviour or evaluation order.
Memoised and non-memoised versions may be extensionally equivalent while having different complexity.

13. INFERENCE RULES
IF recursive call exists THEN CLASSIFY as RecursiveAlgorithm.
IF a reachable base case exists AND each recursive call strictly decreases in a well-founded measure THEN INFER termination, subject to finite branching and valid inputs.
IF correctness induction succeeds AND termination established THEN INFER total correctness.
IF repeated subproblems exist AND results are reusable THEN SUGGEST memoisation.
IF recursive call is in tail position THEN MARK tail_recursive; DO NOT assume compiler optimisation.
IF recursive-call cycle crosses multiple functions THEN CLASSIFY mutual_recursion.

14. VALIDATION
CHECK base-case reachability.
CHECK recursive-case exhaustiveness on domain.
CHECK recursive arguments satisfy input preconditions.
CHECK strict well-founded descent for claimed termination proof.
CHECK combination operator type consistency.
CHECK examples against specification.
CHECK recurrence assumptions before asymptotic simplification.
CHECK integer overflow, stack limits and cyclic data where relevant.

15. CONFIDENCE
DefinitionConfidence: 0.99 (standard mathematical definitions).
ExampleConfidence: 0.99 (for stated domains and assumptions).
TerminationConfidence: PROOF_REQUIRED for each concrete algorithm.
ComplexityConfidence: ASSUMPTION_DEPENDENT.
Confidence values are descriptive metadata, not empirical probability estimates.

16. FLOW_HASH
CanonicalIdentity: recursive-algorithm-ontology
HashAlgorithm: SHA-256
HashInput: canonical UTF-8 serialisation of this flow, excluding the hash value itself.
FLOW_HASH: COMPUTE_AT_PUBLICATION
Do not present a placeholder as a computed digest.

17. UPDATE_MODEL
Version: 1.0
UpdateTriggers: changed definitions, proof obligations, examples, cross-ontology mappings or validation criteria.
UpdatePolicy: increment version; record change log; recompute FLOW_HASH after canonical serialisation.

18. AI_CONSUMPTION
Mode: typed-semantic-reasoning
Tasks: classify recursion, construct call graphs, verify base cases, propose ranking functions, generate proof obligations, analyse recurrences, compare iterative alternatives.
Constraints: do not infer termination solely from the presence of a base case; do not assert correctness without a proof or explicit qualification.
Outputs: typed entities, relationships, proof obligations, derivations, confidence annotations.

19. CROSS-ONTOLOGY LINKS
Algorithm Ontology: general algorithm identity and correctness.
Computability Ontology: recursive and partial computable functions.
Formal Languages Ontology: recursive parsing and grammar derivations.
Graph Ontology: depth-first traversal and recursive search.
Tree Ontology: structural recursion and induction.
Complexity Ontology: recurrence analysis and resource bounds.
Mathematical Logic Ontology: induction and proof rules.

END FLOW ALGEBRA