文档介绍：Algorithms plexity
Herbert S. Wilf
University of Pennsylvania
Philadelphia, PA 19104-6395
Copyright Notice
Copyright 1994 by Herbert S. Wilf. This material may be reproduced for any educational purpose, multiple
copies may be made for classes, etc. Charges, if any, for reproduced copies must be just enough to recover
reasonable costs of reproduction. Reproduction mercial purposes is prohibited. This cover page must
be included in all distributed copies.
Edition, Summer, 1994
This edition of Algorithms plexity is the
le “pub/wilf/” at the anonymous ftp site
“”. It may be taken at no charge by all interested persons. Comments and corrections
are e, and should be sent to ******@
Introduction
Chapter 2: Recursive Algorithms
Introduction
Here are two di
erent ways to de
ne n!, if n is a positive integer. The
rst de
nition is nonrecursive,
the second is recursive.
(1) ‘n! is the product of all of the whole numbers from 1 to n, inclusive.’
(2) ‘If n = 1 then n!=1,elsen!=n
(n
1)!.’
Let’s concentrate on the second de
nition. At a glance, it seems illegal, because we’re de
ning something,
and in the de
nition the same ‘something’ appears. Another glance, however, reveals that the value of n!is
de
ned in terms of the value of the same function at a smaller value of its argument, viz. n
1. So we’re
really only using mathematical induction in order to validate the assertion that a function has indeed been
de
ned for all positive integers n.
What is the practical import of the above? It’s monumental. Many modern high-puter
languages can handle recursive constructs directly, and when this is so, the programmer’s job may be
considerably simpli
ed. Among recursive languages are Pascal, PL/C, Lisp, APL, C, and many others.
Programmers who use these languages should be aware of the power and versatility of recursive methods
(conversely, people who like recursive methods should learn one of tho