Group:
repetitive control
Topic:
backtracking
Topic:
continuation
Topic:
lambda calculus
Topic:
recursive data structures
Topic:
self reference
| |
Summary
Recursion allows for self-referential procedure definitions, refinements, and data description. It generalizes repetition; in particular tail-recursion 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 non-recursive, 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. Non-recursive, non-reentrant 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 non-recursive 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 re-initializes 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: fixed-point form
| QuoteRef: tennRD8_1976 ;;446 change recursive functions into fixed-point 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 DO-loops; 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(n-1)
| | QuoteRef: landPJ_1966 ;;116 recursive functions: functions= AE-without-function [function as operand] the function is the fixed point of the AE (x=Fx) so the fixed-point function Y makes non-recursive 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)
|
