# [Q]: Recursion help

4 views

### Dirt

Jan 21, 2000, 3:00:00 AM1/21/00
to
Hiya,
I have to write a recursive function which calculates a number to
an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
the lisp multiplication function. I started to write this, code below
(yes it doesnt work) but before I fix my code. Is this possible to do
without using the Lisp minus function as well?

Thanks,
Dirt

( defun ex ( b e )

( cond

( ( eq b 0 ) 0 ) ; Base is 0 all done
( ( eq e 0 ) 1 ) ; Answer is 1
( ( eq b 1 ) b ) ; All done
( ( eq e 1 ) b ) ; All done
( ( ex ( * b b ) ( - e 1 ) ) )

( t nil )
)

)

### Dirt

Jan 21, 2000, 3:00:00 AM1/21/00
to
Thnaks Barry,
I think I have my code corrected;

( defun ex ( b e )

( cond

( ( eq b 0 ) 0 ) ; Base is 0 all done
( ( eq e 0 ) 1 ) ; Answer is 1
( ( eq b 1 ) b ) ; All done
( ( eq e 1 ) b ) ; All done

( t ( * b ( ex b ( - e 1 ) ) ) ) ; Call again

( t nil )
)

)

However, as instructed in my homework, I am to do this only by using
the LISP multiplication function and recursion. In my code, I use the
minus function. I can't think of a way to do this without using minus
to keep track of the current iteration. Can this be done as requested?

Thanks,
Dirt

On Sat, 22 Jan 2000 00:33:01 GMT, Barry Margolin
<bar...@bbnplanet.com> wrote:

>In article <u4th8sodb1o55fmcq...@4ax.com>,

>Dirt <pi...@inam3.com> wrote:
>>Hiya,
>> I have to write a recursive function which calculates a number to
>>an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
>>the lisp multiplication function. I started to write this, code below
>>(yes it doesnt work) but before I fix my code. Is this possible to do
>>without using the Lisp minus function as well?
>

>You have two problems:
>
>1) The recursive clause of the cond should be the "t" clause.
>
>2) You have a math error: ex(b, e) = b*ex(b, e-1), not ex(b*b, e-1)

### Robert Monfera

Jan 21, 2000, 3:00:00 AM1/21/00
to

Hi Dirt,

Here is a quote from the Hyperspec. If you find where it is (besides my
hard drive), you'll find references to things you may want to consider.

"An implementation is permitted to make 'copies' of characters and
numbers at any time. The effect is that Common Lisp makes no guarantee
that eq is true even when both its arguments are 'the same thing' if
that thing is a character or number."

Here's how it looks like with common Lisp spacing:

(defun ex (base exponent)
(cond ((eq base 0) 0)
((eq exponent 0) 1)
((eq base 1) base)
((eq exponent 1) base)
(t (* base (ex base (- exponent 1))))
(t nil)))

This is only formatting and naming - I haven't changed functions. Other
than these, isn't the last T condition redundant?

Also, I guess the assignment specifies it is only supposed to work with
positive integers as exponents - you could check it and signal an error
with this: (error "Exponent is not a positive integer.")

After these all, you can tell your teacher there is zero error in it :-)

Robert

### Dirt

Jan 21, 2000, 3:00:00 AM1/21/00
to
>..., isn't the last T condition redundant?

Yes, my mistake. The last t is redundant. I forgot to take it out as
it was part of a condition checking for valid numbers, however, it is
now assumed valid numbers are entered.

Dirt

On Fri, 21 Jan 2000 22:32:30 -0500, Robert Monfera <mon...@fisec.com>
wrote:

### Barry Margolin

Jan 22, 2000, 3:00:00 AM1/22/00
to
In article <u4th8sodb1o55fmcq...@4ax.com>,
Dirt <pi...@inam3.com> wrote:
>Hiya,
> I have to write a recursive function which calculates a number to
>an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
>the lisp multiplication function. I started to write this, code below
>(yes it doesnt work) but before I fix my code. Is this possible to do
>without using the Lisp minus function as well?

You have two problems:

1) The recursive clause of the cond should be the "t" clause.

2) You have a math error: ex(b, e) = b*ex(b, e-1), not ex(b*b, e-1)

>
>Thanks,
> Dirt
>

>( defun ex ( b e )
>
> ( cond
>
> ( ( eq b 0 ) 0 ) ; Base is 0 all done
> ( ( eq e 0 ) 1 ) ; Answer is 1
> ( ( eq b 1 ) b ) ; All done
> ( ( eq e 1 ) b ) ; All done

> ( ( ex ( * b b ) ( - e 1 ) ) )

>
> ( t nil )
> )
>
>)

--
Barry Margolin, bar...@bbnplanet.com
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

### dauc...@hotmail.com

Jan 22, 2000, 3:00:00 AM1/22/00
to
In article <d81i8sc43er38ah4l...@4ax.com>,
Dirt <pi...@inam3.com> wrote:

>
> However, as instructed in my homework, I am to do this only by using
> the LISP multiplication function and recursion. In my code, I use the
> minus function. I can't think of a way to do this without using minus
> to keep track of the current iteration. Can this be done as requested?

Dear Dirt, it's worse than you think: you're also using the cond and
instructions you were given were not correct). Turn it in and don't
worry about it, or, if you wish to stir up some stuff, us CL's loop
facility and teach your professor what's happened with Lisp in the last
15 or so years. Ask some questions about covariance and the Meta-
Object Protocol while you're at it.

<rant>
I hope this is an extra-credit/optional problem. I hate it when profs
say, "You can only use X, Y, and Z of the language." Doesn't the world
impose enough limits without us throwing some extra ones on top?
</rant>

Sincerely,
Douglas M. Auclair

Sent via Deja.com http://www.deja.com/

### Stig Hemmer

Jan 22, 2000, 3:00:00 AM1/22/00
to
Dirt <pi...@inam3.com> writes:
> Is this possible to do
> without using the Lisp minus function as well?

Well, there are two functions 1- and DECF that you could use, but I
doubt that is what you teacher had in mind.

What she was probably thinking was to count upwards using + instead of
downwards using -.

You will have to remember how far you should count by passing an extra
parameter to the recursive function. This means that your recursive
function cannot be EX, but some other function, e.g. EX-HELPER.

You should also take note of what Robert Montfera was saying about
comparing numbers using EQ. It will work perfectly well on most Lisp
implementations, but isn't _guaranteed_ to do so.

Numbers are best compared using the function =. (Common Lisp has many
different equality/equivalence testing functions. Often you can use
more than one. In this case, EQL, EQUAL and EQUALP would all have
worked, but = is still the predicate of choice for numbers)

Stig Hemmer,

### Dirt

Jan 22, 2000, 3:00:00 AM1/22/00
to

>You should also take note of what Robert Montfera was saying about
>comparing numbers using EQ. It will work perfectly well on most Lisp
>implementations, but isn't _guaranteed_ to do so.

Ok, Ill change it over to =.

>Numbers are best compared using the function =. (Common Lisp has many
>different equality/equivalence testing functions. Often you can use
>more than one. In this case, EQL, EQUAL and EQUALP would all have
>worked, but = is still the predicate of choice for numbers)

So, it is safe to recommend to my professor that we should be taught
to use '=' to compare numbers rather than 'eq'?

Thanks,
Dirt

### Marco Antoniotti

Jan 22, 2000, 3:00:00 AM1/22/00
to

Dirt <pi...@inam3.com> writes:

> >You should also take note of what Robert Montfera was saying about
> >comparing numbers using EQ. It will work perfectly well on most Lisp
> >implementations, but isn't _guaranteed_ to do so.
>
> Ok, Ill change it over to =.

On the other end EQL works for numbers of the same type.

> >Numbers are best compared using the function =. (Common Lisp has many
> >different equality/equivalence testing functions. Often you can use
> >more than one. In this case, EQL, EQUAL and EQUALP would all have
> >worked, but = is still the predicate of choice for numbers)
>
> So, it is safe to recommend to my professor that we should be taught
> to use '=' to compare numbers rather than 'eq'?

Yep. As you should be thought about FIRST and REST instead of CAR and
CDR.

Cheers

--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26

### Robert Monfera

Jan 22, 2000, 3:00:00 AM1/22/00
to

Dirt wrote:

> [...] we should be taught

> to use '=' to compare numbers rather than 'eq'?

Yes. As Stig said, eq works on most implementations - provided both
numbers map into one 32-bit word. This is usually true for fixnums
(check most-positive-fixnum and most-negative-fixnum) and maybe other
32-bit data in an optimized setting. This is an accidental and
non-guaranteed side effect of eq working simply by comparing 2 32-bit
values (which are expected to be addresses), because two immediate
values (usually fixnums) that = will have the same bits.

Here's something to try for you with your implementation:

> (eq 7391827918273091 7391827918273091)
NIL
> (eq 2.0 2.0)
NIL
>

Robert

### Dirt

Jan 22, 2000, 3:00:00 AM1/22/00
to
<snip>

>
>Here's something to try for you with your implementation:
>
>> (eq 7391827918273091 7391827918273091)
>NIL
>> (eq 2.0 2.0)
>NIL
>>

Yea, I tried that out and it didn't work just like you said. Thanks
for pointing this out to me guys.

Dirt

Jan 22, 2000, 3:00:00 AM1/22/00
to
* Dirt wrote:

> So, it is safe to recommend to my professor that we should be taught

> to use '=' to compare numbers rather than 'eq'?

Yes! in fact EQ may not work for numbers:

(eq (expt 2 100) (expt 2 100)) -> nil

on all the implementations I've tried (Allegro, genera, gcl, clisp).

--tim

### Janos Blazi

Jan 22, 2000, 3:00:00 AM1/22/00
to
I am sure the wording of the problem is deficient. Probably the intention
was that you must not use LISP's exponentiation as the problem is trivial
then.

J.B.

<dauc...@hotmail.com> schrieb in im Newsbeitrag:
86b9sm\$5g3\$1...@nnrp1.deja.com...

-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
------== Over 73,000 Newsgroups - Including Dedicated Binaries Servers ==-----

### Andreas Eder

Jan 22, 2000, 3:00:00 AM1/22/00
to
Two things:
a) you should reverse the first two clause in your cond

>( ( eq b 0 ) 0 ) ; Base is 0 all done
> ( ( eq e 0 ) 1 ) ; Answer is 1
to
( ( eq e 0 ) 1 ) ; Answer is 1
( ( eq b 0 ) 0 ) ; Base is 0 all done
because 0^0 = 1 = (ex 0 0) as well.

b) iinstead of counting down from n to 0 you could just count up
and thus avoid the minus

--
Wherever I lay my .emacs, there愀 my \$HOME.

### Dirt

Jan 22, 2000, 3:00:00 AM1/22/00
to
On 22 Jan 2000 09:31:37 +0100, Andreas Eder <a...@elgin.eder.de> wrote:

>Two things:
>a) you should reverse the first two clause in your cond
> >( ( eq b 0 ) 0 ) ; Base is 0 all done
> > ( ( eq e 0 ) 1 ) ; Answer is 1
>to
> ( ( eq e 0 ) 1 ) ; Answer is 1
> ( ( eq b 0 ) 0 ) ; Base is 0 all done
>because 0^0 = 1 = (ex 0 0) as well.
>
>b) iinstead of counting down from n to 0 you could just count up
>and thus avoid the minus

Im sorry. This just isn't clicking. If I count up, wont I have to use
the '+' function then?

### Andrew Cooke

Jan 23, 2000, 3:00:00 AM1/23/00
to
In article <u4th8sodb1o55fmcq...@4ax.com>,
Dirt <pi...@inam3.com> wrote:
> Hiya,
> I have to write a recursive function which calculates a number to
> an exponent such as (ex 2 3 ). (answer 8 ) I am only allowed to use
> the lisp multiplication function. I started to write this, code below
> (yes it doesnt work) but before I fix my code. Is this possible to do

> without using the Lisp minus function as well?

Assuming that you can use other operators (just not exponentiation) (as
others on this thread have argued), there's probably a more efficient
(less multiplication - I have no idea what a sufficiently large value of
n is required for it to run more quickly) solution that I haven't seen
mentioned:

x^n = (x^n/2) * (x^n/2)

when n is even (and, of course, you only calculate x^n/2 once.

When n is odd you can reduce it to the even case by taking out a factor
of x.

Obviously, this assumes n is a positive integer (as you are doing

Andrew

### Erik Naggum

Jan 23, 2000, 3:00:00 AM1/23/00
to
* Dirt <pi...@inam3.com>

| So, it is safe to recommend to my professor that we should be taught
| to use '=' to compare numbers rather than 'eq'?

your professor should never teach EQ in the first place. EQ should be
discovered by good students on their own. novices should always use EQL
for typeless object comparison, and try not to think about EQ.

= signals an error for non-numbers. this is often a major pain. EQL
yields false if the objects are of different types. this can sometimes
be exactly what you want. = yields true for _numeric_ equality, which
can sometimes be very expensive to compute, but is often worth the cost,
except when you control the types of both objects and you would have to
be a real klutz to introduce that cost wantonly. therefore, EQL will
tell you about suboptimal programming practices if it yields false on two
numbers that appear "alike", and this fact alone will teach most students
better programming practices.

#:Erik

### Erik Naggum

Jan 23, 2000, 3:00:00 AM1/23/00
to
* Dirt <pi...@inam3.com>

note that (EQL 2.0 2.0) => T, but (EQL 2 2.0) => NIL.

#:Erik

Jan 23, 2000, 3:00:00 AM1/23/00
to
* Andrew Cooke wrote:
> In article <u4th8sodb1o55fmcq...@4ax.com>,

> x^n = (x^n/2) * (x^n/2)

And indeed this gives you a way of doing the calculation without using
- (or / or ODDP). You do need ASH, LOGBITP, and * though. Whether
that's the solution the person was looking for I don't know!

--tim

### Dirt

Jan 23, 2000, 3:00:00 AM1/23/00
to
Ill let you guys know what my professor was thinking tomorrow. This is
our first assignment with LISP so I highly doubt that using

"ASH, LOGBITP, and *"

is the intended solution. ( I Hope not at least) Like others have
suggested in this thread, I think the point was to make it recursive
and NOT use the exponent function.

Dirt

Jan 24, 2000, 3:00:00 AM1/24/00
to
* Dirt wrote:
> Ill let you guys know what my professor was thinking tomorrow. This is
> our first assignment with LISP so I highly doubt that using

> "ASH, LOGBITP, and *"

> is the intended solution. ( I Hope not at least) Like others have
> suggested in this thread, I think the point was to make it recursive
> and NOT use the exponent function.

For what it's worth, the too-clever solution is:

(defun x-to-the-n (x n)
(declare (type (integer 0) n)
(type number x))
(if (= n 1)
x
(let ((half (x-to-the-n x (ash n -1))))
(if (logbitp 0 n)
(* half half x)
(* half half)))))

### Stig Hemmer

Jan 24, 2000, 3:00:00 AM1/24/00
to
Another "too clever" solution: [not recursive]

(defun ex (b e)
(apply #'* (make-list e :initial-element b)))

What this does is to make a list of e elements, each element being b.
Then it multiplies all these numbers together.

E.g. (ex 3 4) --> (apply #'* (3 3 3 3)) --> (* 3 3 3 3) --> 81

Note that (*) returns 1, so this code works for e=0.

#'* is short-hand for "the function *" as opposed to "the varable *".

### Barry Margolin

Jan 24, 2000, 3:00:00 AM1/24/00
to
In article <ekv7lgz...@epoksy.pvv.ntnu.no>,

Stig Hemmer <st...@pvv.ntnu.no> wrote:
>Another "too clever" solution: [not recursive]

Since it's not recursive, it clearly doesn't fit the parameters of the
homework assignment.

>(defun ex (b e)
> (apply #'* (make-list e :initial-element b)))

It would be better to use REDUCE than APPLY. Your solution may not work
when E > CALL-ARGUMENTS-LIMIT.

### Dirt

Jan 24, 2000, 3:00:00 AM1/24/00
to
previous post with my corrected function is acceptable. She just
didn't want us to use lisp's exponent function. That is excusable to
me, however, I am new to lisp and usually follow instructions to a T
when I am new to something. And this can lead to confusion in some
cases.

I also mentioned to my professor that using "eq" to compare two
numbers wasn't such a good idea. she admitted that she may have wrote
the incorrect thing on the board to me in private, however, she never
brought it up in class to note the correction that should be made = (

Thanks for all the help,
Dirt

On 24 Jan 2000 19:20:34 +0100, Stig Hemmer <st...@pvv.ntnu.no> wrote:

>Another "too clever" solution: [not recursive]
>

>(defun ex (b e)
> (apply #'* (make-list e :initial-element b)))
>

### Robert Posey

Jan 25, 2000, 3:00:00 AM1/25/00
to

Dirt wrote:
>
> <snip>

>
> >
> >Here's something to try for you with your implementation:
> >
> >> (eq 7391827918273091 7391827918273091)
> >NIL
> >> (eq 2.0 2.0)
> >NIL
> >>
>
> Yea, I tried that out and it didn't work just like you said. Thanks
> for pointing this out to me guys.
>

> Dirt

You might try and write a version of what I did to help me begin to
learn the difference between 'eq 'eql 'equal and '=. There are definite
differences, and '= at least will blow up if you give it anything that
is not a number in Halequin Lispworks.

(defun equal_test ( x y)
(format T "Input Is ~A ~A ~%" `x `y)
(format T "X = ~A Y= ~A ~% ~%" x y)

(if (eq x y)
(format T "(eq x y) Returns TRUE or T ~% ~%")
(format T "(eq x y) Returns FALSE or NIL ~% ~%")
)

(if (eql x y)
(format T "(eql x y) Returns TRUE or T ~% ~%")
(format T "(eql x y) Returns FALSE or NIL ~%~%")
)

(if (equal x y)
(format T "(equal x y) Returns TRUE or T ~% ~%")
(format T "(equal x y) Returns FALSE or NIL ~% ~%")
)
(if (and (numberp x) (numberp y))
(if (= x y)
(format T "(= x y) Returns TRUE or T ~% ~%")
(format T "(= x y) Returns FALSE or NIL ~% ~% ~%")
)
(block MY_BLOCK
(format T "(= x y) ERROR ~% ")
(format T "One of the inputs is not a number, = takes numbers only ~%~%~%")
)
)
)

Then run a bunch of different test values like

(setf x 5.0)

(EQUAL_TEST x 5.0)

(EQUAL_TEST x 'x)

and so on.

It works here, but I won't promise there aren't mistakes.

Muddy

### Christopher R. Barry

Jan 27, 2000, 3:00:00 AM1/27/00
to
Dirt <pi...@inam3.com> writes:

> Hiya,
> I have to write a recursive function which calculates a number to
> an exponent such as (ex 2 3 ). (answer 8 )

I don't think anyone yet posted the trivial solution. x^n may be
defined recursively as:

n
x = x (when x = 1)

n n-1
x = x * x (when x > 1)

Thus,

(defun rec-expt (x n)

(if (= n 1)
x

(* x (rec-expt x (1- n)))))

Christopher
[Still playing catchup.]

### Christopher R. Barry

Jan 27, 2000, 3:00:00 AM1/27/00
to
cba...@2xtreme.net (Christopher R. Barry) writes:

> n
> x = x (when x = 1)

^

> n n-1
> x = x * x (when x > 1)

^

Those should of course be n instead of x. Why one minute after posting
that error suddenly flashed through my head instead of me catching it
immediately, we'll never know....

Christopher

### Barry Margolin

Jan 27, 2000, 3:00:00 AM1/27/00
to
In article <877lgvl...@2xtreme.net>,

Christopher R. Barry <cba...@2xtreme.net> wrote:
>I don't think anyone yet posted the trivial solution. x^n may be
>defined recursively as:

The original poster did so in his reply to my message on Friday.

> (defun rec-expt (x n)
> (if (= n 1)
> x
> (* x (rec-expt x (1- n)))))

Your function doesn't handle x^0 = 1. The original poster's revised code
does. Score 1 for the newbie!

### Coby Beck

Jan 27, 2000, 3:00:00 AM1/27/00
to
> > (defun rec-expt (x n)
> > (if (= n 1)
> > x
> > (* x (rec-expt x (1- n)))))
>
> Your function doesn't handle x^0 = 1. The original poster's revised code
> does. Score 1 for the newbie!
>

There are of course negative powers to be handled!

(defun rec-expt(base power)
(cond
((< power 0 ) (rec-expt (/ 1 base) (abs power)))
((= power 0) 1)
(t (* base (rec-expt base (1- power))))))

I'll leave it to someone else to handle non-integer powers (translation: i
don't know how... :-(

Coby

### Thomas A. Russ

Jan 31, 2000, 3:00:00 AM1/31/00
to
"Coby Beck" <cb...@mercury.bc.ca> writes:

> I'll leave it to someone else to handle non-integer powers (translation: i
> don't know how... :-(

Well, I don't know how to handle the non-integer powers recursively, but
one method would use natural logs (and the EXP function, which might be
considered cheating...)

(defun non-integer-expt (b e)
(exp (* e (log b))))

--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu