Recursion is silly (if you can avoid it).

I recently draw attention to a toy lisp in Forth.
The example program was a scheme program that counts
how many changes in coins are possible for e.g. 100 dollarcent.
The lisp had to improved to be able to compile the program.
The improved version can hardly manage an input of 100 and takes
a noticable time, 200 and following fails.

A more sane program fills in a table where each entry is derived
from previous entries. A possibility to change for 100 cent is e.g.
adding 10 cent to the possibilities for 90 cent.
This is a kind of reversed dynamic programming.

In Forth it looks like.
\ --------------------- 8< ---------------------------
WANT VALUE
: _ 0 ; \ Don't care value
CREATE kind-of-coins 1 , 5 , 10 , 25 , 50 , 0 ,

_ VALUE limit
_ VALUE aap

\ One possibility to change 0 cent, others initially zero.
: init 1 , limit 0 DO 0 , LOOP ;

: aap[] CELLS aap + ;

\ Add possibilities for denomination to `aap
: add limit 1+ OVER DO I OVER - aap[] @ I aap[] +! LOOP DROP ;
: doit 1 ARG[] EVALUATE TO limit
HERE TO aap init
kind-of-coins BEGIN $@ DUP WHILE add REPEAT DROP
limit aap[] ? CR ;

\ --------------------- 8< ---------------------------
You may have not have to want VALUE.
$@ is another name for @+ / OUNT .
If you can't handle command line arguments, you can replace
`` 1 ARG[] EVALUATE '' with the limit you want.
Around 70 dollar you get overflow in 32 bit systems.
It is hard to measure speed in 32 bit systems,
suffice it to say that is certainly under 10 ms.

My forth (lina) is not the fastest, however

time coinsusa 1,000,000
666793341266850001
real 0m0.353s
user 0m0.281s
sys 0m0.029s

For reference this is the scheme program.
\ --------------------- 8< ---------------------------
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))

(display (count-change 100))
(newline)
\ --------------------- 8< ---------------------------

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

> Recursion is silly (if you can avoid it).

Not really.

Recursion is elegant — but actually isn't any
more efficient than iteration, and of course
it requires stack space.

And yes, most of the time (or always?) there
does exist iterative counterpart solution
--
Z.

albert@cherry.(none) (albert) writes:

> I recently draw attention to a toy lisp in Forth.
> The example program was a scheme program that counts
> how many changes in coins are possible for e.g. 100 dollarcent.

By the way, this is a well-known problem likely very well known by
everyone in this news group. The scheme-procedure you presented is from
section 1.2.2 in

Structure and Interpretation of Computer Programs
Gerald J. Sussman, Harold Abelson, Julie Sussman

> The lisp had to improved to be able to compile the program. The
> improved version can hardly manage an input of 100 and takes a
> noticable time, 200 and following fails.
>
> A more sane program fills in a table where each entry is derived
> from previous entries.

The scheme version you presented builds such a table --- it's called the
stack of execution. (Just another name for ``table''.)

zbigniew2011@gmail.com (LIT) writes:

>> Recursion is silly (if you can avoid it).
>
> Not really.
>
> Recursion is elegant — but actually isn't any
> more efficient than iteration, and of course
> it requires stack space.
>
> And yes, most of the time (or always?) there
> does exist iterative counterpart solution

What do you mean iterative? For instance, Gerald Sussman and Harold
Abelson classify as `iterative' the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.

albert@cherry.(none) (albert) writes:
> This is a kind of reversed dynamic programming.

That is usually called memoization.

> What do you mean iterative?

An iterative function is one that loops to
repeat some part of the code, and a recursive
function is one that calls itself again to
repeat the code
--
Z.

> What do you mean iterative?

An iterative function is one that loops
to repeat some part of the code, and
a recursive function is one that calls
itself again to repeat the code
--
Z.

none wrote:

> Recursion is silly (if you can avoid it).

> I recently draw attention to a toy lisp in Forth.
> The example program was a scheme program that counts
> how many changes in coins are possible for e.g. 100 dollarcent.
> The lisp had to improved to be able to compile the program.
> The improved version can hardly manage an input of 100 and takes
> a noticable time, 200 and following fails.

IOW educated brute force can beat elegant recursion.

You are right in a brutish

zbigniew2011@gmail.com (LIT) writes:

>> What do you mean iterative?
>
> An iterative function is one that loops to
> repeat some part of the code, and a recursive
> function is one that calls itself again to
> repeat the code

Such calling itself again is a form of going back to work on a similar
problem, which seems to fall under your definition of that which loops.

Paul Rubin <no.email@nospam.invalid> writes:
>> This is a kind of reversed dynamic programming.
> That is usually called memoization.

Added: in Scheme, it can be idiomatic to implement memoization using
force and delay. So for the coin problem you'd have a lookup table
indexed by the amount to be changed, and the sizes of coins available,
giving the number of ways to change that amount with those coins.

Each slot in the table would say something like (delay (cc amount coins))
where cc is a recursive function that would return a delayed sum of
the different table lookups corresponding to different breakdowns of
the amount. Finally, you would force the table entries for the amounts
1,2...100 or whatever.

I haven't tried this so I may be missing something, but the above
follows a common pattern.

Julieta Shem <jshem@yaxenu.org> writes:

> What do you mean iterative? For instance, Gerald Sussman and Harold
> Abelson classify as `iterative' the procedure
>
> (def (f n [acc 1])
> (if (= n 1)
> 1
> (f (dec n) (* acc n)))),
>
> which is self-referential.

Are you sure? IIRC they differentiate between programs and processes.
So your function would be a recursive program but it doesn't create a
recursive process (assumed the implementation is tail call optimized).

I admit that it is a long time since I read the book.

Regards

Paul Rubin <no.email@nospam.invalid> writes:
> I haven't tried this so I may be missing something, but the above
> follows a common pattern.

I still haven't worked out the details of the force/delay approach, but
here (at bottom) is a Scheme version that implements memoization using a
hash table by brute force. 100 cents and 200 cents take no perceptible
time.

I ran it with Guile 3.0 (compilation enabled) and got these results on a
small Hetzner VM (number of cents to be changed, result, cpu time in
seconds, and ram consumption in KB):

|---------+------------------------+-------+--------|
| amt | result | sec | KB |
|---------+------------------------+-------+--------|
| 100 | 293 | 0.01 | 9264 |
| 200 | 2728 | 0.01 | 9340 |
| 1000 | 2103596 | 0.01 | 10080 |
| 10000 | 139946140451 | 0.13 | 15176 |
| 100000 | 13398445413854501 | 1.25 | 67564 |
| 500000 | 41707305668679272501 | 5.76 | 293964 |
| 1000000 | 1333983445341383545001 | 15.24 | 580696 |
|---------+------------------------+-------+--------|

================================================================

(define (singleton? lst)
(and (not (null? lst))
(null? (cdr lst))))

(define allcoins '(1 5 10 25 50 100))

(define (cc amount coins)
(cond ((= amount 0) 1)
((< amount 0) 0)
((null? coins) 0)
((singleton? coins)
(if (= (remainder amount (car coins)) 0)
1
0))
(#t (+ (cc (- amount (car coins)) coins)
(cc amount (cdr coins))))))

(define (memoize f)
(define a (make-hash-table))
(define (g . args)
(let ((v (hash-ref a args)))
(if v v (hash-set! a args (apply f args)))))
g)

(set! cc (memoize cc))

(define amt (string->number (cadr (command-line))))

(display (cc amt allcoins))
(display "\n")

> 1000000 | 1333983445341383545001 | 15.24 | 580696

That is quite different from the result none showed.
| time coinsusa 1,000,000
| 666793341266850001
| real 0m0.353s

I guess you are computing something different?
The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

-marcel

mhx@iae.nl (mhx) writes:
> I guess you are computing something different?
> The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

Interesting, what values do you get for 100, 200, etc.? It could be
that my method is wrong. I just did it off the top of my head and may
have done something dumb.

On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
wrote:

>> Recursion is silly (if you can avoid it).
>
>Not really.
>
>Recursion is elegant — but actually isn't any
>more efficient than iteration, and of course
>it requires stack space.

Not necessarily. Scheme compilers actually are *required* to turn
self recursion into a loop (except in the case of a supported "debug"
mode).

I think some of the Lisps can do it also - at least with
(optimize (debug 0) (space 3))

>And yes, most of the time (or always?) there
>does exist iterative counterpart solution

Always. Given enough resources (which could be code or memory space),
any recursion can be turned into an equivalent loop, and vice versa.

mhx@iae.nl (mhx) writes:
> I guess you are computing something different?

Aha, one difference I notice is that Albert's code doesn't have a 100
cent coin. I included that because we have them in the US, though they
aren't used much except for in parking meters. They were introduced
partly for use in vending machines, but those now tend to have dollar
bill slots and sometimes also take credit cards.

Let me try again:

|---------+--------------------+-------+--------|
| 100 | 292 | 0.13 | 33644 |
| 200 | 2435 | 0.00 | 9412 |
| 1000 | 801451 | 0.01 | 9852 |
| 10000 | 6794128501 | 0.05 | 14316 |
| 100000 | 66793412685001 | 1.11 | 63904 |
| 500000 | 41682501983425001 | 6.07 | 240260 |
| 1000000 | 666793341266850001 | 10.67 | 475044 |
|---------+--------------------+-------+--------|

So we're getting the same results for 1000000 now, but my version is
still a lot slower. Maybe the memoization is not working right. Hmm.

On 2023-12-27, George Neuner <gneuner2@comcast.net> wrote:
> On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
> wrote:
>
>>> Recursion is silly (if you can avoid it).
>>
>>Not really.
>>
>>Recursion is elegant — but actually isn't any
>>more efficient than iteration, and of course
>>it requires stack space.
>
> Not necessarily. Scheme compilers actually are *required* to turn
> self recursion into a loop (except in the case of a supported "debug"
> mode).

Careful there: not all self-recursion is tail recursion!

For instance, the obvious way to write a recursive factorial fails
to be tail-recursive, but can be rewritten to tail from with
accumulator passing.

(I know you know all this, likely better than me, but `tis the
season to have your egg nogged.)

In article <pu8poi13a1m0lq1am4a2c4fpop5nro1emh@4ax.com>,
George Neuner <gneuner2@comcast.net> wrote:
>On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
>wrote:
>
>>> Recursion is silly (if you can avoid it).
>>
>>Not really.
>>
>>Recursion is elegant — but actually isn't any
>>more efficient than iteration, and of course
>>it requires stack space.
>
>Not necessarily. Scheme compilers actually are *required* to turn
>self recursion into a loop (except in the case of a supported "debug"
>mode).
>
>I think some of the Lisps can do it also - at least with
> (optimize (debug 0) (space 3))
>
>
>>And yes, most of the time (or always?) there
>>does exist iterative counterpart solution
>
>Always. Given enough resources (which could be code or memory space),
>any recursion can be turned into an equivalent loop, and vice versa.

In the Knuth TAOCP you cannot find recursive algorithms. They are
intended to run fast, and algorithms are specified with explicit
stacks. Of course the size of those stacks are specified.

Groetjes Albert
>
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <8734vn9uit.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>Paul Rubin <no.email@nospam.invalid> writes:
>> I haven't tried this so I may be missing something, but the above
>> follows a common pattern.
>
>I still haven't worked out the details of the force/delay approach, but
>here (at bottom) is a Scheme version that implements memoization using a
>hash table by brute force. 100 cents and 200 cents take no perceptible
>time.
>
>I ran it with Guile 3.0 (compilation enabled) and got these results on a
>small Hetzner VM (number of cents to be changed, result, cpu time in
>seconds, and ram consumption in KB):
>
> |---------+------------------------+-------+--------|
> | amt | result | sec | KB |
> |---------+------------------------+-------+--------|
> | 100 | 293 | 0.01 | 9264 |
> | 200 | 2728 | 0.01 | 9340 |
> | 1000 | 2103596 | 0.01 | 10080 |
> | 10000 | 139946140451 | 0.13 | 15176 |
> | 100000 | 13398445413854501 | 1.25 | 67564 |
> | 500000 | 41707305668679272501 | 5.76 | 293964 |
> | 1000000 | 1333983445341383545001 | 15.24 | 580696 |
> |---------+------------------------+-------+--------|
>
>================================================================
>
<SNIP>

Impressed. My answer for 1000000 is actually wrong
because I didn't know that there are 1 dollar coins.

Improving my program:

~/euler: time coinsusa 100000
13398445413854501

real 0m0.095s
user 0m0.079s
sys 0m0.001s

Memory footprint estimated 900 Kbyte.

I see that you go beyond 64 bit numbers and I cannot
calculate the million dollarcent challenge.
The timing and foot print are slightly less as a reward
for more analysis.
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <feea51c7336d6888f6d7b73e76cacebd@news.novabbs.com>,
mhx <mhx@iae.nl> wrote:
>> 1000000 | 1333983445341383545001 | 15.24 | 580696
>
>That is quite different from the result none showed.
>| time coinsusa 1,000,000
>| 666793341266850001
>| real 0m0.353s
>
>I guess you are computing something different?
>The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

Rubin is apparently knowledgeable about USA coins.
He corrected the coins table to contain 1 dollar coins. (What do I know.)
That spoils the benchmark effect.
Can you run the program again with 100 cent coins?
Maybe with 100,000 because now a million overflows 64 bit.

>
>-marcel
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

In article <87tto38djn.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>mhx@iae.nl (mhx) writes:
>> I guess you are computing something different?
>
>Aha, one difference I notice is that Albert's code doesn't have a 100
>cent coin. I included that because we have them in the US, though they
>aren't used much except for in parking meters. They were introduced
>partly for use in vending machines, but those now tend to have dollar
>bill slots and sometimes also take credit cards.
>
>Let me try again:
>
> |---------+--------------------+-------+--------|
> | 100 | 292 | 0.13 | 33644 |
> | 200 | 2435 | 0.00 | 9412 |
> | 1000 | 801451 | 0.01 | 9852 |
> | 10000 | 6794128501 | 0.05 | 14316 |
> | 100000 | 66793412685001 | 1.11 | 63904 |
> | 500000 | 41682501983425001 | 6.07 | 240260 |
> | 1000000 | 666793341266850001 | 10.67 | 475044 |
> |---------+--------------------+-------+--------|
>
>So we're getting the same results for 1000000 now, but my version is
>still a lot slower. Maybe the memoization is not working right. Hmm.

You must be kidding. The memoization using standard tools impressed me.
Compared to the result below it is only one order of magnitude.

In the meantime I have made a double precision version:

~/euler: time coinsusad 1000000
1333983445341383545001

real 0m1.209s
user 0m1.038s
sys 0m0.021s

A double precision version takes double the time,
900 ms for the original challenge.
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

On 28/12/2023 9:44 am, George Neuner wrote:
> On Wed, 27 Dec 2023 15:57:48 +0000, zbigniew2011@gmail.com (LIT)
> wrote:
>
>>> Recursion is silly (if you can avoid it).
>>
>> Not really.
>>
>> Recursion is elegant — but actually isn't any
>> more efficient than iteration, and of course
>> it requires stack space.
>
> Not necessarily. Scheme compilers actually are *required* to turn
> self recursion into a loop (except in the case of a supported "debug"
> mode).
>
> I think some of the Lisps can do it also - at least with
> (optimize (debug 0) (space 3))

That's kind of offensive (to the programmer) which - not unlike ChatGPT -
puts humans in a diminished role. So the question becomes will humans have
any role at all? Much has been said about 'general purpose subroutines'.
ISTM the only logical reason to have them and (by implication) standards
is that they benefit automation.

Joerg Mertens <joerg-mertens@t-online.de> writes:

> Julieta Shem <jshem@yaxenu.org> writes:
>
>> What do you mean iterative? For instance, Gerald Sussman and Harold
>> Abelson classify as `iterative' the procedure
>>
>> (def (f n [acc 1])
>> (if (= n 1)
>> 1
>> (f (dec n) (* acc n)))),
>>
>> which is self-referential.
>
> Are you sure? IIRC they differentiate between programs and processes.

They do --- between ``procedures'' and processes.

> So your function would be a recursive program but it doesn't create a
> recursive process (assumed the implementation is tail call optimized).

On section 1.2.1, Figure 1.4 is roughly

--8<---------------cut here---------------start------------->8---
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

Figure 1.4: A linear iterative process for computing 6!.
--8<---------------cut here---------------end--------------->8---

You're right that they don't call it an iterative /procedure/, but they
do call it an iterative /process/. So maybe I can fix my post with

--8<---------------cut here---------------start------------->8---
[They] classify as `iterative' the process generated by the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.
--8<---------------cut here---------------end--------------->8---

Here's their words directly:

--8<---------------cut here---------------start------------->8---
Consider the [linearly recursive naive factorial procedure]. The
substitution model reveals a shape of expansion followed by contraction,
indicated by the arrow in figure 1.3. The expansion occurs as the
process builds up a chain of deferred operations (in this case, a chain
of multiplications). The contraction occurs as the operations are
actually performed. This type of process, characterized by a chain of
deferred operations, is called a recursive process. Carrying out this
process requires that the interpreter keep track of the operations to be
performed later on. In the computation of n!, the length of the chain of
deferred multiplications, and hence the amount of information needed to
keep track of it, grows linearly with n (is proportional to n), just
like the number of steps. Such a process is called a linear recursive
process.

By contrast, the second process [the fact-iter procedure of Figure 1.4]
does not grow and shrink. At each step, all we need to keep track of,
for any n, are the current values of the variables product, counter, and
max-count. We call this an /iterative process/. In general, an iterative
process is one whose state can be summarized by a fixed number of state
variables, together with a fixed rule that describes how the state
variables should be updated as the process moves from state to state and
an (optional) end test that specifies conditions under which the process
should terminate. In computing n!, the number of steps required grows
linearly with n. Such a process is called a linear iterative process.
--8<---------------cut here---------------end--------------->8---

They constrast the two notions:

--8<---------------cut here---------------start------------->8---
In contrasting iteration and recursion, we must be careful not to
confuse the notion of a recursive process with the notion of a recursive
procedure. When we describe a procedure as recursive, we are referring
to the syntactic fact that the procedure definition refers (either
directly or indirectly) to the procedure itself. But when we describe a
process as following a pattern that is, say, linearly recursive, we are
speaking about how the process evolves, not about the syntax of how a
procedure is written. It may seem disturbing that we refer to a
recursive procedure such as fact-iter as generating an iterative
process. However, the process really is iterative: Its state is captured
completely by its three state variables, and an interpreter need keep
track of only three variables in order to execute the process.
--8<---------------cut here---------------end--------------->8---

albert@cherry.(none) (albert) writes:
> You must be kidding. The memoization using standard tools impressed me.
> Compared to the result below it is only one order of magnitude.

I see, so the algorithms are basically similar. I haven't examined your
code closely yet. But I see you are using a much more efficient memo
table than I am. Yours is indexed on the offset into the coin list,
while mine uses the entire list. I might try adapting mine, maybe to
use arrays instead of a hash table.

I noticed I got an 8x speedup and 5x memory reduction by simply
reversing the order of the coin list, i.e. using (100 50 25 10 5 1)
instead of (1 5 10 25 50 100).

In reality, 50 cent coins and dollar coins are rarely used in the US.
50 cent coins are large enough to be cumbersome, and dollar coins never
became popular because they are too easily confused with quarters (they
are just slightly larger).

Canada has all the coins that the US has, plus a 2 dollar coin, and they
actually use them. France before the Euro had even more, I believe.

In article <87plyq9419.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>albert@cherry.(none) (albert) writes:
>> You must be kidding. The memoization using standard tools impressed me.
>> Compared to the result below it is only one order of magnitude.
>
>I see, so the algorithms are basically similar. I haven't examined your
>code closely yet. But I see you are using a much more efficient memo
>table than I am. Yours is indexed on the offset into the coin list,
>while mine uses the entire list. I might try adapting mine, maybe to
>use arrays instead of a hash table.

It is similar in the sense that at the end intermediate results
are calculated in the same partial sums. There is a great difference
that it is reversed. Memoization asks for the intermediate results e.g. 100,5
to be calculated. I start from the bottom and just guess that all
intermediate results are needed.I start with calculating 1,1 2,1 3,1 ..
This depend on analysing the problem.
You will get nowhere by this method if you apply at eulerproject
problem 502 (counting castles).

>
>I noticed I got an 8x speedup and 5x memory reduction by simply
>reversing the order of the coin list, i.e. using (100 50 25 10 5 1)
>instead of (1 5 10 25 50 100).
>
>In reality, 50 cent coins and dollar coins are rarely used in the US.
>50 cent coins are large enough to be cumbersome, and dollar coins never
>became popular because they are too easily confused with quarters (they
>are just slightly larger).
>
>Canada has all the coins that the US has, plus a 2 dollar coin, and they
>actually use them. France before the Euro had even more, I believe.

France used denominations 10 centimes up till 10 Franc .
The 10 Franc piece and 2 euro piece and the Can 2 dollar piece
have comparable purchasing power. A the time the Netherlands
had a 2.5 guilder coins, also comparable.
Formally the Euro has a regular 1 2 5 10 20 50 100 200 series
but the 1 and 2 cent pieces are no more used in the Netherlands.
So 5 or 6 coins in actual use.

Groetjes Albert
>
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -