Group: repetitive control
Topic: backtracking
Topic: continuation
Topic: lambda calculus
Topic: recursive data structures
Topic: self reference
 
Summary
Recursion allows for selfreferential procedure definitions, refinements, and data description. It generalizes repetition; in particular tailrecursion is equivalent to a simple loop. Recursion is particularly suited to embedded structures such as syntax trees, list processors, and symbolic representation. Embedded structures can also be built through nonrecursive, incremental development of descriptions.
Recursion is conceptually difficult because of its arbitrary embedding depth and sudden context change from initial call to recursive calls. Generalized recursion is expensive because the system's state must be saved before each recursive call. These costs are illustrated by code generation for PL/M. Nonrecursive, nonreentrant code generation is usually within 50% of assembly code length while recursive or reentrant code is about ten times that of assembly code. Implementation costs can be reduced by converting recursion to nonrecursive forms, or by identifying critical state information as a record which is saved between calls. Thimbleby defines a control structure similar to recursion. His 'recall' statement reinitializes a procedure's execution after removing the current execution stack. (cbb 5/80)
Subtopic: recursion vs. loops
Quote: recursion is more natural than repetition because when there's more to be done, one specifies it [»hehnEC4_1979]
 Quote: every program can be written as a recursive function without assignments or gotos [»dijkEW5_1965]
 Quote: recursive refinement is better than the repetitive DO statement [»hehnEC4_1979]
 Quote: with recursive refinement, each alternative is independent; specify further (possibly recursive) action only where needed [»hehnEC4_1979]
 Quote: can implement Dijkstra's 'do' statement via recursive calls of Hehner's 'if' statement
 Quote: with do..od, immediate exit if omit the recursive "DO" from some alternative
 Quote: transform recursion to iteration to eliminate stack frames; based on input increment; constant extra space [»liuYA1_2000]
 QuoteRef: hamiM3_1976 ;;14 loops not allowed in HOS specification. Instead uses recursion with all variables unique and protected
 Subtopic: fixedpoint form
QuoteRef: tennRD8_1976 ;;446 change recursive functions into fixedpoint form
 Subtopic: nestexit
Quote: Madcap 6 includes a 'nestexit' to exit from all nested recursive calls [»morrJH8_1972]
 Subtopic: examples
Quote: EDSAC's floating point interpreter had recursion, an index register. and DOloops; first recorded use of recursion [»campM1_1980]
 Quote: example of writing a recursive expression refinement for factorial [»redeDH7_1979]
 Quote: recall(p,x) is for simplifying program design; like recursion [»thimH2_1980]
 QuoteRef: landPJ_1966 ;;116 factorial: f= Y lambda f. lambda n. if n=0 then 1 else n* f(n1)
 QuoteRef: landPJ_1966 ;;116 recursive functions: functions= AEwithoutfunction [function as operand] the function is the fixed point of the AE (x=Fx) so the fixedpoint function Y makes nonrecursive i.e. x=YF
 Subtopic: problems with recursion
Quote: van Wijngaarden's approach may be too subtle and intricate to explain a programming language; highly recursive from simple rules [»wirtN1_1966]

Related Topics
Group: repetitive control (7 topics, 117 quotes)
Topic: backtracking (30 items)
Topic: continuation (16 items)
Topic: lambda calculus (16 items)
Topic: recursive data structures (18 items)
Topic: self reference (27 items)
