On 5/8/2011 7:36 PM, Dan Stromberg wrote:
On Sun, May 8, 2011 at 3:41 PM, Terry Reedy <tjre...@udel.edu
<mailto:tjre...@udel.edu>> wrote:
Because inductive algorithms commonly branch on 'input is something'
(not done, change args toward 'nothing'and recurse or iterate)
versus 'input is nothing (done, return base expression).
Just what is an inductive algorithm?
The parenthesized comments were meant to define common patterns such as:
def f(x):
if x:
return g(f(reduce_arg(x))
else:
return base(x)
def f(x)
ret = start(x)
while x:
ret = reduce_arg(x)
return x
More generally, an inductive algorithm computes by looping (with
recursion or iteration). That is my definition. That includes most of
the 'interesting' algorithms. You might ask, what is not an inductive
algorithm? One that does no looping and just returns non-recursive
expressions, perhaps in multiple branches. The functions in the
expression are taken as primitives and their internal use of induction
is ignored. Of course, a computer is nothing but an induction machine:
while not halted:
get next instruction
get args
compute result
Michal Torrie's response is right. Inductive algorithms follow the
pattern of inductive proofs.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
