COMP1811 Paradigms of Programming
Introduction to Recursion in Scheme
Numbers and Lists
Copyright By PowCoder代写 加微信 powcoder
• Problem Solving.
• Inductive Defined types.
• Principles of recursion design
• Recursion on lists
• Operational approach.
• Different approaches
– Translating the data to be solved as other, then do inverse
translation.
– Instantiating a more general problem.
– Iteratingtoapproachingthesolution.
– Reducing the size of data on same problem, then solving.
• Usually they mix each other (not in this lecture)
Problem Solving.
• Naturals:
• N ::= 0 | suc(N)
• Lists: (cons 3 (cons 2 (cons 1 ( cons 0 ())))) -> (3,2,1,0) • L::=empty|conselemL
• Be warned: lists are not vectors (or lists in Python)
• Accessing l[n] is not random, but sequential (you have to run
all previous to reach it)
• Accessing l[n] (in Python jargon) is not so “fast”.
suc(suc(suc(0))) -> 3
Inductive Defined Types
Naturals and Lists
• Contracts on input/output
– I require this input. .
– I commit to this output.
– It is not code, very important, though!.
– No further reduction. Trivial Solution
– (Possible more than one)
• Successor:
– Reducing the size of data (quota)
• Recursion step
– Solve for minor size.
– (Possible more than one)
• Computation function.
Cond(input)
ond(input)
Cond(output) Cond(output)
Cond(input) Suc (input) Compute
Cond(output)
Cond(output)
Suc(input)
– Post-process the recursive result with parameters (May be unnecessary)
Principles of recursion design
A Template is not runnable code. It belongs to “metacode” (code who describes code)
• Shape of function (paramet)
• Formulate informally the contract
on parameters.
• Sketch the solution for general
case (comp ,succ, rec).
• Check successor’s adequacy to
• Identify base cases and solve them
• Iterate until consistent solution reached*.
*Techniques for formal correctness verification exists. Out of scope this course
Template in Scheme
To keep consistency, mind some non-intuitive properties about lists.
The empty list 0 – of summands yields 0 (neutral for +).
• 𝑖1+⋯+𝑖𝑛=0 ifn=0
– of factors yields 1 (neutral for *). 1
• 𝑖1∗⋯∗𝑖𝑛=1 ifn=0
– of booleans yields true for universal properties (all,and)
• 𝑖1∧⋯∧𝑖𝑛=⊤ifn=0
– of booelans yields false for existential properties (any,or)
• 𝑖1∨⋯∨𝑖𝑛=⊥ifn=0
True False
All the element of the empty list are flying cows
There are no flying cows in the empty list
Maximum, minimum are undefined on empty lists. Required one! – Any value you may offer would be inconsistent.
Recursion on lists
Empty lists Golden Rules
• Contract:
– Input: list of integers, possibly empty
– Output: sum of every element
• Sketch reduction:
– “Solve for the rest of the list. Then add
my first number”
– (rest l) fits contract?
• (Only if list not empty. Fixed condition for general)
– Which is the solution for empty? (neutral element for +)
Mind error on contract violation (we don’t care!)
Recursion on lists
(sum-list)
Mind error on contract violation (we don’t care!)
• Contract:
– Input: List (possibly empty) of anything.
– Output: True if all elements are symbols
• Sketch reduction:
– “Solve for the rest of the list. If they are all symbols and as well as my first symbol, then all the list is.”
– (rest l) fits contract?
• (Only if (non-empty). Fixed condition for general)
– Which is the solution for empty?true
Recursion on lists
(all-symbols?)
Mind error on contract violation (we don’t care!)
• Contract:
– Input: non-empty list of integers
– Output: max of every element
• Sketch reduction:
– “Solve for the rest of the list. Then
select between result and first”
– (rest l) fits contract?
• (Only if (two or more items). Fixed condition for general)
– Which is the solution for singletonlist? The only element
Recursion on lists
• Does it make sense? • Hints
• Mind metaprogramming
• Don’t abuse quote shortcut notation. Use original (quote a)
• Check what quote return when applied to id and lists.
The million-pound challenge
(You may skip)
– Input: List (possibly empty) of anything, index not beyond limit.
– Output: access element Sketch reduction (Sliding list):
– “Solve for slided list, decreasing i” Succ:
(Rest l) and (-nth 1) fit contract?
• (Only if (non-empty). If empty, I cannot have (0 <= nth < 0)
• (Fixed condition for general)
– Which is the solution for empty?
Mind error on contract violation (we don’t care!)
(my-list-ref)
– Input: List (possibly empty) of anything.
– Output: reverted list Sketch reduction:
– “Solve for the slided list... Then, append the list formed by the first element...”
Why the list and not just “the first Succ: element”
– (rest l) fits contract?
• (Only if (non-empty). Fixed
condition for general)
– Which is the solution for empty?
• Contract:
– Input: See relation between 0<= I <= j <=
– Output: Semiopen segment [i,j)
• Sketch reduction (“Sliding list”): 13– Two cases:
– shift the rest of list,
– decreasing i,j
– Grab first element
– shift rest of list, decreasing only j
– Succ (rest) fits contract?
• Only if i<> j. Otherwise, they cross!
– Which is the solution for i=j?
Mind error on contract violation (we don’t care!)
The growing structure is an stack.
• On non-tail recursion, it may run-out your
• We’ll see other forms as tail recursion.
Use trace to debug your functions
Under the hood
Operational approach
• What if You don’t decrease the quota?
• Program may loop forever…
• Or runout of memory in some cases!
Don’t forget reduce the size…
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com