A handler that calls itself
Some problems contain smaller copies of themselves. The factorial of 5 (5 × 4 × 3 × 2 × 1) is 5 times the factorial of 4; a folder holds files and smaller folders, which hold files and smaller folders. A handler can solve such a problem by calling itself on the smaller copy: this is recursion.
function factorial pN
if pN <= 1 then return 1
return pN * factorial(pN - 1)
end factorial
put factorial(5)
put factorial(20)120 2432902008176640000
Every recursive handler has two parts: a base case, small enough to answer at once (pN <= 1), and a recursive case, which makes the problem smaller and calls itself. Each call has its own pN, so factorial(5) waits for factorial(4), which waits for factorial(3), down to the base case, and the answers come back up.
No base case, no end
Without a base case, or with one it never reaches, a handler calls itself until xTalk runs out of room and stops it with an error, on the line of the call:
function countDown pN
return countDown(pN - 1)
end countDown
put countDown(10)The engine's recursionLimit property sets how deep calls may go. Raising it is rarely the fix: check that each call really makes the problem smaller, and that the base case catches it.
Thinking recursively
Recursion shines when the answer is easy to describe in terms of a smaller answer. The Tower of Hanoi moves a pile of disks from one peg to another, one disk at a time, never a big disk on a small one. Hard to plan move by move, it is three lines recursively: move all but the bottom disk out of the way, move the bottom disk, and move the others back on top of it:
local sMoves
command hanoi pDisks, pFrom, pTo, pVia
if pDisks is 0 then exit hanoi
hanoi pDisks - 1, pFrom, pVia, pTo
put pFrom && "to" && pTo & return after sMoves
hanoi pDisks - 1, pVia, pTo, pFrom
end hanoi
put empty into sMoves
hanoi 3, "A", "C", "B"
put the number of lines of sMoves && "moves:"
put line 1 to 3 of sMoves7 moves: A to C A to B C to B
Walking through folders
Folders inside folders are recursion's home ground. This function lists everything in a folder, then calls itself for each folder inside, indenting a step at each level. folders() includes .., the folder above, which must be skipped, or the walk would climb back up for ever:
function listTree pFolder, pIndent
local tList, tNames, tName
put files(pFolder) into tNames
sort tNames
repeat for each line tName in tNames
put pIndent & tName & return after tList
end repeat
put folders(pFolder) into tNames
sort tNames
repeat for each line tName in tNames
if tName is ".." then next repeat
put pIndent & tName & "/" & return after tList
put listTree(pFolder & "/" & tName, pIndent & " ") after tList
end repeat
return tList
end listTree
function deleteTree pFolder
local tName, tCount
repeat for each line tName in files(pFolder)
delete file (pFolder & "/" & tName)
add 1 to tCount
end repeat
repeat for each line tName in folders(pFolder)
if tName is ".." then next repeat
add deleteTree(pFolder & "/" & tName) to tCount
end repeat
delete folder pFolder
return tCount
end deleteTree
put specialFolderPath("temporary") & "/oxt-lesson-tree" into tRoot
create folder tRoot
create folder (tRoot & "/docs")
create folder (tRoot & "/docs/old")
put "x" into URL ("file:" & tRoot & "/readme.txt")
put "x" into URL ("file:" & tRoot & "/docs/guide.txt")
put "x" into URL ("file:" & tRoot & "/docs/old/notes.txt")
put "x" into URL ("file:" & tRoot & "/docs/old/draft.txt")
put listTree(tRoot, "")
put deleteTree(tRoot) && "files deleted"readme.txt
docs/
guide.txt
old/
draft.txt
notes.txt
4 files deleted
The empty line comes from the list's last return. Each call works on one folder and trusts the calls it makes to deal with the folders inside: that trust is the whole trick of recursion.
Arrays inside arrays
An array's elements can be arrays themselves, to any depth (Arrays), and a recursive handler is the natural way to visit them all:
function countValues pArray
local tKey, tCount
if pArray is not an array then return 1
repeat for each key tKey in pArray
add countValues(pArray[tKey]) to tCount
end repeat
return tCount
end countValues
put "Ada" into tPerson["name"]
put "London" into tPerson["address"]["city"]
put "UK" into tPerson["address"]["country"]
put "maths" into tPerson["likes"][1]
put "machines" into tPerson["likes"][2]
put "poetry" into tPerson["likes"][3]
put countValues(tPerson)6
Remembering answers
A recursive handler can do the same work many times. The Fibonacci numbers (each the sum of the two before) are a famous case: fib(30) worked out plainly calls itself well over a million times, mostly to work out the same few values again. Keep each answer in an array the first time, and every later call is a lookup. This is called memoization:
local sKnown
function fib pN
if pN < 2 then return pN
if sKnown[pN] is empty then
put fib(pN - 1) + fib(pN - 2) into sKnown[pN]
end if
return sKnown[pN]
end fib
put fib(30)
put fib(50)832040 12586269025
Drawing with recursion
A tree is a trunk with two smaller trees on top of it. Written that way, a few lines draw one: each call draws a branch, then calls itself twice for two shorter branches, turned left and right. One graphic holds every branch: in a graphic's points, an empty line lifts the pen, so the branches need not join up.
local sPoints
command branch pX, pY, pLength, pAngle, pDepth
if pDepth is 0 then exit branch
put pX + pLength * cos(pAngle) into tX
put pY - pLength * sin(pAngle) into tY
put round(pX) & comma & round(pY) & return after sPoints
put round(tX) & comma & round(tY) & return & return after sPoints
branch tX, tY, pLength * 0.75, pAngle + pi / 7, pDepth - 1
branch tX, tY, pLength * 0.75, pAngle - pi / 7, pDepth - 1
end branch
put empty into sPoints
branch 240, 350, 80, pi / 2, 9
create graphic "Tree"
set the style of it to "polygon"
set the points of it to sPoints
set the foregroundColor of it to "#15803D"
set the lineSize of it to 2
put the number of lines of sPoints div 3 && "branches"511 branches
Nine levels of two calls each make 29 − 1 = 511 branches. Change the angle, the 0.75 or the depth, and the tree changes shape.
Try it yourself
Write a recursive function reverseText that reverses text: the reverse of a text is the reverse of everything after its first character, followed by the first character. What is the base case? Reverse stressed.
Show a solution
The base case is text of one character or none, which is its own reverse.
function reverseText pText
if the length of pText <= 1 then return pText
return reverseText(char 2 to -1 of pText) & char 1 of pText
end reverseText
put reverseText("stressed")
put reverseText("racecar")desserts racecar
Words in this lesson
Each one finds every lesson that uses it. The Dictionary has the whole story of each, with its syntax and more examples.