TEACH RECURSE3 Aaron Sloman November 1989 RECURSION AND THE TERMINATING VALUE People learning about recursion often have considerable difficulty over what to do with the terminating condition, especially when recursing down a list. What result should be returned when the empty list [] is found? In particular, difficulties often arise if it is decided to make -false- the result when the list is empty, and otherwise to return a list of items. This teach file explores some of the design issues that need to be understood in dealing with such cases. CONTENTS - (Use g to access required sections) -- The problem -- How can we think about taking this decision? Two issues -- Addressing the first issue: Q1 -- SUMMARY of answer to Q1: -- How to answer Q2 -- What if the answers to Q1 and Q2 are different ? -- The complicated solution -- The simpler (divide and conquer) solution -- POP-11 allows nested procedure definitions -- Final silly exercise -- Further Reading -- The problem -------------------------------------------------------- We are talking about a schema of the SECOND of the following two forms, representing a procedure P that takes a list, and possibly other arguments (e.g. a predicate), and recurses down the list, looking at every element for some purpose, and returns some result. Schema (A) The procedure produces no result (e.g. because it is doing something with some or all elements of the list such as printing them on the terminal, or putting them into the database or writing them to a file). define P(list, .....); ..... enddefine; Ignore Schema (A) for now. It is mentioned simply to point out that the following discussion does not apply to it, as we are considering only recursive procedures that produce a result (on the stack). Schema (B) A result is produced. define P(list, ....) -> result; ...... enddefine; The problem is: what should the result for the stopping condition be? define P(list, ....) -> result; if list == [] then ???? -> result else(if) ...... ...... endif enddefine; -- How can we think about taking this decision? Two issues ------------ In order to answer this question you have to separate two different questions and think VERY clearly about them. Q1. What should the procedure P return when given an empty list? Q2. What does the result of P have to be for the recursive terminating case in order that the result can be used sensibly for the other (non-terminating) cases? Let's ignore Q2 for now, and concentrate on Q1. -- Addressing the first issue: Q1 ------------------------------------- Q1 Has to be answered on the basis of how the problem is defined originally, and THAT may depend on what you want to use the procedure P for, e.g. which other procedures will call it. CASE 1 The procedure is to be used in CONDITIONs like these: if P(.........) then ..... until P(.........) do ..... while P(.........) do ..... then the answer to Q1 should be that the procedure produces a result that is essentially BOOLEAN, i.e. sometimes false, sometimes not. (Remember in Pop-11 anything other than false counts as true, in a condition.) If P never returns false, in these contexts, then the condition will always be true, and there is no point using a condition. CASE 2 The result of the procedure is to be used as one argument for an operation or procedure that REQUIRES a list as input, as in: .... :: P(.....) (Second arg of "::" MUST be a list) P(.....) <> ....... (Both args of "<>" MUST be lists) [^^(P(......) ....] ("^^" in a list REQUIRES a list) rev(P(.....)) (Arg of "rev" MUST be a list) Then for these uses P MUST always return a list (which could be [], as that is a list). CASE 3 The result of P is used as one argument for an arithmetic operation, e.g. "+" or "*", as in x + P(x - 1) (Arguments for "+" MUST be numbers) Then the result of P MUST be a number (e.g. it could be 0). CASE 4 The result of P is used as input to some other procedure that requires a particular type of result (e.g. a string, or a vector, etc), e.g. subscrs(num, P(.....)) subscrv(num, P(.....)) then the result of P MUST be an object of the required type. CASE 5 the result of P is used only as input for procedures that will operate on ANY kind of object, e.g. the first argument of -member- can be any kind of object. In that case you don't get any programming constraints on the result of P, though there may be other constraints, that depend on what the procedure is supposed to be doing. -- SUMMARY of answer to Q1: ------------------------------------------- The result produced by P depends on the kind of use to which the result is to be put. So for some procedures the result should be boolean, for others a (possibly empty) list, for others a (possibly zero) number, etc. -- How to answer Q2 --------------------------------------------------- As you may already have noticed, in a recursive procedure P, the result of a recursive call will itself be used in some way, and THAT use can determine what sort of result the recursive call should produce, including the terminating case. E.g. if P is making a list of objects, and the result of the recursive call is used in creating that list, i.e. the recursive call is used something like this: hd(list) :: P(tl(list), ....) -> result P(tl(list), ....) <> ....... -> result [^^(P(tl(list), ....) ....] -> result then the recursive call (on tl(list)) MUST always return a list, possibly []. It must NOT return FALSE, or the program will produce ;;; MISHAP - LIST NEEDED ;;; INVOLVING: ;;; DOING : :: P(*3) ..... where P(*3) means it was three levels deep in recursion in P when the error occurred, and "::" in the DOING list tells you that it is complaining about being given as argument to "::" If P is traced the last bit of tracing before the error would be something like this !!!> P [] !!!< P i.e. it recursed on [], returned false, and then the PREVIOUS call of P waiting for the result of P([]) complained. So if the result of the recursive call is used as input to a list-processing procedure, then the result for the terminating condition MUST be a list. This will usually be [], but it may be some other list in more complex cases. Similarly, if the result of the recursive call is used as input for an arithmetic operation, then the result of the terminating condition MUST be a number, e.g. 0 or 1, as in define P(list) -> result if list == [] then 0 -> result else hd(list) + P(tl(list)) -> result endif enddefine; -- What if the answers to Q1 and Q2 are different ? ------------------- Then you have a problem. There are two different solutions. The complicated one is to try to make one procedure definition for P handle the situation. The simpler solution is to use two procedures, one that does the work, and one that calls it and decides whether to return false. -- The complicated solution ------------------------------------------- Here for example is a version of findall that takes a list and a predicate and returns false if NO items in the list satisfy the predicate, otherwise a list of all the items that do. define findall(list, pred) -> out; if list == [] then false -> out else ;;; first get the result for the tail, and then decide what ;;; to do about the head findall(tl(list), pred) -> out; if out then ;;; out is not false, so it must be a list. Use it if pred(hd(list)) then [^(hd(list)) ^^out] -> out else ;;; do nothing - return previous value of out endif else ;;; decide what to by testing hd(list) if pred(hd(list)) then ;;; ignore previous value of out, because it is false [^(hd(list))] -> out else ;;; do nothing - return previous (false) value of out endif endif endif enddefine; NOTE: you can remove the empty "else" clauses. We can test this to make sure it works. findall([], isword) => ** findall([cat],isword) => ** [cat] findall([1 cat on 2 mats],isword) => ** [cat on mats] -- The simpler (divide and conquer) solution -------------------------- The above definition is fairly complex, even if you ignore the empty "else" clauses. But you can do it more simply by defining a recursive sub-procedure called sub_find, that returns a LIST under all conditions, and then define findall to see if the list is empty. define findall(list, pred) -> out; sub_find(list, pred) -> out; ;;; decide whether to replace the value of out with false if out == [] then false -> out endif; enddefine; define sub_find(list, pred) -> out; if list == [] then [] -> out elseif pred(hd(list)) then [^(hd(list)) ^^(sub_find(tl(list), pred))] -> out else sub_find(tl(list), pred) -> out endif enddefine; findall([], isword) => ** findall([cat],isword) => ** [cat] findall([1 cat on 2 mats],isword) => ** [cat on mats] NOTE You might have been tempted to write [^^(sub_find(tl(list), pred))] -> out Can you see why that is unnecessary complexity? (The square brackets say make a list. "^^(...)" says put in all the elements of the list you started with!). -- POP-11 allows nested procedure definitions ------------------------- If the procedure -sub_find- is used nowhere but in findall, then we can hide it from everything else, by actually putting its definition INSIDE that of findall. If you do that, make sure that you give the nested definition extra indentation to show very clearly that it is nested. tidy (or jcp if the cursor is at the beginning of the outer definition) will do this automatically. (See HELP * MARK ) This is how the nested procedures look: define findall(list, pred) -> out; define sub_find(list, pred) -> out; if list == [] then [] -> out elseif pred(hd(list)) then [^(hd(list)) ^^(sub_find(tl(list), pred))] -> out else sub_find(tl(list), pred) -> out endif enddefine; sub_find(list, pred) -> out; ;;; decide whether to replace the value of out with false if out == [] then false -> out endif; enddefine; You can make your nested procedure slightly more efficient if you replace the nested "define" with "define lconstant", as in: define findall(list, pred) -> out; define lconstant sub_find(list, pred) -> out; if list == [] then [] -> out elseif pred(hd(list)) then [^(hd(list)) ^^(sub_find(tl(list), pred))] -> out else sub_find(tl(list), pred) -> out endif enddefine; sub_find(list, pred) -> out; ;;; decide whether to replace the value of out with false if out == [] then false -> out endif; enddefine; -- Final silly exercise ----------------------------------------------- As a test for whether you have understood all that, try to define a recursive procedure called silly that takes a list of numbers and returns the sum of all the numbers if the list is non-empty, otherwise, for the empty list, returns the result FALSE, not 0! silly([]) => ** false silly([3 4 5]) => ** 12 -- Further Reading ---------------------------------------------------- TEACH * RECURSE1 TEACH * RECURSE2 TEACH * SETS TEACH * SETS2 --- C.all/teach/recurse3 --- Copyright University of Sussex 1990. All rights reserved. ----------