checking if a list is empty

[Terry Reedy]

On 5/8/2011 7:36 PM, Dan Stromberg wrote:
>
> On Sun, May 8, 2011 at 3:41 PM, Terry Reedy <tjreedy at udel.edu
> <mailto:tjreedy at 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