Recursion occurs when a routine calls itself.



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
% proc Llength list {expr {$list eq ""? 0: 1 + [Llength [lrange $list 1 end]]}}
% Llength [iota1 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.