6.16 Recursion

8.12

6.16 Recursion🔗ℹ

Rhombus functions defined with fun can be recursive, of course, but the recur form offers a shorthand for the case that a recurive function would be used just once and is better written inline. Iteration with for is also a kind of recursion, but recur supports non-tail recursion, instead of only iterative loops.

expression

recur id(bind_maybe_kw_opt, ...) maybe_res_annot:

body

...

Similar to defining id as a function and immediately calling it, where id is bound only within the body block for recursive calls. The intent is to implement a recursive calculation “in place,” instead of defining a recurive function and then calling it—including cases where the recursion is not in tail position or where for is not a good fit for some other reason.

Racket and Scheme programmers will recognize this form as a kind of “named let.”

To enable the immediate call of id, each bind_maybe_kw_opt must include a “default” expression, and the immediate call is like supplying zero arguments. Thus, each “default” expression is really an initial-value expression. The binding of id within the body block, however, is a function where only keyword arguments are optional. The default value for a keyword argument in a recursive call, meanwhile, is whatever was supplied for the enclosing call, with the effect that keyword arguments are automatically propogated in a recursive call.

Beware that when maybe_res_annot specifies a result annotation using ::, the annotation is checked on every recursive call. In that case, no recursive calls are in tail position.

> recur nest_to(n = 5):
    match n
    | 0: [0]
    | ~else: [n, nest_to(n-1)]
[5, [4, [3, [2, [1, [0]]]]]]

> recur sum_halves(l = [1, 2, 3, -4, 5, -6],
                   ~pos_sum: pos_sum = 0,
                   ~neg_sum: neg_sum = 0):
    match l
    | []:
        values(pos_sum, neg_sum)
    | [n, & ns]:
        if n > 0
        | sum_halves(ns, ~pos_sum: pos_sum + n)
        | sum_halves(ns, ~neg_sum: neg_sum + n)
11
-10

1	Rhombus Essentials
2	Collections and Iteration
3	Syntax Objects and Macros
4	Classes and Interfaces
5	Static Information and Binding
6	Core Reference
7	Meta and Macros Reference
8	Rhombus Static by Default
9	Libraries
10	Naming Conventions

6.1	General Forms
6.2	Definitions
6.3	Namespaces
6.4	Import
6.5	Export
6.6	Functions
6.7	Operators
6.8	Classes and Interfaces
6.9	Veneers
6.10	Mutable Variables and Assignment
6.11	Repetitions
6.12	Block
6.13	Conditionals
6.14	Matching
6.15	Iteration
6.16	Recursion
6.17	Context Parameters
6.18	Exceptions
6.19	Continuations
6.20	Implicit Forms
6.21	Static and Dynamic Lookup
6.22	Modules and Submodules
6.23	Booleans
6.24	Numbers
6.25	Characters
6.26	Strings
6.27	Keywords
6.28	Symbols
6.29	Byte Strings
6.30	Lists
6.31	Pairs and Pair Lists
6.32	Mutable Lists
6.33	Arrays
6.34	Maps
6.35	Sets
6.36	Boxes
6.37	Indexables
6.38	Listables
6.39	Sequences
6.40	Appendables
6.41	Comparables
6.42	Paths
6.43	Source Locations
6.44	Void
6.45	Equality
6.46	Dot
6.47	Multiple Values
6.48	Annotations
6.49	Enumerations
6.50	Input and Output
6.51	Eval
6.52	Syntax Objects
6.53	Syntax Classes
6.54	Simple Expression Macros
6.55	Unit Testing