tobold.org

correct • elegant • free

△ Comp.lang.c △

◅ also for math

Expression to round up without branching ▻

function as parameter

In article <7mktv9$489$1@elf.bsdi.com>, Chris Torek <torek@elf.bsdi.com> wrote:
>For example, imagine we have the function:
>
>   /* produce x**n, where n is a nonnegative integer */
>   double intpower(double x, int n) {
>           return n > 0 ? x * intpower(x, n - 1) : 1.0;
>   }
>
>written tail-recursively since this is so common in those other
>languages.

That's not tail-recursive, at least not in the sense that it can be
executed in constant space.  The problem is that you are using the value
of the recursive call, instead of just returning it.

Here's a properly tail-recursive version.


    double intpoweraux(double x, int n, double a) {
            return n > 0 ? intpoweraux(x, n - 1, a * x) : a;
    }

    double intpower(double x, int n) {
            return intpoweraux(x, n, 1.0);
    }

(The third argument of the auxiliary function is named for
"accumulator".  Some, probably most, of "those other languages" have
nested functions (à la Pascal).  Then this can be written so that
the auxiliary function is visible only to the main function, and the
argument `x', which never changes, does not need to be passed to the
auxiliary.)

`gcc -O2' is able to eliminate the recursive call in this version.

Tim.
--
Tim Goodwin   | "You don't need to do drugs in order to
University of | think that the government's policies are
Leicester, UK | stupid and dangerous." -- David Bancroft

Original headers:

From: tjg@ltpcg.star.le.ac.uk (Tim J Goodwin)
Newsgroups: comp.lang.c
Subject: Re: function as parameter
Date: 16 Jul 1999 15:07:46 +0100
Organization: University of Leicester, UK
Message-ID: <7mnec8$jh7$1@ltpcg.star.le.ac.uk>
References: <378DB64D.230EDE4F@brainwork.at> <378DCC6F.41A62C7A@brainwork.at>
  <932047860snz@genesis.demon.co.uk> <7mktv9$489$1@elf.bsdi.com>

△ Comp.lang.c △

◅ also for math

Expression to round up without branching ▻