Topic: recursion

topics > computer science > programming > Group: program control

repetitive control

lambda calculus
recursive data structures
self reference


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 up

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 up

QuoteRef: tennRD8_1976 ;;446 change recursive functions into fixed-point form

Subtopic: nestexit up

Quote: Madcap 6 includes a 'nestexit' to exit from all nested recursive calls [»morrJH8_1972]

Subtopic: examples up

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 up

Quote: van Wijngaarden's approach may be too subtle and intricate to explain a programming language; highly recursive from simple rules

Related Topics up

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)

Updated barberCB 12/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.