Updated 2018-04-20 08:34:31 by pooryorick

Recursion occurs when a routine calls itself.

Examples  edit

Description  edit

Richard Suchenwirth 2005-04-08

Recursion is popular in functional programming. In Tcl, we're a bit handicapped by the [interp recursionlimit] which is at ~398 on Windows, even if set higher.

Here's an example for a recursive integer range generator, so that [iota1 5] == {1 2 3 4 5} :
proc iota1 n {expr {$n == 1? 1: [concat [iota1 [- $n 1]] $n]}}

rdt For completeness, shouldn't your definition of - (from func) be here also? - RS: Oops, of course - just another one-liner :)
proc - {a {b ""}} {expr {$b eq ""? -$a: $a-$b}}

To illustrate the recursionlimit problem (which is directly related to the C stack):
% interp recursionlimit {} 10000
10000
% proc Llength list {expr {$list eq ""? 0: 1 + [Llength [lrange $list 1 end]]}}
% Llength [iota1 398]
398
% Llength [iota1 399]
too many nested evaluations (infinite loop?)

Of course it's silly to reimplement llength this wasteful way, as lists first and foremost know how long they are, but in Lisp this implementation might make more sense :)

Lars H: On the bifurcation page there is a Tcl command with which one can do "in-place recursion" (even branching recursions), i.e., recursion without using up space on the C stack.

NEM: See tail call optimization for other ways of achieving recursion in constant stack space.


[Category Concept Arts and crafts of Tcl-Tk programming]