Can anyone explain to me recursion from a C point of view I've found
this.

http://en.wikipedia.org/wiki/Recursi...mputer_science)

I was wondering if someone could help me with a simple example in C.

Thanks to those interested.

Bill

"Bill Cunningham" <nospam@nspam.com> wrote in message
news:t_x8k.22$x65.13@trnddc01...
Maybe this is the right link.

Bill Cunningham said:

If a function calls itself, that's recursion.

If two functions call each other, that's recursion.

If A calls B calls C calls A, that's recursion.

And so on.

<snip>

int main(void) { return main(); }

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

<snip>


int factorial(int n)
{
if(n==0)
return 1;
return n * factorial(n-1);
}

Anytime you re-enter a function before you exit.

w..

Richard Heathfield wrote:

"Bill Cunningham" <nospam@nspam.com> writes:

One problem you will find is that examples are either contrived (the
algorithm is simpler to write some other way) or rather complex. The
most useful uses of recursion are with structures that are logically
nested -- the structure itself is recursive -- like binary trees.

One example this is not too contrived in this function to print a
number in decimal. iprint handles the special cases and then hands
off to the recursive auxiliary function.

#include <stdlib.h>
#include <stdio.h>

void aux_iprint(int n)
{
if (n > 0) {
aux_iprint(n/10);
putchar('0' + n % 10);
}
}

void iprint(int n)
{
if (n < 0) {
putchar('-');
aux_iprint(-n);
}
else if (n == 0)
putchar('0');
else aux_iprint(n);
}

int main(int argc, char *argv[])
{
while (--argc) {
int n = atoi(*++argv);
printf("Arg=%s itoa(%d) => ", *argv, n);
iprint(n);
printf("\n");
}
return 0;
}


Another example I rather like is this function to tell if a number is
a palindrome in a particular base although it uses very similar ideas
and as such shows very little new:

int pal_aux(int n, int r, int b)
{
return n == 0 ? r : pal_aux(n / b, r * b + n % b, b);
}

int is_pal_in(int n, int b)
{
return pal_aux(n, 0, b) == n;
}

For example, is_pal_in(12321, 10) returns true, as does
is_pal_in(0x12321, 16).

If you'd like an exercise... Write a function with this prototype:

int count_ways(int amount, int n, int *coins);

that returns the number of ways to make up the amount of money in the
first argument, given the array of 'n' coin values. For example,

int coins[] = {1, 5, 10, 25, 50};
count_ways(100, 5, coins) == 292

and for UK readers:

int coins[] = {1, 2, 5, 10, 20, 50, 100};
count_ways(100, 7, coins) == 4563

--
Ben.

Ben Bacarisse said:

<snip>
You will also need to add 200 to that mix. Yes, we have a two-pound coin.
There are also dark rumours of a five-pound coin, but those have been
going on for years, without my ever actually seeing one in my change.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

On Jun 25, 1:35*pm, "Bill Cunningham" <nos...@nspam.com> wrote:
Here is a real life example of a recursive function that is fairly
small and easy to understand. Pay special attention to intro_sort(),
and notice that intro_sort() calls intro_sort(). That is because it
is an implementation of quick sort that is being watched for bad
behavior (in which case we switch to heap sort).

/* Plauger's introspective sort function (CUJ Oct 99) */
#include <stdlib.h>
#include <string.h>

typedef int (*cmp) (const void *, const void *);

#define BUF_SIZE 512 /* > 0, auto buffer size */
#define SORT_MAX 32 /* > 1, cutover for insertion sort */

static void swap(char *qb, char *qe, size_t size)
{ /* swap elements *qb and *qe */
char buf[BUF_SIZE]; /* chunk to copy on swap */
size_t ms;

for (ms = size; 0 < ms { /* swap as many as possible */
size_t m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, qb, m);
memcpy(qb, qe, m);
memcpy(qe, buf, m);
ms -= m, qb += m, qe += m;
}
}

static void rotate(char *qb, char *qe, size_t size)
{ /* right rotate [*qb, *qe] one place
*/
char buf[BUF_SIZE]; /* chunk to copy on rotate */
size_t ms,
mtot = qe - qb + size;

for (ms = size; 0 < ms { /* rotate as many as possible */
size_t m = ms < sizeof(buf) ? ms : sizeof(buf);
memcpy(buf, qe + (size - m), m);
memmove(qb + m, qb, mtot - m);
memcpy(qb, buf, m);
ms -= m;
}
}

static void adjust_heap(char *qb, size_t h, size_t n, size_t size,
cmp * compare)
{ /* reheap item at h in heap (char
* qb[size])[n] */
size_t h0 = h;
size_t k = 2 * h + 2;
char *qh = qb + h * size;
char *qk = qb + k * size;
/* percolate hole out to larger/only child */
for (; k <= n; k = 2 * k + 2, qk = qb + k * size) {
if (k == n || (*compare) (qk, qk - size) < 0)
--k, qk -= size;
swap(qh, qk, size);
h = k, qh = qk;
}
/* percolate hole back in as far as h0 */
for (; h0 < h {
size_t i = (h - 1) / 2;
char *qi = qb + i * size;
if ((*compare) (qh, qi) <= 0)
break;
swap(qi, qh, size);
h = i, qh = qi;
}
}

static void intro_sort(char *qb, size_t n, size_t ideal, size_t
size, cmp * compare)
{
for (; 0 < ideal && SORT_MAX < n { /* quick sort with fat
pivot */
size_t m = n / 2;
char *qm = qb + m * size;
char *qf = qb,
*ql = qb + n * size;

if ((*compare) (qm, qf) < 0)
swap(qf, qm, size);
if ((*compare) (ql - size, qm) < 0)
swap(qm, ql - size, size);
if ((*compare) (qm, qf) < 0)
swap(qf, qm, size);

for (;; qf += size) { /* partition about pivot value */
for (; qf < ql && (*compare) (qf, qm) <= 0; qf += size);
for (; qb < ql && (*compare) (qm, ql -= size) <= 0;
if (ql <= qf)
break;

swap(qf, ql, size);
if (qm == qf)
qm = ql;
else if (qm == ql)
qm = qf;
}
ideal /= 2, ideal += ideal / 2;
m = (ql - qb) / size + 1;
n -= (qf - qb) / size;
if (m <= n)
intro_sort(qb, m, ideal, size, compare), qb = qf;
else
intro_sort(qf, n, ideal, size, compare), n = m;
}

if (SORT_MAX < n) { /* heap sort */
size_t h;
char *qe;
for (h = n / 2; 0 < h
adjust_heap(qb, --h, n, size, compare);
/* pop largest item to (shrinking) end */
for (qe = qb + n * size; 1 < n {
swap(qb, qe -= size, size);
adjust_heap(qb, 0, --n, size, compare);
}
} else if (1 < n) { /* insertion sort */
char *qm;
/* percolate back elements [2, n) */
for (qm = qb; 0 < --n {
qm += size;
if ((*compare) (qm, qb) < 0)
rotate(qb, qm, size);
else { /* scan backwards for insertion point */
char *qx = qm,
*qx0 = qm;
for (; (*compare) (qm, qx0 -= size) < 0; qx = qx0);
if (qx != qm)
rotate(qx, qm, size);
}
}
}
}

void qsortI(void *base, size_t n, size_t size, cmp * compare)
{ /* sort (char base[size])[n] using introsort */
intro_sort((char *)base, n, n, size, compare);
}

On Jun 25, 2:35 pm, "Bill Cunningham" <nos...@nspam.com> wrote:
void f()
{
f();
}

is the simplest example of a recursive function. But it will just fill
the
stack until the computer crashes (although a good O/S will catch it
before it brings the whole system down.).

Generally, a recursive function is one that calls itself, even if
indirectly.

An example that will not crash, at least for a sufficiently small
argument:

unsigned int f(unsigned int n)
{
if(n == 0) return(n);
else return(f(n - 1) + n);
}

which just adds up the integers from 1 to n.

An example of _indirect_ recursion, although crashing:

void g(); /* prototype */

void f()
{
g();
}

void g()
{
f();
}

Get the drift?

Bill Cunningham wrote:
Exercise 3-4 in K&R2, is itoa.
Here's a recursive version of itoa,
in the C language proper:

void itoa(int n, char *s);
static char *utoa_plus_zero(unsigned n, char *s);
static char *utoa_plus_one(unsigned n, char *s);

void itoa(int n, char *s)
{
if (0 > n) {
*s++ = '-';
*utoa_plus_one(-(n + 1), s) = '\0';
} else {
*utoa_plus_zero(n, s) = '\0';
}
}

static char *utoa_plus_zero(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (tenth != 0) {
s = utoa_plus_zero(tenth, s);
}
*s = (char)(digit + '0');
return s + 1;
}

static char *utoa_plus_one(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (digit == 9) {
if (tenth != 0) {
s = utoa_plus_one(tenth, s);
} else {
*s++ = '1';
}
*s = '0';
} else {
if (tenth != 0) {
s = utoa_plus_zero(tenth, s);
}
*s = (char)(digit + '1');
}
return s + 1;
}

--
pete

pete <pfiland@mindspring.com> writes:

Cunning way to avoid the overflow problem (makes it a bit mysterious
for a learner) but I suspect there is a neater way since we are using
recursion:

static char *aux_itoa(unsigned int n, char *s)
{
if (n > 0) {
s = aux_itoa(n / 10, s);
*s++ = '0' + n % 10;
}
return s;
}

void itoa(int n, char *s)
{
if (n == 0)
*s++ = '0';
else if (n < 0) {
*s = '-';
s = aux_itoa(-(n / 10), s + 1);
*s++ = '0' + (-(n + 10)) % 10;
}
else s = aux_itoa(n, s);
*s = 0;
}

--
Ben.

user923005 wrote:
typedef int (cmp) (const void *, const void *);

There's too many asterisks in the posted code.
That's the easiest one to remove.

I'm impressed by how often I see the wrong choice of operators
used at this point in this algorithm.
It should be (<) instead of (<=).
(<) gives a more evenly split partition,
and that makes a much bigger difference than saving a swap.
It's like nobody reads Knuth.

http://www.mindspring.com/~pfilandr/C/e_driver/

/* BEGIN e_driver.c program output */

Timing 6 different sorting functions.
Sorting arrays of N number of elements,
in 3 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N sssort h_sort qisort qrsort qsortI m_sort
1999998 3.609000 4.156000 1.453000 1.499000 2.202000 1.844000
1999999 3.624000 4.187000 1.453000 1.484000 2.187000 1.843000
Total times:
sssort: 7.233000 qsort interface, Sedgewick Shellsort
h_sort: 8.343000 qsort interface, heapsort, down and up
qisort: 2.906000 qsort interface, center pivot introspective
qrsort: 2.983000 qsort interface, random pivot introspective
qsortI: 4.389000 Plauger's introspective (CUJ Oct 99)
m_sort: 3.687000 qsort interface, stable merge, TOO_SMALL is 10

Distribution #2: Ramp, Drives center pivot qsorts, quadratic
N sssort h_sort qisort qrsort qsortI m_sort
1999998 1.250000 2.015000 3.640000 1.203000 6.468000 0.937000
1999999 1.250000 2.016000 3.610000 1.267000 6.516000 0.938000
Total times:
sssort: 2.500000 qsort interface, Sedgewick Shellsort
h_sort: 4.031000 qsort interface, heapsort, down and up
qisort: 7.250000 qsort interface, center pivot introspective
qrsort: 2.470000 qsort interface, random pivot introspective
qsortI: 12.984000 Plauger's introspective (CUJ Oct 99)
m_sort: 1.875000 qsort interface, stable merge, TOO_SMALL is 10

Distribution #3: Two values, Some qsorts choke on this
N sssort h_sort qisort qrsort qsortI m_sort
1999998 0.891000 1.608000 1.093000 1.046000 7.656000 0.969000
1999999 0.891000 1.610000 1.078000 1.047000 7.688000 0.985000
Total times:
sssort: 1.782000 qsort interface, Sedgewick Shellsort
h_sort: 3.218000 qsort interface, heapsort, down and up
qisort: 2.171000 qsort interface, center pivot introspective
qrsort: 2.093000 qsort interface, random pivot introspective
qsortI: 15.344000 Plauger's introspective (CUJ Oct 99)
m_sort: 1.954000 qsort interface, stable merge, TOO_SMALL is 10

/* END e_driver.c program output */

When the (<=) operators are replaced with (<),
then Distribution #3 looks like this:

Distribution #3: Two values, Some qsorts choke on this
N sssort h_sort qisort qrsort qsortI m_sort
1999998 0.891000 1.610000 1.094000 1.047000 2.188000 0.969000
1999999 0.890000 1.609000 1.093000 1.047000 2.218000 0.984000
Total times:
sssort: 1.781000 qsort interface, Sedgewick Shellsort
h_sort: 3.219000 qsort interface, heapsort, down and up
qisort: 2.187000 qsort interface, center pivot introspective
qrsort: 2.094000 qsort interface, random pivot introspective
qsortI: 4.406000 Plauger's introspective (CUJ Oct 99)
m_sort: 1.953000 qsort interface, stable merge, TOO_SMALL is 10

--
pete

pete wrote:
That makes it look like I'm trying to show that qsortI is slow,
which is not the case. The other tested functions are biased towards
sorting arrays of small objects.

/* BEGIN e_driver.c program output */

Timing 6 different sorting functions.
Sorting arrays of N number of elements,
in 3 different distributions.
The elements are of type struct { char array[50]; d_type data;}.
sizeof (struct { char array[50]; d_type data;}) is 64.
The times shown are in seconds.

Distribution #1: Shuffled
N sssort h_sort qisort qrsort qsortI m_sort
199998 2.109000 1.750000 0.641000 0.672000 0.609000 1.469000
199999 2.077000 1.750000 0.640000 0.671000 0.593000 1.437000
Total times:
sssort: 4.186000 qsort interface, Sedgewick Shellsort
h_sort: 3.500000 qsort interface, heapsort, down and up
qisort: 1.281000 qsort interface, center pivot introspective
qrsort: 1.343000 qsort interface, random pivot introspective
qsortI: 1.202000 Plauger's introspective (CUJ Oct 99)
m_sort: 2.906000 qsort interface, stable merge, TOO_SMALL is 5

Distribution #2: Ramp, Drives center pivot qsorts, quadratic
N sssort h_sort qisort qrsort qsortI m_sort
199998 0.827000 1.328000 1.577000 0.641000 1.374000 0.921000
199999 0.828000 1.328000 1.593000 0.640000 1.390000 0.922000
Total times:
sssort: 1.655000 qsort interface, Sedgewick Shellsort
h_sort: 2.656000 qsort interface, heapsort, down and up
qisort: 3.170000 qsort interface, center pivot introspective
qrsort: 1.281000 qsort interface, random pivot introspective
qsortI: 2.764000 Plauger's introspective (CUJ Oct 99)
m_sort: 1.843000 qsort interface, stable merge, TOO_SMALL is 5

Distribution #3: Two values, Some qsorts choke on this
N sssort h_sort qisort qrsort qsortI m_sort
199998 0.344000 1.235000 0.813000 0.751000 1.501000 0.844000
199999 0.344000 1.235000 0.813000 0.766000 1.500000 0.845000
Total times:
sssort: 0.688000 qsort interface, Sedgewick Shellsort
h_sort: 2.470000 qsort interface, heapsort, down and up
qisort: 1.626000 qsort interface, center pivot introspective
qrsort: 1.517000 qsort interface, random pivot introspective
qsortI: 3.001000 Plauger's introspective (CUJ Oct 99)
m_sort: 1.689000 qsort interface, stable merge, TOO_SMALL is 5

/* END e_driver.c program output */


When the (<=) operators are replaced with (<),
then Distribution #3 looks like this:

Distribution #3: Two values, Some qsorts choke on this
N sssort h_sort qisort qrsort qsortI m_sort
199998 0.359000 1.281000 0.843000 0.780000 0.765000 0.906000
199999 0.359000 1.312000 0.858000 0.781000 0.750000 0.874000
Total times:
sssort: 0.718000 qsort interface, Sedgewick Shellsort
h_sort: 2.593000 qsort interface, heapsort, down and up
qisort: 1.701000 qsort interface, center pivot introspective
qrsort: 1.561000 qsort interface, random pivot introspective
qsortI: 1.515000 Plauger's introspective (CUJ Oct 99)
m_sort: 1.780000 qsort interface, stable merge, TOO_SMALL is 5

--
pete

"Richard Heathfield" <rjh@see.sig.invalid> wrote in message
news:L-6dnZLeJPeEuf7VnZ2dneKdnZydnZ2d@bt.com...
That's interesting too. Another question (really). How many shillings in
a pound sterling? 100 pence I know, but not shilling.

Bill

Bill Cunningham said:

There are twenty shillings in a pound, and twelve pennies in a shilling,
which means that there are 240 pennies in a pound. Since, as you rightly
point out and as everyone knows, there are 100 pennies in a pound, the
obvious conclusion is that there are 2.4 pennies in a penny, which of
course means in turn that there are only 0.4166r pennies in a penny.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

"Richard Heathfield" <rjh@see.sig.invalid> wrote in message
newss2dnVxBKf7gqPjVnZ2dneKdnZydnZ2d@bt.com...


Bill

On Fri, 27 Jun 2008 18:50:45 +0000
Richard Heathfield <rjh@see.sig.invalid> wrote:

Is this the time to mention farthings, crowns, tanners and guineas ?

--
C:>WIN | Directable Mirror Arrays
The computer obeys and wins. | A better way to focus the sun
You lose and Bill collects. | licences available see
| http://www.sohara.org/

Steve O'Hara-Smith said:

Not to mention half-crowns, florins and thruppenny bits.

Oh, and groats.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

"Bill Cunningham" <nospam@nspam.com> writes:

What mistake? I see no mistake. English is not maths. In English it
is perfectly possible for there to be 100 Xs in a Y *and* 240 Xs in a
Y -- it just means that either the word "X" or the word "Y" has more
than one meaning.

I don't know what Richard Heathfield's point was, but I don't think he
was pointing out a mistake.

--
Ben.

Ben Bacarisse said:

You are right not to think so, for the thing you weren't thinking I was
doing was indeed not what I was doing; that is, I was not pointing out a
mistake. I'm not sure that I had a point, exactly - I was just answering
his question, and at the same time adding a little Imperial/metric spin
for the heck of it.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999