Ban function recursion and name-hoisting? (2026)

By Xah Lee. Date: .

function recursion

programing language, function recursion should be banned. in recent years, been thinking function def that calls itself, should be banned. because it involves some sort of name hoisting. u want everything linear for simplicity.

recursion should be allowed by having a Nest[f,n], NestWhile[f,p] and FixedPoint[f] functions. (example there is wolfram lang.). its interesting i dont see this Nest in other langs. i think its so elegant.

also, mutual recursion should be banned... or cyclic. only allow self recursion, via Nest. because, they just make things complex.

... sans implementing a lang, am clueless here... any feel free to comment... but i prob no understand it... and gonna ask ai a lot.

8:46 PM · Jul 31, 2026

ai answer

what do you think @grok

Nest/FixedPoint are elegant for pure iteration and dodge name-binding circularity. Self-recursion stays more natural and flexible for trees, graphs, or branching structure where depth isn't known upfront. Mutual recursion has real uses (parsers, even/odd). Banning both simplifies semantics but loses expressiveness; you'd just encode the same logic less clearly. Fine for a deliberately restricted language.

tell me more about mutual recursion, show example

Mutual recursion means two or more functions that call each other.

Classic example (even/odd): 

isEven(n) =
 if n==0 then true
 else isOdd(n-1)

isOdd(n) =
 if n==0 then false
 else isEven(n-1)

isEven(4) → true, isOdd(5) → true.

Useful in recursive-descent parsers (expr calls term, term calls factor, factor calls expr) or tree walks where siblings alternate roles. You can always rewrite it as one function with a flag, but the mutual form often reads clearer.

are you saying mutual recursion is important? the c cpp java no do but the world no collapses? is there actually a single person in real life writes even odd function using mutual recursion?

No, not essential. C/C++/Java all support it (forward decls in C/C++). Everyday code rarely needs it; world runs fine on loops and single recursion.

Even/odd mutual is pure textbook demo. Zero real-life use—just do n%2. Actual cases are recursive-descent parsers and some tree walks where the mutual form is clearer than a flag.

try again. show me a example that mutual recursion is truly useful.

Real use: recursive-descent parsers for expressions. 

expr calls term
term calls factor
factor, on '(', calls expr

Mutual cycle mirrors the grammar, handles nested parens + precedence cleanly. Real compilers/interpreters rely on it. One function + flags works but is less readable and harder to keep in sync with the grammar.

show a example of even odd mutual recursion in java

Here is the classic even/odd mutual recursion in Java: 

class EvenOdd {
 static boolean isEven(int n) {
 if (n == 0) return true;
 return isOdd(n - 1);
 }
 static boolean isOdd(int n) {
 if (n == 0) return false;
 return isEven(n - 1);
 }
}

isEven(4) yields true; isOdd(5) yields true. Pure textbook demo; real code just uses n % 2.

show example of even/odd mutual recursion in c

Here is the classic even/odd mutual recursion in C: 

<stdbool.h>

bool isOdd(int n);

bool isEven(int n) {
 if (n == 0) return true;
 return isOdd(n - 1);
}

bool isOdd(int n) {
 if (n == 0) return false;
 return isEven(n - 1);
}

isEven(4) yields true; isOdd(5) yields true. Pure textbook demo; real code just uses n % 2.

does c support recursion? just single function.

Yes. C has supported single-function recursion from day one.

Example for even/odd: 

bool isEven(int n) {
 if (n == 0) return true;
 return !isEven(n - 1);
}

isEven(4) is true; isEven(5) is false.

ok. u r right that mutual recursion is useful or any cycle of call.

Agreed. Mutual recursion fits problems whose natural structure is cyclic: expression grammars, mutually recursive data types, or certain state machines. Nest/FixedPoint handle pure repeated application of one function cleanly, but the general case of call graphs still benefits from unrestricted recursion (with the usual stack-depth caveats).

now can u explain whats the issue of name hoisting in recursive def of function?

The issue is that a recursive definition refers to the function's own name inside its body. That name must therefore be bound and visible while the body is still being constructed. Ordinary sequential binding (define then use) cannot provide it, so languages either hoist the name into the body (JS function declarations) or introduce a special recursive form such as letrec / rec that makes the binding circular by design. Nest-style constructs avoid the problem entirely by never naming the recursive step.

at what stage of parsing or compiler is this recursive function name binding occur or resolved

It happens after parsing, in the name-resolution / semantic-analysis phase. Parsing only builds an AST containing the free identifier. The binder then installs the name in the environment before (or circularly with) analyzing the body, so the self-reference resolves to the binding being defined. That is why ordinary sequential define/let is insufficient and letrec or hoisting is required.

explain how letrec works, and name hoisting.

letrec first allocates the variable slots (uninitialized), then evaluates the right-hand sides in an environment that already contains those names, and finally stores the results. The body and any RHS can therefore refer to the names being defined, supporting self- and mutual recursion.

Name hoisting (JS function declarations) moves the binding of the name to the top of its scope at compile time. The name is therefore visible everywhere in the scope, so a recursive call inside the body resolves correctly.

how's letrec and name hoisting different? they r diff techniques in the name-binding part of compiling process, right?

Yes, different techniques for name binding to support recursion.

letrec allocates the slots first (uninitialized), evaluates the RHS expressions in an environment that already contains those names (enabling self/mutual refs), then stores the values.

Name hoisting is a compile-time rewrite that moves the binding (and for JS function declarations, the whole body) to the top of the scope so the name is visible everywhere inside it.

Same goal, different stages and mechanisms.

is letrec a generic term for the technique in compiler or is it used mostly by lispers or some functional language community

Mostly from Scheme/Lisp and the functional programming community. Scheme introduced letrec in the 1970s for recursive local bindings. Functional-language compilers and papers use the term routinely; general imperative compiler literature almost never does, preferring other names for similar allocation-then-init techniques.

lol. so you been misleading. then how do c cpp compilers refer to the technique of solving name binding in function calling itself in body?

No misleading. C/C++ compilers have no special term like letrec for this.

They just process the function header first, insert the name into the symbol table, then analyze the body. The self-reference therefore resolves by ordinary name lookup.

Mutual recursion needs an explicit forward declaration so the name exists before either body is seen. That is the entire mechanism.

so, the c cpp compilers dont even have to do anything special. why does lisp need letrec? cant they also, throw the name into a table before looking at the body?

Lisp can and does exactly that. That is what letrec is for.

Ordinary let evaluates every initializer in the outer environment first, then binds the results, then runs the body. The new names are deliberately not visible while the right-hand sides are computed. This keeps non-recursive bindings simple and safe.

When you need the names visible during initializer evaluation (so a lambda can call itself or its mutual partners), you use letrec: allocate the slots first, evaluate the inits in an environment that already contains those names, store the values, then run the body.

C/C++ function definitions have no runtime initializer expression of that kind. The declarator is processed and the name is entered into the symbol table before the body is even looked at. There is therefore no need for a separate recursive binding form.

now, is Name hoisting just a term used by js? i think this technique is also used in other langs, right?

Yes, "name hoisting" is a JavaScript-specific term. The technique of making a name available before its definition site appears in source is widespread: C/C++ enters the name into the symbol table on seeing the declarator; Scheme uses letrec; Java/C# class methods are visible regardless of order within the class; many compilers simply process all declarations in a scope first.

so why only js use this name-hoisting term and technique? why isnt js doing like c?

Only JS needs the term "hoisting" because its function (and var) declarations create availability before the definition site in a way that feels surprising and needs a nickname. Other languages just process declarators early or use multi-pass without special jargon.

JS is deliberately not like C. Function declaration hoisting was chosen so you can call before define and get mutual recursion for free, without forward declarations or forced bottom-up order. C requires the stricter declarator-first model plus explicit forwards.

please show example how c cannot do what js name-hoisting do

JS: 

foo();
function foo(){console.log(1)}
// works (hoisted).

C equivalent: 

int main(){foo();}
void foo(){}
/* fails to compile. Needs prior void foo(); */

Mutual recursion same: JS free any order; C demands forward decls.

thx. please show example what u mean by forward decls for mutual recursion in c.

Example: 

int is_odd(int n); // forward decl

int is_even(int n) {
 if (n==0) return 1;
 return is_odd(n-1);
}

int is_odd(int n) {
 if (n==0) return 0;
 return is_even(n-1);
}

Without the forward decl of is_odd, the call inside is_even fails to compile.

what other langs have js behavior of name-hoisting?

Almost none use the term or exact rewrite. JS function decls (and TypeScript) uniquely hoist the full body so calls work before the text site.

C needs explicit forwards; Python/Ruby require runtime definition first.

can you explain. Go/Rust/Haskell: package/module multi-pass, any order

In Go the compiler collects every declaration across a package's files first, so calls work in any textual order. Rust does the same for items inside a module after full parsing. Haskell treats a module's top-level bindings as one mutually recursive set, so order is irrelevant. No forward declarations needed.

pls explain how they do. Java/C#: class methods any order

In Java and C# the compiler parses the whole class body first, collecting every method signature into the type's member table before analyzing any bodies. Calls then resolve no matter the textual order. No forward declarations needed inside the class.

so, a lot programing languages supports using name before function declaration. i know perl and elisp can too. is there a generic term for this feature? why again just js has the term name-hoisting.

No standard generic term exists. Closest are "forward references" or "declaration collection in a prior pass."

"Hoisting" is pure JS slang for its create-phase behavior (decls treated as if moved to scope top). Tutorials popularized it because of var's undefined init and function-vs-expression quirks. Other languages achieve similar results via multi-pass parsing or runtime lookup without that metaphor.

why cant the js compiler do like other lang by 2-pass approach, why it use this name-hoisting? does the js parser actually rearrange or refactor the decl to top as 1st step???

JS never rearranges source. "Hoisting" is just a metaphor. On scope entry the engine walks the AST and creates all declaration bindings in the environment record before any code runs (spec: Declaration Instantiation). Function decls get the full object; vars get undefined. Same effect as multi-pass collection in other languages, done at runtime setup. Function hoisting was intentional for mutual recursion; var was an unintended 1995 side-effect.

wow. u r amazing. u know so much. can u explain this part more: var was an unintended 1995 side-effect.

Eich made function hoisting deliberate: call before declare enables mutual recursion and top-down code without Lisp-style letrec or forced bottom-up order.

Var just tagged along. Early JS had only function scope (no blocks). In the 10-day 1995 rush the engine created every binding at scope entry. Vars therefore got early undefined bindings as a pure side-effect of that mechanism. Assignment still happens later.

fantastic. ive learned so much. thank u. now on my original question. about not allow a function to call itself, is that a valid concern? seems a trivial binding issue, 2-pass will resolve. but why didnt lisp made letrec as the default behavior of lef?

The self-call concern is not strong enough to ban it. Two-pass (or scope-entry binding collection) is standard, cheap, and already how most languages enable mutual and self recursion without forced bottom-up order. Nest/FixedPoint is elegant explicit iteration, but naming the function remains simpler and more flexible for real code.

Lisp kept let non-recursive so inits evaluate in the outer environment (outer same-name bindings stay visible, no self-ref). letrec installs the bindings first, then evaluates inits inside them—extra machinery and careful init order. Early machines made the cheapest form the default.