Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #64979 > unrolled thread
| Started by | "Morten W. Petersen" <morphex@gmail.com> |
|---|---|
| First post | 2015-07-09 12:49 +0200 |
| Last post | 2015-07-16 09:41 +1200 |
| Articles | 20 on this page of 292 — 25 participants |
Back to article view | Back to comp.lang.c
Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 12:49 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 12:03 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 14:15 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 13:49 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 15:15 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 14:25 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 15:36 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 14:51 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 16:02 +0200
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-09 20:48 +0100
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-09 09:54 -0400
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 15:08 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 16:16 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 15:18 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 16:24 +0200
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-09 20:31 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 21:42 +0200
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-10 00:57 +0100
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-09 20:39 +0100
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 21:44 +0100
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-09 22:50 +0100
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-09 13:49 +0100
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 13:52 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 15:26 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 14:28 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-09 05:28 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 15:09 +0200
Re: Recursion or loop, design questions "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-09 09:25 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 18:41 +0200
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-10 11:52 -0400
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-10 18:44 +0200
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-10 18:52 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-10 20:34 +0200
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-10 11:50 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-10 20:56 +0200
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-10 13:30 -0700
Re: Recursion or loop, design questions Philip Lantz <prl@canterey.us> - 2015-07-11 10:51 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-11 16:07 -0700
Re: Recursion or loop, design questions Philip Lantz <prl@canterey.us> - 2015-07-12 00:20 -0700
Re: Recursion or loop, design questions gordonb.j93iw@burditt.org (Gordon Burditt) - 2015-07-11 21:26 -0500
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-09 10:08 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 19:19 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-09 19:11 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 21:28 +0200
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-09 13:41 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 15:22 +0200
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 18:45 +0200
Re: Recursion or loop, design questions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-07-09 18:05 +0000
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-11 07:06 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-11 15:51 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-15 09:36 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-15 10:49 -0700
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-15 13:05 -0500
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 10:28 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-20 12:41 -0700
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-20 21:37 +0100
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-24 13:05 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-24 15:07 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-30 12:42 -0700
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-24 15:38 -0500
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-30 12:39 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-30 22:35 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-08-02 07:09 -0700
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-08-02 14:43 -0500
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-08-03 09:48 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-09 21:23 +0200
Re: Recursion or loop, design questions Andrew Cooper <amc96@cam.ac.uk> - 2015-07-10 00:52 +0100
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-10 01:28 +0100
Re: Recursion or loop, design questions Phil Carmody <pc+usenet@asdf.org> - 2015-07-12 13:20 +0300
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-12 11:39 +0100
Re: Recursion or loop, design questions David Kleinecke <dkleinecke@gmail.com> - 2015-07-12 10:28 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-13 08:17 +1200
Re: Recursion or loop, design questions David Brown <david.brown@hesbynett.no> - 2015-07-21 14:46 +0200
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-25 19:27 -0700
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-07-13 21:16 +0000
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-10 08:34 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-10 00:46 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-10 12:35 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-10 12:47 +0100
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-10 14:29 +0200
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-11 06:36 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-11 07:16 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-15 14:23 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-15 15:27 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 19:27 -0700
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-11 15:27 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-11 08:00 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-11 15:46 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-11 16:01 -0700
Re: Recursion or loop, design questions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-07-12 00:36 +0000
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-15 13:55 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-15 14:12 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 19:45 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-15 14:34 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-15 15:37 -0700
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-16 10:07 +0100
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-16 10:18 +0100
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-16 13:35 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-16 21:10 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-17 13:55 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-17 11:16 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-17 11:25 -0700
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-17 20:51 +0100
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-17 13:48 -0700
Re: Recursion or loop, design questions David Brown <david.brown@hesbynett.no> - 2015-07-21 15:12 +0200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-21 10:56 -0700
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-21 19:43 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-21 12:52 -0700
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-21 21:17 +0100
Re: Recursion or loop, design questions David Brown <david.brown@hesbynett.no> - 2015-07-21 23:58 +0200
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-22 20:39 +0100
Re: Recursion or loop, design questions Richard Damon <Richard@Damon-Family.org> - 2015-07-24 00:54 -0400
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-24 09:06 +0100
Re: Recursion or loop, design questions Richard Damon <Richard@Damon-Family.org> - 2015-07-24 08:04 -0400
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-24 13:48 +0100
Re: Recursion or loop, design questions Richard Damon <Richard@Damon-Family.org> - 2015-07-25 14:02 -0400
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-30 13:41 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-02 15:41 +0200
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-02 21:51 +0000
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-03 01:20 +0200
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-04 10:54 +0000
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-04 06:02 -0700
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-08-04 14:03 +0100
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-08-04 11:36 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-08-04 11:21 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-04 12:18 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-04 13:19 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-04 13:35 -0700
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-08-04 21:40 +0100
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-04 13:51 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-04 22:57 +0200
Re: Recursion or loop, design questions David Brown <david.brown@hesbynett.no> - 2015-08-05 08:45 +0200
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-04 14:19 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-04 23:22 +0200
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-04 14:28 -0700
Language (was: Re: Recursion or loop, design questions) "Morten W. Petersen" <morphex@gmail.com> - 2015-08-04 23:35 +0200
Re: Language (was: Re: Recursion or loop, design questions) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-04 14:45 -0700
Re: Language "Morten W. Petersen" <morphex@gmail.com> - 2015-08-04 23:55 +0200
Re: Language (was: Re: Recursion or loop, design questions) fir <profesor.fir@gmail.com> - 2015-08-04 16:44 -0700
Re: Language (was: Re: Recursion or loop, design questions) fir <profesor.fir@gmail.com> - 2015-08-04 17:18 -0700
Re: Language (was: Re: Recursion or loop, design questions) fir <profesor.fir@gmail.com> - 2015-08-05 01:32 -0700
Re: Language Richard Heathfield <rjh@cpax.org.uk> - 2015-08-05 09:51 +0100
Re: Language Richard Heathfield <rjh@cpax.org.uk> - 2015-08-05 12:55 +0100
Re: Language Gareth Owen <gwowen@gmail.com> - 2015-08-05 19:12 +0100
Re: Language Richard Heathfield <rjh@cpax.org.uk> - 2015-08-06 17:09 +0100
Re: Language luser droog <luser.droog@gmail.com> - 2015-08-06 15:10 -0700
Re: Language Richard Heathfield <rjh@cpax.org.uk> - 2015-08-07 09:48 +0100
Re: Language luser droog <luser.droog@gmail.com> - 2015-08-07 13:37 -0700
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-06 10:54 +0000
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-06 13:32 +0200
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-08-06 11:06 -0400
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-06 11:52 -0700
Re: Recursion or loop, design questions David Brown <david.brown@hesbynett.no> - 2015-08-06 21:19 +0200
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-08-06 17:59 -0400
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-06 15:54 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-06 12:56 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-07 23:45 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-08 09:27 +0200
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-08 01:09 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-08 01:34 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-08-08 13:00 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-08 14:22 -0700
Re: Recursion or loop, design questions David Kleinecke <dkleinecke@gmail.com> - 2015-08-08 16:12 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-08-08 17:31 -0700
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-09 13:34 +0000
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-09 08:38 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-09 09:31 +0200
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-09 01:52 -0700
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-06 04:40 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-25 20:19 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-25 23:59 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-30 15:53 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-25 19:43 -0700
Re: Recursion or loop, design questions David Kleinecke <dkleinecke@gmail.com> - 2015-07-25 20:05 -0700
Re: Recursion or loop, design questions Richard Heathfield <rjh@cpax.org.uk> - 2015-07-27 23:53 +0100
Re: Recursion or loop, design questions fir <profesor.fir@gmail.com> - 2015-08-03 01:51 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-08-03 10:04 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-17 21:34 +0100
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-17 13:52 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-17 21:57 +0100
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 10:44 +0100
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-18 11:00 +0100
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-18 05:25 -0500
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 14:26 +0100
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-18 17:38 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-18 10:05 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 21:31 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-18 14:28 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-18 15:01 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-18 15:39 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-18 15:44 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-18 15:55 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-19 10:58 +1200
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-18 16:26 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-18 17:23 -0700
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-18 18:04 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 00:03 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-19 13:30 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 08:45 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-19 20:59 +0200
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-19 21:19 +0200
Re: Recursion or loop, design questions Les Cargill <lcargill99@comcast.com> - 2015-07-20 07:23 -0500
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-07-19 21:11 +0000
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 15:37 -0700
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-09 13:55 +0000
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-05 11:22 -0700
Re: Recursion or loop, design questions Gareth Owen <gwowen@gmail.com> - 2015-07-19 17:22 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 10:25 -0700
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-19 03:15 -0500
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-19 10:36 +0100
Re: Recursion or loop, design questions Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2015-07-19 12:45 -0400
Re: Recursion or loop, design questions Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2015-07-19 13:05 -0400
Re: Recursion or loop, design questions Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2015-07-19 13:09 -0400
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 10:40 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-19 22:31 +0100
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-09 14:05 +0000
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-09 21:22 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-09 16:14 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-10 05:39 +0200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-10 01:40 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-08-10 21:03 +1200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-10 03:16 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-10 12:16 +0200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-10 03:36 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-10 12:45 +0200
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-22 14:07 +0000
Re: Recursion or loop, design questions raltbos@xs4all.nl (Richard Bos) - 2015-08-22 14:07 +0000
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 02:47 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-19 22:23 +1200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 05:01 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-20 09:55 +1200
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-19 23:13 +0100
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-20 10:19 +1200
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-19 17:21 -0500
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-20 00:25 +0100
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-20 11:45 +1200
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-20 02:34 -0500
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-20 10:52 +0100
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-20 05:31 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 22:16 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-20 17:24 +1200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 22:36 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-20 21:07 +1200
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-20 02:51 -0700
Re: Recursion or loop, design questions Les Cargill <lcargill99@comcast.com> - 2015-07-19 10:12 -0500
Re: Recursion or loop, design questions Robert Wessel <robertwessel2@yahoo.com> - 2015-07-19 16:54 -0500
Re: Recursion or loop, design questions Les Cargill <lcargill99@comcast.com> - 2015-07-20 12:34 -0500
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-23 07:28 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-27 11:08 +0200
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-30 15:45 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-02 14:59 +0200
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-08-04 08:40 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-08-04 23:05 +0200
Re: Recursion or loop, design questions Keith Thompson <kst-u@mib.org> - 2015-07-19 12:46 -0700
Re: Recursion or loop, design questions Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-07-19 12:57 -0700
Re: Recursion or loop, design questions Gareth Owen <gwowen@gmail.com> - 2015-07-19 21:16 +0100
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 15:50 -0700
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-18 09:13 -0400
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 15:04 +0100
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-18 12:40 -0400
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 16:27 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 14:26 +0100
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-18 09:58 -0400
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 15:24 +0100
Re: Recursion or loop, design questions Richard Damon <Richard@Damon-Family.org> - 2015-07-18 10:29 -0400
Re: Recursion or loop, design questions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-07-18 17:32 +0000
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 15:28 -0700
Re: Recursion or loop, design questions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-07-20 22:58 +0000
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-23 03:13 -0700
Re: Recursion or loop, design questions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-18 21:49 +0100
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 15:12 -0700
Re: Recursion or loop, design questions "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-20 15:21 -0700
Re: Recursion or loop, design questions "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-20 15:23 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-23 03:46 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-23 03:31 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-21 04:08 -0700
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-11 08:50 -0700
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-11 18:43 +0200
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-11 18:54 +0200
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-11 13:06 -0400
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-12 23:45 +0200
Re: Recursion or loop, design questions James Kuyper <jameskuyper@verizon.net> - 2015-07-12 17:48 -0400
Re: Recursion or loop, design questions "Morten W. Petersen" <morphex@gmail.com> - 2015-07-13 01:27 +0200
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-11 19:39 +0100
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-11 14:51 -0700
Re: Recursion or loop, design questions Bartc <bc@freeuk.com> - 2015-07-11 23:51 +0100
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-15 08:04 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-16 09:36 +1200
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-20 10:37 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-21 20:55 +1200
Re: Recursion or loop, design questions Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-23 07:39 -0700
Re: Recursion or loop, design questions Ian Collins <ian-news@hotmail.com> - 2015-07-16 09:41 +1200
Page 4 of 15 — ← Prev page 1 2 3 [4] 5 6 … 15 Next page →
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-07-30 12:39 -0700 |
| Message-ID | <kfnio91cu57.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #66312 |
Robert Wessel <robertwessel2@yahoo.com> writes:
> On Mon, 20 Jul 2015 10:28:44 -0700, Tim Rentsch
> <txr@alumni.caltech.edu> wrote:
>
>> Robert Wessel <robertwessel2@yahoo.com> writes:
>>
>>> On Wed, 15 Jul 2015 09:36:52 -0700, Tim Rentsch
>>> <txr@alumni.caltech.edu> wrote:
>>>
>>>> Keith Thompson <kst-u@mib.org> writes:
>>>>
>>>>> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>>>>> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>>>>>
>>>>> [...]
>>>>>
>>>>>>> The most obvious is factorial,
>>>>>>
>>>>>> Hogwash. You're assuming a naive recursive formulation, which
>>>>>> is a bad assumption. For small integers it hardly makes a
>>>>>> difference - easier just to do a table lookup. For large
>>>>>> integers a recursive formulation is better: for example,
>>>>>> computing 1000000 factorial (or was it 10000000 factorial?
>>>>>> I think it was one of the two), my simple recursive version
>>>>>> ran about 50 times faster than the simple looping version.
>>>>>
>>>>> I'm curious about the details. How do you get a 50x speedup using
>>>>> recursion rather than iteration?
>>>>>
>>>>> Of course with numbers that big the representation is going to be an
>>>>> issue.
>>>>
>>>> Right, and that's the heart of the matter. The key idea is that
>>>> when you multiply multiple-precision integers you want to keep
>>>> the numbers as small as you can, or in other words have the two
>>>> numbers being multiplied as close to being the same size as you
>>>> can. With the understanding that I am writing in regular C
>>>> rather than a language that has multiple-precision arithmetic
>>>> built-in, here is the algorithm:
>>>>
>>>> static unsigned product( unsigned, unsigned );
>>>>
>>>> unsigned
>>>> factorial( unsigned n ){
>>>> return product( n, 1 );
>>>> }
>>>>
>>>> unsigned
>>>> product( unsigned n, unsigned v ){
>>>> /* the product of 'n' consecutive integers starting at 'v' */
>>>> if( n < 2 ) return v;
>>>> return product( n-n/2, v ) * product( n/2, v + (n-n/2) );
>>>> }
>>>>
>>>> This computes factorial using a binary tree of products, so the
>>>> numbers being multiplied at each stage are, roughly, the same
>>>> size. Silly for small integers, but a huge win for computing
>>>> factorials of large integers.
>>>
>>> You've implemented a completely different algorithm, not just a
>>> non-recursive version of the same algorithm.
>>
>> I never claimed to be using a transformed version of the simple
>> iterative algorithm, only that recursion is useful (or more
>> accurately, can be useful) in the problem of computing factorial.
>>
>>> This is like saying that recursive algorithms are better by
>>> comparing Quicksort to a bubble sort.
>>
>> First I didn't say that recursive algorithms are better, only
>> that (for factorial) they aren't always worse (and are better
>> in this particular case).
>>
>> Second I don't think your analogy is quite on-point. The
>> iterative algorithm and the recursive algorithm I gave compute
>> all the same multiplications, it just computes them in a
>> different order. The reason Quicksort is better than bubble
>> sort is because it does very different computations, and most
>> notably fewer computations. Certainly the recursive factorial
>> algorithm is not exactly the same as the regular iterative one,
>> but the differences are not nearly as dramatic as those between
>> Quicksort and bubble sort.
>
> Not that it really matters, but I think it's a pretty apt
> comparision - in both cases you're turning a simple(r) approach
> into a divide-and-conqure approach.
That is a way of looking at things, and not completely
unreasonable.
However, we might look at things somewhat differently. All of
the three basic algorithms for computing factorial -- ie,
multiplying upwards in an iterative fashion, simplistic recursion
by calling factorial( n-1 ), and the split-in-half recursive
method given earlier -- are all divide-and-conquer approaches,
with the only difference being how the partitions are chosen - 1
and N-1 in the first case, N-1 and 1 in the second case, and N/2,
N-N/2 in the third case. In each case the partitioning depends
only on the size of the range in question, and combining the two
halves is always the same operation.
For sorting, bubble sort isn't really a divide-and-conquer type
algorithm, but let's say insertion sort instead. Now we again
have two divide-and-conquer type algorithms, but with a big
diffence in how the partitioning is done and in how the two parts
are combined into a larger whole. With insertion sort, the
partitioning is easy, we slice off one more element each time,
but the combination operation is non-trivial. In quicksort, it's
exactly the opposite - the partitioning is complicated and
depends heavily on the input, but when we have finished doing the
subparts nothing more needs to be done to combine them into a
sorted whole. This is quite wonderful as divide-and-conquer
goes.
So, I don't think it's wrong when you say there are some
parallels. There are. But I don't think the parallels tell the
whole story. What makes quicksort interesting is not the
recursive nature of it but the extremely clever way it partitions
the input so combining the two halves can be done with no further
effort. The split-in-half recursive factorial doesn't have this
property; it is a little bit clever, I'll grant you that, but
not nearly as clever as quicksort.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-07-30 22:35 -0700 |
| Message-ID | <f60989d4-daf3-40f8-a946-314488fb6384@googlegroups.com> |
| In reply to | #66578 |
On Thursday, July 30, 2015 at 8:39:30 PM UTC+1, Tim Rentsch wrote: > > However, we might look at things somewhat differently. All of > the three basic algorithms for computing factorial -- ie, > multiplying upwards in an iterative fashion, simplistic recursion > by calling factorial( n-1 ), and the split-in-half recursive > method given earlier -- are all divide-and-conquer approaches, > with the only difference being how the partitions are chosen - 1 > and N-1 in the first case, N-1 and 1 in the second case, and N/2, > N-N/2 in the third case. In each case the partitioning depends > only on the size of the range in question, and combining the two > halves is always the same operation. > I would reserve "divide and conquer" for logarithmic approaches. The characteristic is that you chop the problem into a few large pieces, with the algorithm working best when the chop is roughly 50/50. qsort degrades catastrophically if the input is contrived so that each partition is exactly one / N-1 (as happens when you use the first element as the partition on already sorted input). Iterating through a list isn't "divide and conquer", it's the brute force approach. Of course if you insist on recasting iteration as recursion, this won't be as obvious, you'll lose the feel for how long your algorithms are taking.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-08-02 07:09 -0700 |
| Message-ID | <kfnh9ohaijr.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #66596 |
Malcolm McLean <malcolm.mclean5@btinternet.com> writes: > On Thursday, July 30, 2015 at 8:39:30 PM UTC+1, Tim Rentsch wrote: > >> However, we might look at things somewhat differently. All of >> the three basic algorithms for computing factorial -- ie, >> multiplying upwards in an iterative fashion, simplistic recursion >> by calling factorial( n-1 ), and the split-in-half recursive >> method given earlier -- are all divide-and-conquer approaches, >> with the only difference being how the partitions are chosen - 1 >> and N-1 in the first case, N-1 and 1 in the second case, and N/2, >> N-N/2 in the third case. In each case the partitioning depends >> only on the size of the range in question, and combining the two >> halves is always the same operation. > > I would reserve "divide and conquer" for logarithmic approaches. > The characteristic is that you chop the problem into a few > large pieces, with the algorithm working best when the chop is > roughly 50/50. [snip elaboration] That is a way of classifying things, but not the way I had in mind. The point of my comment (whether one wants to call it "divide and conquer" or something else) is that a problem is split into parts, the parts are dealt with independently, and the results combined to produce an overall answer. Sometimes this can lead to great efficiencies, sometimes it has essentially no effect on efficiency, and sometimes it basically cannot be done (eg, with bin packing or other NP-hard problems). What I'm trying to emphasize is similarity in approach, not what term is used to name it.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-08-02 14:43 -0500 |
| Message-ID | <35ssra97ddgpgd67ebu873kc0u85gsd841@4ax.com> |
| In reply to | #66578 |
On Thu, 30 Jul 2015 12:39:16 -0700, Tim Rentsch
<txr@alumni.caltech.edu> wrote:
>Robert Wessel <robertwessel2@yahoo.com> writes:
>
>> On Mon, 20 Jul 2015 10:28:44 -0700, Tim Rentsch
>> <txr@alumni.caltech.edu> wrote:
>>
>>> Robert Wessel <robertwessel2@yahoo.com> writes:
>>>
>>>> On Wed, 15 Jul 2015 09:36:52 -0700, Tim Rentsch
>>>> <txr@alumni.caltech.edu> wrote:
>>>>
>>>>> Keith Thompson <kst-u@mib.org> writes:
>>>>>
>>>>>> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>>>>>> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>>>>>>
>>>>>> [...]
>>>>>>
>>>>>>>> The most obvious is factorial,
>>>>>>>
>>>>>>> Hogwash. You're assuming a naive recursive formulation, which
>>>>>>> is a bad assumption. For small integers it hardly makes a
>>>>>>> difference - easier just to do a table lookup. For large
>>>>>>> integers a recursive formulation is better: for example,
>>>>>>> computing 1000000 factorial (or was it 10000000 factorial?
>>>>>>> I think it was one of the two), my simple recursive version
>>>>>>> ran about 50 times faster than the simple looping version.
>>>>>>
>>>>>> I'm curious about the details. How do you get a 50x speedup using
>>>>>> recursion rather than iteration?
>>>>>>
>>>>>> Of course with numbers that big the representation is going to be an
>>>>>> issue.
>>>>>
>>>>> Right, and that's the heart of the matter. The key idea is that
>>>>> when you multiply multiple-precision integers you want to keep
>>>>> the numbers as small as you can, or in other words have the two
>>>>> numbers being multiplied as close to being the same size as you
>>>>> can. With the understanding that I am writing in regular C
>>>>> rather than a language that has multiple-precision arithmetic
>>>>> built-in, here is the algorithm:
>>>>>
>>>>> static unsigned product( unsigned, unsigned );
>>>>>
>>>>> unsigned
>>>>> factorial( unsigned n ){
>>>>> return product( n, 1 );
>>>>> }
>>>>>
>>>>> unsigned
>>>>> product( unsigned n, unsigned v ){
>>>>> /* the product of 'n' consecutive integers starting at 'v' */
>>>>> if( n < 2 ) return v;
>>>>> return product( n-n/2, v ) * product( n/2, v + (n-n/2) );
>>>>> }
>>>>>
>>>>> This computes factorial using a binary tree of products, so the
>>>>> numbers being multiplied at each stage are, roughly, the same
>>>>> size. Silly for small integers, but a huge win for computing
>>>>> factorials of large integers.
>>>>
>>>> You've implemented a completely different algorithm, not just a
>>>> non-recursive version of the same algorithm.
>>>
>>> I never claimed to be using a transformed version of the simple
>>> iterative algorithm, only that recursion is useful (or more
>>> accurately, can be useful) in the problem of computing factorial.
>>>
>>>> This is like saying that recursive algorithms are better by
>>>> comparing Quicksort to a bubble sort.
>>>
>>> First I didn't say that recursive algorithms are better, only
>>> that (for factorial) they aren't always worse (and are better
>>> in this particular case).
>>>
>>> Second I don't think your analogy is quite on-point. The
>>> iterative algorithm and the recursive algorithm I gave compute
>>> all the same multiplications, it just computes them in a
>>> different order. The reason Quicksort is better than bubble
>>> sort is because it does very different computations, and most
>>> notably fewer computations. Certainly the recursive factorial
>>> algorithm is not exactly the same as the regular iterative one,
>>> but the differences are not nearly as dramatic as those between
>>> Quicksort and bubble sort.
>>
>> Not that it really matters, but I think it's a pretty apt
>> comparision - in both cases you're turning a simple(r) approach
>> into a divide-and-conqure approach.
>
>That is a way of looking at things, and not completely
>unreasonable.
>
>However, we might look at things somewhat differently. All of
>the three basic algorithms for computing factorial -- ie,
>multiplying upwards in an iterative fashion, simplistic recursion
>by calling factorial( n-1 ), and the split-in-half recursive
>method given earlier -- are all divide-and-conquer approaches,
>with the only difference being how the partitions are chosen - 1
>and N-1 in the first case, N-1 and 1 in the second case, and N/2,
>N-N/2 in the third case. In each case the partitioning depends
>only on the size of the range in question, and combining the two
>halves is always the same operation.
>
>For sorting, bubble sort isn't really a divide-and-conquer type
>algorithm, but let's say insertion sort instead. Now we again
>have two divide-and-conquer type algorithms, but with a big
>diffence in how the partitioning is done and in how the two parts
>are combined into a larger whole. With insertion sort, the
>partitioning is easy, we slice off one more element each time,
>but the combination operation is non-trivial. In quicksort, it's
>exactly the opposite - the partitioning is complicated and
>depends heavily on the input, but when we have finished doing the
>subparts nothing more needs to be done to combine them into a
>sorted whole. This is quite wonderful as divide-and-conquer
>goes.
>
>So, I don't think it's wrong when you say there are some
>parallels. There are. But I don't think the parallels tell the
>whole story. What makes quicksort interesting is not the
>recursive nature of it but the extremely clever way it partitions
>the input so combining the two halves can be done with no further
>effort. The split-in-half recursive factorial doesn't have this
>property; it is a little bit clever, I'll grant you that, but
>not nearly as clever as quicksort.
If you consider multiplication *not* to be a basic operation, which it
is not when dealing with large numbers, then an effort to avoid the
use of large multiplications is clearly different than one that does
not. Yes, insertion sort can be sort-of thought of as dividing
sorting into two smaller sorting problems, but of wildly unequal size.
But we don't usually mean that when we say divide-and-conquer. Looked
at this way, Quicksort does not sort any fewer partitions than does
insertion sort - it just sorts *better* partitions. So while
iterative factorial is like insertion sort (and yes, that is a better
analogy than bubble sort in this case), the "good" recursive version
is still more like Quicksort, in that its arraigning the underlying
operations, not so that it's doing fewer multiplications, just better
ones.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-08-03 09:48 -0700 |
| Message-ID | <kfntwsg8gix.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #66732 |
Robert Wessel <robertwessel2@yahoo.com> writes:
> On Thu, 30 Jul 2015 12:39:16 -0700, Tim Rentsch
> <txr@alumni.caltech.edu> wrote:
>
>> Robert Wessel <robertwessel2@yahoo.com> writes:
>>
>>> On Mon, 20 Jul 2015 10:28:44 -0700, Tim Rentsch
>>> <txr@alumni.caltech.edu> wrote:
>>>
>>>> Robert Wessel <robertwessel2@yahoo.com> writes:
>>>>
>>>>> On Wed, 15 Jul 2015 09:36:52 -0700, Tim Rentsch
>>>>> <txr@alumni.caltech.edu> wrote:
>>>>>
>>>>>> Keith Thompson <kst-u@mib.org> writes:
>>>>>>
>>>>>>> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>>>>>>> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>>>>>>>
>>>>>>> [...]
>>>>>>>
>>>>>>>>> The most obvious is factorial,
>>>>>>>>
>>>>>>>> Hogwash. You're assuming a naive recursive formulation, which
>>>>>>>> is a bad assumption. For small integers it hardly makes a
>>>>>>>> difference - easier just to do a table lookup. For large
>>>>>>>> integers a recursive formulation is better: for example,
>>>>>>>> computing 1000000 factorial (or was it 10000000 factorial?
>>>>>>>> I think it was one of the two), my simple recursive version
>>>>>>>> ran about 50 times faster than the simple looping version.
>>>>>>>
>>>>>>> I'm curious about the details. How do you get a 50x speedup using
>>>>>>> recursion rather than iteration?
>>>>>>>
>>>>>>> Of course with numbers that big the representation is going to be an
>>>>>>> issue.
>>>>>>
>>>>>> Right, and that's the heart of the matter. The key idea is that
>>>>>> when you multiply multiple-precision integers you want to keep
>>>>>> the numbers as small as you can, or in other words have the two
>>>>>> numbers being multiplied as close to being the same size as you
>>>>>> can. With the understanding that I am writing in regular C
>>>>>> rather than a language that has multiple-precision arithmetic
>>>>>> built-in, here is the algorithm:
>>>>>>
>>>>>> static unsigned product( unsigned, unsigned );
>>>>>>
>>>>>> unsigned
>>>>>> factorial( unsigned n ){
>>>>>> return product( n, 1 );
>>>>>> }
>>>>>>
>>>>>> unsigned
>>>>>> product( unsigned n, unsigned v ){
>>>>>> /* the product of 'n' consecutive integers starting at 'v' */
>>>>>> if( n < 2 ) return v;
>>>>>> return product( n-n/2, v ) * product( n/2, v + (n-n/2) );
>>>>>> }
>>>>>>
>>>>>> This computes factorial using a binary tree of products, so the
>>>>>> numbers being multiplied at each stage are, roughly, the same
>>>>>> size. Silly for small integers, but a huge win for computing
>>>>>> factorials of large integers.
>>>>>
>>>>> You've implemented a completely different algorithm, not just a
>>>>> non-recursive version of the same algorithm.
>>>>
>>>> I never claimed to be using a transformed version of the simple
>>>> iterative algorithm, only that recursion is useful (or more
>>>> accurately, can be useful) in the problem of computing factorial.
>>>>
>>>>> This is like saying that recursive algorithms are better by
>>>>> comparing Quicksort to a bubble sort.
>>>>
>>>> First I didn't say that recursive algorithms are better, only
>>>> that (for factorial) they aren't always worse (and are better
>>>> in this particular case).
>>>>
>>>> Second I don't think your analogy is quite on-point. The
>>>> iterative algorithm and the recursive algorithm I gave compute
>>>> all the same multiplications, it just computes them in a
>>>> different order. The reason Quicksort is better than bubble
>>>> sort is because it does very different computations, and most
>>>> notably fewer computations. Certainly the recursive factorial
>>>> algorithm is not exactly the same as the regular iterative one,
>>>> but the differences are not nearly as dramatic as those between
>>>> Quicksort and bubble sort.
>>>
>>> Not that it really matters, but I think it's a pretty apt
>>> comparision - in both cases you're turning a simple(r) approach
>>> into a divide-and-conqure approach.
>>
>> That is a way of looking at things, and not completely
>> unreasonable.
>>
>> However, we might look at things somewhat differently. All of
>> the three basic algorithms for computing factorial -- ie,
>> multiplying upwards in an iterative fashion, simplistic recursion
>> by calling factorial( n-1 ), and the split-in-half recursive
>> method given earlier -- are all divide-and-conquer approaches,
>> with the only difference being how the partitions are chosen - 1
>> and N-1 in the first case, N-1 and 1 in the second case, and N/2,
>> N-N/2 in the third case. In each case the partitioning depends
>> only on the size of the range in question, and combining the two
>> halves is always the same operation.
>>
>> For sorting, bubble sort isn't really a divide-and-conquer type
>> algorithm, but let's say insertion sort instead. Now we again
>> have two divide-and-conquer type algorithms, but with a big
>> diffence in how the partitioning is done and in how the two parts
>> are combined into a larger whole. With insertion sort, the
>> partitioning is easy, we slice off one more element each time,
>> but the combination operation is non-trivial. In quicksort, it's
>> exactly the opposite - the partitioning is complicated and
>> depends heavily on the input, but when we have finished doing the
>> subparts nothing more needs to be done to combine them into a
>> sorted whole. This is quite wonderful as divide-and-conquer
>> goes.
>>
>> So, I don't think it's wrong when you say there are some
>> parallels. There are. But I don't think the parallels tell the
>> whole story. What makes quicksort interesting is not the
>> recursive nature of it but the extremely clever way it partitions
>> the input so combining the two halves can be done with no further
>> effort. The split-in-half recursive factorial doesn't have this
>> property; it is a little bit clever, I'll grant you that, but
>> not nearly as clever as quicksort.
>
> If you consider multiplication *not* to be a basic operation,
> which it is not when dealing with large numbers, then an effort to
> avoid the use of large multiplications is clearly different than
> one that does not.
The point is it's the same operation whether a linear approach or
a subdividing approach is taken. It is better to combine subarts
in a different order, but it's still the same operation.
> Yes, insertion sort can be sort-of thought of
> as dividing sorting into two smaller sorting problems, but of
> wildly unequal size. But we don't usually mean that when we say
> divide-and-conquer. Looked at this way, Quicksort does not sort
> any fewer partitions than does insertion sort - it just sorts
> *better* partitions. So while iterative factorial is like
> insertion sort (and yes, that is a better analogy than bubble sort
> in this case), the "good" recursive version is still more like
> Quicksort, in that its arraigning the underlying operations, not
> so that it's doing fewer multiplications, just better ones.
If you want me to agree that a subdividing factorial is more
clever than a linear factorial, I have no problem with that.
However, I still think trying to draw an analogy between
quicksort and subdividing factorial (and their corresponding
linear versions) strains the metaphor past the point where it is
reasonable. The cleverness of quicksort is qualitatively bigger
than the cleverness of subdividing factorial. And in terms of
performance, the performance /improvement/ of quicksort is more
than a thousand times larger than the performance improvement of
subdividing factorial (compared to their corresponding linear
versions) for inputs of these sizes. (And this is if it was
only a million factorial - if it was ten million factorial,
the ratio is closer to ten thousand.)
If we still have a difference of opinion on the matter, I'm okay
with that. But IMO it is not anything more than a difference of
opinion.
[toc] | [prev] | [next] | [standalone]
| From | "Morten W. Petersen" <morphex@gmail.com> |
|---|---|
| Date | 2015-07-09 21:23 +0200 |
| Message-ID | <mnmhlm$ucl$1@speranza.aioe.org> |
| In reply to | #64979 |
On 09.07.2015 19:55, Stefan Ram wrote: > ram@zedat.fu-berlin.de (Stefan Ram) writes: [...] I'll have a look at these to get a better understanding of trees. Thanks. -Morten
[toc] | [prev] | [next] | [standalone]
| From | Andrew Cooper <amc96@cam.ac.uk> |
|---|---|
| Date | 2015-07-10 00:52 +0100 |
| Message-ID | <mnn1eu$hm3$1@flame.srcf.net> |
| In reply to | #64979 |
On 09/07/2015 11:49, Morten W. Petersen wrote: > However, choosing between recursion and looping is less > obvious, to me at least. Never ever ever recurse. It will come back and bite you. In this example, there are specific XML files which will overflow any arbitrary stack size you choose. One could argue that it might make more readable code. Some programming languages actively encourage it as an example of elegance[1]. (I am a systems programmer and biased in this area. An 8K is genuinely enough for anyone, and 4K is sufficient for the overwhelming majority of cases.) Of course, this like any rule is open to be broken. In my case, anyone who is unable to justify why their specific use of recusion is safe in all circumstances is not going to have their code accepted. ~Andrew [2] We encountered a crash at work. The crash was a stack overflow in program written exclusively on Ocaml. After convincing the developers in question that Ocaml (being a functional language) wasn't immune to the practicalities of real life (a non-infinite stack), a fix was needed. It genuinely took three of them a day crowded around a computer and a whiteboard to alter the problematic function away from being a plain recursive function. The purpose of the function in question was to read data from stderr and forward it to syslog.
[toc] | [prev] | [next] | [standalone]
| From | Bartc <bc@freeuk.com> |
|---|---|
| Date | 2015-07-10 01:28 +0100 |
| Message-ID | <mnn3ha$400$1@dont-email.me> |
| In reply to | #65084 |
On 10/07/2015 00:52, Andrew Cooper wrote: > On 09/07/2015 11:49, Morten W. Petersen wrote: >> However, choosing between recursion and looping is less >> obvious, to me at least. > > Never ever ever recurse. It will come back and bite you. > > In this example, there are specific XML files which will overflow any > arbitrary stack size you choose. > > One could argue that it might make more readable code. Some programming > languages actively encourage it as an example of elegance[1]. > > (I am a systems programmer and biased in this area. An 8K is genuinely > enough for anyone, and 4K is sufficient for the overwhelming majority of > cases.) 8K and 4K what? Do you mean 8KB and 4KB? Machines now have a million times more memory than that. There's nothing wrong with recursion, especially when it will work just fine with all normal input. Just put in extra checks to catch anything unusual (eg. more than 10,000 nested tags in XML. Then tell whoever was responsible for generating the XML to do it properly). -- Bartc
[toc] | [prev] | [next] | [standalone]
| From | Phil Carmody <pc+usenet@asdf.org> |
|---|---|
| Date | 2015-07-12 13:20 +0300 |
| Message-ID | <87a8v1brth.fsf@bazspaz.fatphil.org> |
| In reply to | #65086 |
Bartc <bc@freeuk.com> writes: > On 10/07/2015 00:52, Andrew Cooper wrote: > > On 09/07/2015 11:49, Morten W. Petersen wrote: > >> However, choosing between recursion and looping is less > >> obvious, to me at least. > > > > Never ever ever recurse. It will come back and bite you. > > > > In this example, there are specific XML files which will overflow any > > arbitrary stack size you choose. > > > > One could argue that it might make more readable code. Some programming > > languages actively encourage it as an example of elegance[1]. > > > > (I am a systems programmer and biased in this area. An 8K is genuinely > > enough for anyone, and 4K is sufficient for the overwhelming majority of > > cases.) > > 8K and 4K what? Do you mean 8KB and 4KB? > > Machines now have a million times more memory than that. > > There's nothing wrong with recursion, especially when it will work > just fine with all normal input. Just put in extra checks to catch > anything unusual (eg. more than 10,000 nested tags in XML. Then tell > whoever was responsible for generating the XML to do it properly). Which bit of "I am a systems programmer" do you not understand? 4K/8K stack limits are completely unremarkable, as is the instruction "never ever ever recurse". I remember at my previous job when we had a new security architecture imposed on us, the easiest way around it was to stack smash by exploiting its recursive parser. Phil -- A well regulated militia, being necessary to the security of a free state, the right of the people to keep and bear arms, shall be well regulated.
[toc] | [prev] | [next] | [standalone]
| From | Bartc <bc@freeuk.com> |
|---|---|
| Date | 2015-07-12 11:39 +0100 |
| Message-ID | <mntg30$io9$1@dont-email.me> |
| In reply to | #65401 |
On 12/07/2015 11:20, Phil Carmody wrote: > Bartc <bc@freeuk.com> writes: >> On 10/07/2015 00:52, Andrew Cooper wrote: >>> (I am a systems programmer and biased in this area. An 8K is genuinely >>> enough for anyone, and 4K is sufficient for the overwhelming majority of >>> cases.) >> >> 8K and 4K what? Do you mean 8KB and 4KB? >> >> Machines now have a million times more memory than that. > Which bit of "I am a systems programmer" do you not understand? > > 4K/8K stack limits are completely unremarkable, as is the instruction > "never ever ever recurse". I remember at my previous job when we had > a new security architecture imposed on us, the easiest way around it > was to stack smash by exploiting its recursive parser. This seems completely backwards. The first two machines I used, had a call mechanism where the return address was stored in part of the function itself, which precluded recursion. Then return addresses started to be stored on a stack. Languages such a C had 'auto' local variables which also made recursion possible. It was the way forward. Now you're saying we should forget all that, just use static local variables everywhere, and not use recursion if we can possibly avoid it? All because we choose to restrict ourselves, on a 16,000,000KB machine, to a smaller stack than a 16KB Spectrum! -- Bartc
[toc] | [prev] | [next] | [standalone]
| From | David Kleinecke <dkleinecke@gmail.com> |
|---|---|
| Date | 2015-07-12 10:28 -0700 |
| Message-ID | <32cfd188-9a99-498b-b8be-5c6b7ff5e30e@googlegroups.com> |
| In reply to | #65403 |
On Sunday, July 12, 2015 at 3:40:00 AM UTC-7, Bart wrote: > On 12/07/2015 11:20, Phil Carmody wrote: > > Bartc <bc@freeuk.com> writes: > >> On 10/07/2015 00:52, Andrew Cooper wrote: > > >>> (I am a systems programmer and biased in this area. An 8K is genuinely > >>> enough for anyone, and 4K is sufficient for the overwhelming majority of > >>> cases.) > >> > >> 8K and 4K what? Do you mean 8KB and 4KB? > >> > >> Machines now have a million times more memory than that. > > > Which bit of "I am a systems programmer" do you not understand? > > > > 4K/8K stack limits are completely unremarkable, as is the instruction > > "never ever ever recurse". I remember at my previous job when we had > > a new security architecture imposed on us, the easiest way around it > > was to stack smash by exploiting its recursive parser. > > This seems completely backwards. > > The first two machines I used, had a call mechanism where the return > address was stored in part of the function itself, which precluded > recursion. > > Then return addresses started to be stored on a stack. Languages such a > C had 'auto' local variables which also made recursion possible. It was > the way forward. > > Now you're saying we should forget all that, just use static local > variables everywhere, and not use recursion if we can possibly avoid it? > All because we choose to restrict ourselves, on a 16,000,000KB machine, > to a smaller stack than a 16KB Spectrum! One doesn't need an overt stack to implement recursive functions but there will have to be a list which is a covert stack (there is essentially no difference between a one-way list and a stack). One can start with, say, 100 unused nodes and list and unlist without reallocating anything until you finally get 100 deep and need to allocate 100 more. You still have to allocate arguments - I tend to give my function one argument - a pointer to a struct with the actual arguments - so I can handle the arguments in the same list. The loss of call-by-value seems to be insignificant.
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-07-13 08:17 +1200 |
| Message-ID | <d0g09vFmf76U4@mid.individual.net> |
| In reply to | #65403 |
Bartc wrote: > On 12/07/2015 11:20, Phil Carmody wrote: >> Bartc <bc@freeuk.com> writes: >>> On 10/07/2015 00:52, Andrew Cooper wrote: > >>>> (I am a systems programmer and biased in this area. An 8K is genuinely >>>> enough for anyone, and 4K is sufficient for the overwhelming majority of >>>> cases.) >>> >>> 8K and 4K what? Do you mean 8KB and 4KB? >>> >>> Machines now have a million times more memory than that. > >> Which bit of "I am a systems programmer" do you not understand? >> >> 4K/8K stack limits are completely unremarkable, as is the instruction >> "never ever ever recurse". I remember at my previous job when we had >> a new security architecture imposed on us, the easiest way around it >> was to stack smash by exploiting its recursive parser. > > This seems completely backwards. Never the less, it is very common in the embedded world. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2015-07-21 14:46 +0200 |
| Message-ID | <molerf$1e7$1@dont-email.me> |
| In reply to | #65449 |
On 12/07/15 22:17, Ian Collins wrote: > Bartc wrote: >> On 12/07/2015 11:20, Phil Carmody wrote: >>> Bartc <bc@freeuk.com> writes: >>>> On 10/07/2015 00:52, Andrew Cooper wrote: >> >>>>> (I am a systems programmer and biased in this area. An 8K is >>>>> genuinely >>>>> enough for anyone, and 4K is sufficient for the overwhelming >>>>> majority of >>>>> cases.) >>>> >>>> 8K and 4K what? Do you mean 8KB and 4KB? >>>> >>>> Machines now have a million times more memory than that. >> >>> Which bit of "I am a systems programmer" do you not understand? >>> >>> 4K/8K stack limits are completely unremarkable, as is the instruction >>> "never ever ever recurse". I remember at my previous job when we had >>> a new security architecture imposed on us, the easiest way around it >>> was to stack smash by exploiting its recursive parser. >> >> This seems completely backwards. > > Never the less, it is very common in the embedded world. > Often it is more of a guideline than a rule - avoid recursion (or other loops in the call paths) unless it is clearly the best way to handle it. And like any other loops, be sure you know your limits and that the loop will exit without causing overflows. Since it is often harder to be sure that your recursion exits cleanly and safely than with an iterative loop, banning all recursion is often the safe and simple rule. But then, systems with such coding standards are seldom asked to parse XML files of unknown sizes up to possibly 10 GB.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-07-25 19:27 -0700 |
| Message-ID | <kfnoaizfyag.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #66107 |
David Brown <david.brown@hesbynett.no> writes: > On 12/07/15 22:17, Ian Collins wrote: >> Bartc wrote: >>> On 12/07/2015 11:20, Phil Carmody wrote: >>>> Bartc <bc@freeuk.com> writes: >>>>> On 10/07/2015 00:52, Andrew Cooper wrote: >>>>> >>>>>> (I am a systems programmer and biased in this area. An 8K is >>>>>> genuinely >>>>>> enough for anyone, and 4K is sufficient for the overwhelming >>>>>> majority of >>>>>> cases.) >>>>> >>>>> 8K and 4K what? Do you mean 8KB and 4KB? >>>>> >>>>> Machines now have a million times more memory than that. >>>> >>>> Which bit of "I am a systems programmer" do you not understand? >>>> >>>> 4K/8K stack limits are completely unremarkable, as is the >>>> instruction "never ever ever recurse". I remember at my >>>> previous job when we had a new security architecture imposed on >>>> us, the easiest way around it was to stack smash by exploiting >>>> its recursive parser. >>> >>> This seems completely backwards. >> >> Never the less, it is very common in the embedded world. > > Often it is more of a guideline than a rule - avoid recursion (or > other loops in the call paths) unless it is clearly the best way > to handle it. ISTM that isn't so much a rule as a meaningless platitude. > And like any other loops, be sure you know your limits and that > the loop will exit without causing overflows. > > Since it is often harder to be sure that your recursion exits > cleanly and safely than with an iterative loop, banning all > recursion is often the safe and simple rule. IME usually it's easier to verify code written using recursion rather than iteration, because it isn't necessary to reason about state changes going around the loop. In terms of stack space and potential overflow problems there, it's important to distinguish several different kinds of recursion. Recursion determined by the form of a data structure derived from outside input is usually a bad idea, lest it be used as an attack vector (or simply a bad choice of input) to make the system misbehave. Recursion that is determined by a data structure (or similar considerations) known to be well-behaved (eg, balanced trees), so upper bounds on stack use is small, eg logarithmic, and can be computed and checked; usually these are okay in systems with even modestly sized stacks, but those with very limited stack space should be vetted carefully (and recursion foregone if there is any doubt). Recursion of the tail-call-optimizable variety should be okay on any system, with the condition that the tail-call elimination has been verified; generally this should be easy to do (automatedly, if need be) by producing the generated assembly and verifying the absence of any recursive call instructions.
[toc] | [prev] | [next] | [standalone]
| From | raltbos@xs4all.nl (Richard Bos) |
|---|---|
| Date | 2015-07-13 21:16 +0000 |
| Message-ID | <55a42a72.24943625@news.xs4all.nl> |
| In reply to | #65403 |
Bartc <bc@freeuk.com> wrote: > On 12/07/2015 11:20, Phil Carmody wrote: > > Bartc <bc@freeuk.com> writes: > >> On 10/07/2015 00:52, Andrew Cooper wrote: > > >>> (I am a systems programmer and biased in this area. An 8K is genuinely > >>> enough for anyone, and 4K is sufficient for the overwhelming majority of > >>> cases.) > >> > >> 8K and 4K what? Do you mean 8KB and 4KB? > >> > >> Machines now have a million times more memory than that. > > > Which bit of "I am a systems programmer" do you not understand? > Now you're saying we should forget all that, just use static local > variables everywhere, and not use recursion if we can possibly avoid it? > All because we choose to restrict ourselves, on a 16,000,000KB machine, > to a smaller stack than a 16KB Spectrum! Yeah... so, _which_ bit of "I am a systems programmer" did you not understand? Richard
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-07-10 08:34 +0100 |
| Message-ID | <mnnsf9$vdt$1@dont-email.me> |
| In reply to | #65084 |
On 10/07/15 00:52, Andrew Cooper wrote: > On 09/07/2015 11:49, Morten W. Petersen wrote: >> However, choosing between recursion and looping is less >> obvious, to me at least. > > Never ever ever recurse. It will come back and bite you. For the same reason, you should never climb stairs, never cross the road, and never, ever, in any circumstances, board an aeroplane. Recursion /does/ bite if it gets too deep, but "too deep" is pretty darn deep. If it's likely to be a problem, add a test. > In this example, there are specific XML files which will overflow any > arbitrary stack size you choose. A sanity check will deal with the problem. Test for it. > One could argue that it might make more readable code. Some programming > languages actively encourage it as an example of elegance[1]. It does, they do, and it is so they should. > (I am a systems programmer and biased in this area. An 8K is genuinely > enough for anyone, and 4K is sufficient for the overwhelming majority of > cases.) Then you will undoubtedly see stack overflows on a regular basis, whereas those who can summon up a stack a thousand or even ten thousand times the size are far less likely to see a problem. Impossible? No, but you can guard against that. I didn't bother, though, when writing a recursive floodfill a few years ago - and guess what? Right, it has never, ever, ever crashed in the real world. (I posted the algorithm to comp.lang.c and they had it crashing in a few minutes, but that's different.) Nevertheless, because clc /did/ manage to crash it, when I eventually get around to improving that function, a sanity check for recursive depth will go in there. I've got a permutation function that recurses. If you give it a few tens of thousands if items to permute, I suppose it may well crash. On the other hand, if you give it the 26 letters of the Latin alphabet, at 10^9 permutations a second it'll take almost 130,000 millennia to run to completion (but it won't crash through recursion). > Of course, this like any rule is open to be broken. In my case, anyone > who is unable to justify why their specific use of recusion is safe in > all circumstances is not going to have their code accepted. And they won't be allowed to cross the road, either. If excess recursion is a threat, test for it. > [2] We encountered a crash at work. The crash was a stack overflow in > program written exclusively on Ocaml. After convincing the developers > in question that Ocaml (being a functional language) wasn't immune to > the practicalities of real life (a non-infinite stack), a fix was > needed. It genuinely took three of them a day crowded around a computer > and a whiteboard to alter the problematic function away from being a > plain recursive function. The purpose of the function in question was > to read data from stderr and forward it to syslog. I think that says more about Ocaml programmers than it does about recursion. :-) -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-07-10 00:46 -0700 |
| Message-ID | <695f5194-c11d-4e3e-948d-af69c4ed395d@googlegroups.com> |
| In reply to | #65091 |
On Friday, July 10, 2015 at 8:34:38 AM UTC+1, Richard Heathfield wrote: > On 10/07/15 00:52, Andrew Cooper wrote: > > > It genuinely took three of them a day crowded around a computer > > and a whiteboard to alter the problematic function away from being a > > plain recursive function. The purpose of the function in question was > > to read data from stderr and forward it to syslog. > > I think that says more about Ocaml programmers than it does about > recursion. :-) > Iteration can be expressed as recursion. So adding a list of numbers can be expressed as: if the list is empty, return 0. if the list is non empty, take away the fist member, call the add function, then add the result to the fist member, and return the result. There are some theoretical advantages in expressing computer programs that way.
[toc] | [prev] | [next] | [standalone]
| From | "Morten W. Petersen" <morphex@gmail.com> |
|---|---|
| Date | 2015-07-10 12:35 +0200 |
| Message-ID | <mno749$bf6$1@speranza.aioe.org> |
| In reply to | #65091 |
On 10.07.2015 09:34, Richard Heathfield wrote: > On 10/07/15 00:52, Andrew Cooper wrote: >> On 09/07/2015 11:49, Morten W. Petersen wrote: >>> However, choosing between recursion and looping is less >>> obvious, to me at least. >> >> Never ever ever recurse. It will come back and bite you. > > For the same reason, you should never climb stairs, never cross the > road, and never, ever, in any circumstances, board an aeroplane. > > Recursion /does/ bite if it gets too deep, but "too deep" is pretty darn > deep. If it's likely to be a problem, add a test. This is an interesting point. XML can be used for pretty much anything, I tried to think of an example of a deeply nested structure but couldn't come up with anything that couldn't (or should be) be represented in another way. But, using recursion, one relies on the stack being big enough. And it looks like there is no cross-platform way of specifying the stack size, neither is there a cross-platform way to get the stack size and current stack size used. So to be able to handle things correctly, one has to choose a recursion level that is cross-platform, and a lowest common denominator. If the stack gets too big, the results seem to be arbitrary, and there is also a possibility of security issues. If one uses looping for everything, it looks like the amount of available memory available is the limit for how deeply nested elements one can work with, and out of memory issues is something one should take in account in any case. -Morten
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-07-10 12:47 +0100 |
| Message-ID | <mnobae$g32$1@dont-email.me> |
| In reply to | #65099 |
On 10/07/15 11:35, Morten W. Petersen wrote:
<snip>
> But, using recursion, one relies on the stack being big enough. And it
> looks like there is no cross-platform way of specifying the stack size,
> neither is there a cross-platform way to get the stack size and current
> stack size used.
C offers you almost no guarantees about memory (for hosted
implementations). One of the very few guarantees you get is that you
will be able to allocate at least one object at least 32767 bytes in
size (C99 upped this to 65535, which C11 seems to be happy with). Every
time you write a program that has an object bigger than that (or two
objects of that size), you're taking a risk.
C does not specify a minimum depth for the function stack (as far as I
can tell), although we can deduce that that depth must be at least 2
(main and one child function) from other limits that the Standard
imposes. But as soon as you call a grandchild function, you're taking a
risk.
Has that ever, ever, ever caused you a problem?
> So to be able to handle things correctly, one has to choose a recursion
> level that is cross-platform, and a lowest common denominator.
And if you go the loop+homegrownstack route, you run the risk of running
out of memory /that/ way. There is no silver bullet.
> If the stack gets too big, the results seem to be arbitrary, and there
> is also a possibility of security issues.
The "stack smashing" you've heard about is not to do with the stack
growing too large. It's an exploit along these lines:
char string[32];
scanf("%s", string);
User deliberately inputs a carefully crafted string that is longer than
31 bytes, so that the return address on the program stack is overwritten
by a value of his choosing, such that control jumps to the rest of his
string, which is of course machine code for doing whatever it is he
wants to do. That's a very different matter from a stack overflow. Some
compilers do allow you to ask them to insert runtime checks for stack
overflow.
> If one uses looping for everything, it looks like the amount of
> available memory available is the limit for how deeply nested elements
> one can work with, and out of memory issues is something one should
> take in account in any case.
Yes. There's no silver bullet. Every way has its limitations. If you
reject a particular strategy because it has a possible theoretical
weakness, you end up rejecting all strategies (because they all have
possible theoretical weaknesses), and the program doesn't get written.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | "Morten W. Petersen" <morphex@gmail.com> |
|---|---|
| Date | 2015-07-10 14:29 +0200 |
| Message-ID | <mnodpu$sba$1@speranza.aioe.org> |
| In reply to | #65102 |
On 10.07.2015 13:47, Richard Heathfield wrote:
> On 10/07/15 11:35, Morten W. Petersen wrote:
[...]
> C does not specify a minimum depth for the function stack (as far as I
> can tell), although we can deduce that that depth must be at least 2
> (main and one child function) from other limits that the Standard
> imposes. But as soon as you call a grandchild function, you're taking a
> risk.
>
> Has that ever, ever, ever caused you a problem?
I guess no minimum stack etc. is as it is because C programs should be
able to run on anything?
I assume regular use is safe, I'm more worried about malicious
input such as the stack smashing below.
>> So to be able to handle things correctly, one has to choose a recursion
>> level that is cross-platform, and a lowest common denominator.
>
> And if you go the loop+homegrownstack route, you run the risk of running
> out of memory /that/ way. There is no silver bullet.
>
>> If the stack gets too big, the results seem to be arbitrary, and there
>> is also a possibility of security issues.
>
> The "stack smashing" you've heard about is not to do with the stack
> growing too large. It's an exploit along these lines:
>
> char string[32];
> scanf("%s", string);
>
> User deliberately inputs a carefully crafted string that is longer than
> 31 bytes, so that the return address on the program stack is overwritten
> by a value of his choosing, such that control jumps to the rest of his
> string, which is of course machine code for doing whatever it is he
> wants to do. That's a very different matter from a stack overflow. Some
> compilers do allow you to ask them to insert runtime checks for stack
> overflow.
Yes, OK. I've read about that and wasn't sure if exhausting the stack
was also something that could lead to security issues.
>> If one uses looping for everything, it looks like the amount of
>> available memory available is the limit for how deeply nested elements
>> one can work with, and out of memory issues is something one should
>> take in account in any case.
>
> Yes. There's no silver bullet. Every way has its limitations. If you
> reject a particular strategy because it has a possible theoretical
> weakness, you end up rejecting all strategies (because they all have
> possible theoretical weaknesses), and the program doesn't get written.
Well, controlling a loop gives control over memory usage and as someone
mentioned earlier on comp.lang.c - if you can't make memory available,
you could for example "garbage collect" or free memory that no longer
is of use.
It will also give a more usable feedback to the integrator, as a stack
exhaustion probably won't give any useable feedback.
-Morten
[toc] | [prev] | [next] | [standalone]
Page 4 of 15 — ← Prev page 1 2 3 [4] 5 6 … 15 Next page →
Back to top | Article view | comp.lang.c
csiph-web