C/the.ansi.c.programming.language/notes.accompany.ansi.c/sx7j.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <!-- This collection of hypertext pages is Copyright 1995, 1996 by Steve Summit. -->
   3 <!-- This material may be freely redistributed and used -->
   4 <!-- but may not be republished or sold without permission. -->
   5 <html>
   6 <head>
   7 <link rev="owner" href="mailto:scs@eskimo.com">
   8 <link rev="made" href="mailto:scs@eskimo.com">
   9 <title>section 4.10: Recursion</title>
  10 <link href="sx7i.html" rev=precedes>
  11 <link href="sx7k.html" rel=precedes>
  12 <link href="sx7.html" rev=subdocument>
  13 </head>
  14 <body>
  15 <H2>section 4.10: Recursion</H2>
  16
  17 page 86
  18 <p>Recursion is a simple but deep concept
  19 which is occasionally presented somewhat bewilderingly.
  20 Please don't be put off by it.
  21 If this section stops making sense,
  22 don't worry about it;
  23 we'll revisit recursion in chapter 6.
  24 </p><p>Earlier we said that a function is
  25 (or ought to be)
  26 a ``black box''
  27 which does some job and does it well.
  28 Whenever you need to get that job done,
  29 you're supposed to be able to call that function.
  30 You're not supposed to have to worry about any reasons why the
  31 function might not be able to do that job for you just now.
  32 </p><p>It turns out that some functions
  33 are naturally written in such a way
  34 that they can do their job
  35 by <em>calling themselves</em> to do part of their job.
  36 This seems like a crazy idea at first,
  37 but based on a strict interpretation of our observation about
  38 functions--that
  39 we ought to be able to call them whenever we need their job
  40 done--calling
  41 a function from within itself ought not to be illegal,
  42 and in fact in C it is legal.
  43 Such a call is called a <dfn>recursive</dfn> call,
  44 and it works because it's possible
  45 to have several instances of a function active simultaneously.
  46 They don't interfere with each other,
  47 because each instance has its own copies of its parameters and local variables.
  48 (However,
  49 if a function accesses any static or global data,
  50 it must be written carefully if it is to be called recursively,
  51 because then different instances of it
  52 <em>could</em> interfere with each other.)
  53 </p><p>Let's consider the <TT>printd</TT> example rather carefully.
  54 First,
  55 remind yourself about the reverse-order problem from the
  56 <TT>itoa</TT> example on page 64 in section 3.6.
  57 The ``obvious'' algorithm for determining the digits in a number,
  58 which involves successively dividing it by 10 and looking at
  59 the remainders,
  60 generates digits in right-to-left order,
  61 but we'd usually like them in left-to-right order,
  62 especially if we're printing them out as we go.
  63 Let's see if we can figure out another way to do it.
  64 </p><p>It's easy to find the lowest (rightmost) digit;
  65 that's <TT>n % 10</TT>.
  66 It's easy to compute
  67 all but
  68 the lowest digit;
  69 that's <TT>n / 10</TT>.
  70 So we could print a number left-to-right,
  71 directly,
  72 without any explicit reversal step,
  73 if we had a routine to print all but the last digit.
  74 We could call that routine,
  75 then print the last digit ourselves.
  76 </p><p>But--here's the surprise--the routine to
  77 ``print all but the last digit''
  78 is <TT>printd</TT>,
  79 the routine we're writing,
  80 if we call it with an argument of <TT>n / 10</TT>.
  81 </p><p>Recursion seems like cheating--it seems that if you're
  82 writing a routine to do something
  83 (in this case,
  84 to print digits)
  85 and instead of writing code to print digits
  86 you just punt and call a routine for printing digits
  87 and which is in fact the very routine you're supposed to
  88 write--it seems like you haven't done the job you came to do.
  89 A recursive function seems like circular reasoning;
  90 it seems to beg the question of how it does its job.
  91 </p><p>But if you're writing a recursive function,
  92 as long as you do a little bit of work yourself,
  93 and only pass on a portion of the job to another instance of yourself,
  94 you haven't completely reneged on your responsibilities.
  95 Furthermore,
  96 if you're ever called with such a small job to do
  97 that the little bit you're willing to do encompasses the whole job,
  98 you don't have to call yourself again
  99 (there's no remaining portion that you can't do).
 100 Finally,
 101 since each recursive call does some work,
 102 passing on smaller and smaller portions to succeeding recursive calls,
 103 and since the last call
 104 (where the remaining portion is empty)
 105 doesn't generate any more recursive calls,
 106 the recursion is broken
 107 and doesn't constitute an infinite loop.
 108 </p><p>Don't worry about the quicksort example
 109 if it seems impenetrable--quicksort is an important algorithm,
 110 but it
 111 is not easy
 112 to understand completely at first.
 113 <br></p><p>Note that the <TT>qsort</TT> routine described here is very different
 114 from the standard library <TT>qsort</TT>
 115 (in fact, it probably shouldn't even have the same name).
 116 </p><hr>
 117 <p>
 118 Read sequentially:
 119 <a href="sx7i.html" rev=precedes>prev</a>
 120 <a href="sx7k.html" rel=precedes>next</a>
 121 <a href="sx7.html" rev=subdocument>up</a>
 122 <a href="top.html">top</a>
 123 </p>
 124 <p>
 125 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 126 // <a href="copyright.html">Copyright</a> 1995, 1996
 127 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 128 </p>
 129 </body>
 130 </html>