What is recursion
Dann Corbit
> I think the subject is pretty self explanatory.
Actually off-topic here, since it is not about the C programming language.
Instead, news:comp.programming would be a more sensible lodging place for
this particular query.
Recursion is often used for solving a problem by dividing it into smaller
ones. Suppose you have some great big problem that looks hard to solve.
Why not cut the problem into chunks and solve them instead? Then look at
those solutions to find out which one is the best. Hoare's quick-sort
algorithm works like that. Pick some thing from the pile. Move the things
bigger than the one you picked into a "big things" pile. Move the things
smaller than the one you picked into a "small things" pile. So how does
that help? Do the same trick again to these two piles. Pick some thing
from the big pile. Move the things bigger than the one you picked into a
"really big things" pile. Move the things smaller than the one you picked
into a "smaller big things" pile. Do the same thing with the pile of small
things. It should be obvious that eventually, we will have piles with only
one thing in them. At this point, we will have put the set into perfect
order.
This trick is analogous to division by two. You can also divide by bigger
numbers and do hybrid techniques of all sorts.
At any rate, the gist of recursion is:
"This problem is tough -- let's make a simpler one and solve that."
The typical examples like fibonacci numbers and factorial calculation are
horrible, inefficient piles of dog-doo and they make me want to puke. I
don't think they have any purpose except that they dispense with teaching
recursion rapidly because they can be explained in 5 minutes. However, they
have no utility at all and do not express the concept in a useful context.
I think it is a disservice to teach recursion using those sort of problems
because they are better solved by iteration and far better yet by a simple
table lookup. I do think that a discussion of Ackermann's function is a
good idea because it does discuss the real bugaboo of recursion --
termination. It takes some careful analysis to make sure that recursive
routines will terminate and also that they terminate not only
mathematically, but within a reasonable period of time (feasibly).
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
Thomas A Schenck
Dann Corbit wrote:
>
> <du...@nobrain.com> wrote in message news:3858774B...@nobrain.com...
> > I think the subject is pretty self explanatory.
>
> Actually off-topic here, since it is not about the C programming language.
> Instead, news:comp.programming would be a more sensible lodging place for
> this particular query.
>
[SNIP]
Psst ... I wonder if we should tell Dann where he CROSS posted this
reply? :-)
Karl Heinz Buchegger
<du...@nobrain.com> wrote in message news:3858774B...@nobrain.com...
> I think the subject is pretty self explanatory.
>
the big trick envolved with recursion is:
Come up with strategies to
* divide your problem into simpler problems
the simpler problem is of the same type as the harder,
and you know how to combine the simpler results.
* you know how to solve the trivial problem.
The problem of moving n disc's from Base A to Base B is hard.
It would be easier if wou could move n-1 disc's from Base A
to Base C, then move 1 disc from Base A to Base B (which is trivial)
and then move n-1 discs from Base C to Base B.
What do we have in total:
a hard problem, where n discs are involved has been
replaced by
* a somewhat simpler problem of moving n-1 discs
* moving 1 disc
* moving n-1 discs again.
now how do we move n-1 discs. Easy: apply the same strategy,
this time you will have to move n-2 discs. How to do that:
the same strategy leads to a problem of moving n-3 discs.
This goes on and on until you reach a point where you have
to move n-n+1 -> 1 disc, which becomes trivial again
-----------------------------------------------------------
Karl Heinz Buchegger
kbuc...@gascad.at
David Batty
<dco...@solutionsiq.com> writes
>Recursion is often used for solving a problem by dividing it into smaller
>ones. Suppose you have some great big problem that looks hard to solve.
>Why not cut the problem into chunks and solve them instead?
This is not a good explanation of recursion, this could describe any
method of dividing a problem in to smaller solutions and is not a
definition of recursion.
Recursion is a process where a procedure calls itself repeatedly until
some limit/answer/boundary is detected. Nobody who posted a reply to
this mentioned the routine calling itself which is what recursion is.
For example it may call itself for example 100 times, when it finds an
answer or limit or whatever is set to trigger it to stop calling itself
it then returns to the procedure which called it (which was itself) and
then returns again and again until it has done 100 returns and then the
procedure has correctly 'unwound' itself.
Recursion can be used to traverse directories looking for a file, in a
directory your procedure may find more directories, it then goes in to
the first of these (by calling itself and giving this new directory as
an argument) and it then finds another directory so it then calls itself
again giving this new directory as a parameter to search, then because
there are no more directories in this one it then looks through the
files to see if the one it is supposed to find exists there. By calling
itself with a new directory to search, one procedure can look in all the
directories. If you wrote this code without recursion then you would
have great difficulty writing efficient code to do the job.
Recursion can be handy in Chess Games, File searching, Mathematical
calculations and goal seeking software amongst many other uses.
David Batty
Lawrence Kirby
da...@sectorsoftware.demon.co.uk "David Batty" writes:
>In article <8eb64.265$qj7.2232@client>, Dann Corbit
><dco...@solutionsiq.com> writes
>>Recursion is often used for solving a problem by dividing it into smaller
>>ones. Suppose you have some great big problem that looks hard to solve.
>>Why not cut the problem into chunks and solve them instead?
>
>This is not a good explanation of recursion, this could describe any
>method of dividing a problem in to smaller solutions and is not a
>definition of recursion.
The key point regarding recursion is that the smaller problems have the
same form as the larger one i.e. can be solved using the same algorithm.
There must also come a point where the problem becomes simple enough to
solve directly i.e. without further recourse to recursion.
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
karl malbrain
Lawrence Kirby <fr...@genesis.demon.co.uk> wrote in message
news:945649...@genesis.demon.co.uk...
> In article <voi2uVAu...@sectorsoftware.demon.co.uk>
> da...@sectorsoftware.demon.co.uk "David Batty" writes:
>
> >In article <8eb64.265$qj7.2232@client>, Dann Corbit
> ><dco...@solutionsiq.com> writes
> >>Recursion is often used for solving a problem by dividing it into
smaller
> >>ones. Suppose you have some great big problem that looks hard to solve.
> >>Why not cut the problem into chunks and solve them instead?
You mean INTEGRATION by parts, from ANALYTICAL GEOMETRY?
> >This is not a good explanation of recursion, this could describe any
> >method of dividing a problem in to smaller solutions and is not a
> >definition of recursion.
>
> The key point regarding recursion is that the smaller problems have the
> same form as the larger one i.e. can be solved using the same algorithm.
> There must also come a point where the problem becomes simple enough to
> solve directly i.e. without further recourse to recursion.
You're confusing PROBLEM with SOLUTION. Recursion REDUCES a SOLUTION of a
`larger' problem into smaller COMPLEXITY using the same SOLUTION, until the
answer appears as a THING-IN-ITSELF. Karl M
Lawrence Kirby
...
>> The key point regarding recursion is that the smaller problems have the
>> same form as the larger one i.e. can be solved using the same algorithm.
>> There must also come a point where the problem becomes simple enough to
>> solve directly i.e. without further recourse to recursion.
>
>You're confusing PROBLEM with SOLUTION. Recursion REDUCES a SOLUTION of a
>`larger' problem into smaller COMPLEXITY using the same SOLUTION, until the
>answer appears as a THING-IN-ITSELF. Karl M
I'm not confusing anything, it is quite possible for recursion to
be part of a problem definition and/or part of the specification
and implementation of a solution.
Dann Corbit
> In article <itv74.33$ue.1...@nntp1-sf.pbi.net> kar...@acm.org writes:
>
> ...
>
> >> The key point regarding recursion is that the smaller problems have the
> >> same form as the larger one i.e. can be solved using the same
algorithm.
> >> There must also come a point where the problem becomes simple enough to
> >> solve directly i.e. without further recourse to recursion.
> >
> >You're confusing PROBLEM with SOLUTION. Recursion REDUCES a SOLUTION of
a
> >`larger' problem into smaller COMPLEXITY using the same SOLUTION, until
the
> >answer appears as a THING-IN-ITSELF. Karl M
>
> I'm not confusing anything, it is quite possible for recursion to
> be part of a problem definition and/or part of the specification
> and implementation of a solution.
Pedagogic example:
Ackermann's function.
The definition is clearly recursive. It may somehow be possible to turn it
into iteration, but I have never seen anything but a recursive
implementation. I suspect it would be very difficult to create one. Maybe
Karl can make one for us.
The same is true of many real-life (non-contrived) examples.
Tak-Shing Chan
I love recursion! While we are still at Ackerman functions:
/*
* From the BRAIN DAMAGED (TM) Exam Library Version 0.1
*
* Print this out using obscure fonts, and put this in a test
* that asks the poor student to give the output for a(3, 3).
* Access to computers is not allowed. Assume non-ANSI C which
* allows the use of underscores as variable names.
*/
#define _ 1
int a(int __, int ___)
{
return !__?___+_:!___?a(__-_,_):a(__-_,a(__,___-_));
China Blue Blood
/ > into iteration, but I have never seen anything but a recursive
/ > implementation. I suspect it would be very difficult to create one. Maybe
/ > Karl can make one for us.
Correct definition?
A = \(mn).[
m=0 -> n+1
m/=0 ^ n=0 -> A(m-1,1)
m/=0 ^ n/=0 -> A(m-1,A(m,n-1))
]
I don't remember.
Create an empty extensible function A (ig est, a hash table).
Create a stack with one element (m,n).
while stack is not empty,
pop stack -> (m,n)
if A(m,n) does not exist,
if m=0,
map A(m,n) -> n+1
else if n=0,
if A(m-1,1) does exist,
push (m,n) on the stack
push (m-1,n) on the stack
else
map A(m,n) -> A(m-1,1)
else
if A(m,n-1) does not exist,
push (m,n) on the stack
push (m,n-1) on the stack
else if A(m-1,A(m,n-1)) does not exist,
push (m,n) on the stack
push (m-1,A(m,n-1)) on the stack
else
map A(m,n) -> A(m-1,A(m,n-1))
return A(m,n)
--
CACS: Collective Against Consensual Sanity v0.123
Now a text site map! http://www.angelfire.com/ca3/cacs/
pretty? http://www.geocities.com/SoHo/Studios/5079/
There is no sanctuary. I am an Andrea Chen plush toy.
Andy L
<0nz74.1499$pf1.2784@client>:
>Ackermann's function.
>
>The definition is clearly recursive. It may somehow be possible to
>turn it into iteration, but I have never seen anything but a
>recursive implementation. I suspect it would be very difficult to
>create one. Maybe Karl can make one for us.
>
Sorry to veer OT ...
When you speak of converting recursion to iteration, do you mean
without using stacks? I ask because I thought any recursive function
can be expressed as an iterative one by just using stacks explicitly,
rather than using the function environment on the compilers run-time
stack. Ie one essentially does part-of what the compiler was doing
before. So logically, I guess it is still "recursive", that is
"defined in terms of itself", but by managing the stack oneself,
it is more efficient. If this is the case, what is the definition of
iterative?
Regards,
Andy L
Dann Corbit
news:8EA3768C4lor...@127.0.0.1...
In my view, an explicit stack instead of an implicit stack is _still_
recursion. It just means that *you* are playing the compiler. You have not
changed the form of the algorithm at all. Here are three different
algorithms for computation of factorial. One uses lookup, one uses
iteration, and one uses recursion:
static const double factorials[] =
{
1.,
1.,
2.,
6.,
24.,
120.,
720.,
5040.,
40320.,
362880.,
3628800.,
39916800.,
479001600.,
6227020800.,
87178291200.,
1307674368000.,
20922789888000.,
355687428096000.,
6402373705728000.,
121645100408832000.,
2432902008176640000.,
51090942171709440000.,
1.1240007277776077e+021,
2.5852016738884978e+022,
6.2044840173323941e+023,
1.5511210043330986e+025,
4.0329146112660565e+026,
1.0888869450418352e+028,
3.0488834461171387e+029,
8.8417619937397019e+030,
2.6525285981219107e+032,
8.2228386541779224e+033,
2.6313083693369352e+035,
8.6833176188118859e+036,
2.9523279903960416e+038,
1.0333147966386145e+040,
3.7199332678990125e+041,
1.3763753091226346e+043,
5.2302261746660112e+044,
2.0397882081197444e+046,
8.1591528324789768e+047,
3.3452526613163808e+049,
1.4050061177528800e+051,
6.0415263063373834e+052,
2.6582715747884489e+054,
1.1962222086548019e+056,
5.5026221598120892e+057,
2.5862324151116818e+059,
1.2413915592536073e+061,
6.0828186403426752e+062,
3.0414093201713376e+064,
1.5511187532873822e+066,
8.0658175170943877e+067,
4.2748832840600255e+069,
2.3084369733924138e+071,
1.2696403353658276e+073,
7.1099858780486348e+074,
4.0526919504877214e+076,
2.3505613312828785e+078,
1.3868311854568984e+080,
8.3209871127413899e+081,
5.0758021387722484e+083,
3.1469973260387939e+085,
1.9826083154044401e+087,
1.2688693218588417e+089,
8.2476505920824715e+090,
5.4434493907744307e+092,
3.6471110918188683e+094,
2.4800355424368305e+096,
1.7112245242814130e+098,
1.1978571669969892e+100,
8.5047858856786230e+101,
6.1234458376886085e+103,
4.4701154615126844e+105,
3.3078854415193862e+107,
2.4809140811395400e+109,
1.8854947016660504e+111,
1.4518309202828587e+113,
1.1324281178206297e+115,
8.9461821307829757e+116,
7.1569457046263806e+118,
5.7971260207473678e+120,
4.7536433370128420e+122,
3.9455239697206588e+124,
3.3142401345653532e+126,
2.8171041143805501e+128,
2.4227095383672734e+130,
2.1077572983795279e+132,
1.8548264225739844e+134,
1.6507955160908460e+136,
1.4857159644817615e+138,
1.3520015276784029e+140,
1.2438414054641308e+142,
1.1567725070816416e+144,
1.0873661566567431e+146,
1.0329978488239059e+148,
9.9167793487094965e+149,
9.6192759682482120e+151,
9.4268904488832480e+153,
9.3326215443944153e+155,
9.3326215443944151e+157,
9.4259477598383599e+159,
9.6144667150351271e+161,
9.9029007164861805e+163,
1.0299016745145628e+166,
1.0813967582402910e+168,
1.1462805637347084e+170,
1.2265202031961380e+172,
1.3246418194518290e+174,
1.4438595832024937e+176,
1.5882455415227430e+178,
1.7629525510902446e+180,
1.9745068572210740e+182,
2.2311927486598138e+184,
2.5435597334721877e+186,
2.9250936934930160e+188,
3.3931086844518981e+190,
3.9699371608087211e+192,
4.6845258497542909e+194,
5.5745857612076058e+196,
6.6895029134491271e+198,
8.0942985252734441e+200,
9.8750442008336011e+202,
1.2146304367025329e+205,
1.5061417415111409e+207,
1.8826771768889261e+209,
2.3721732428800469e+211,
3.0126600184576594e+213,
3.8562048236258041e+215,
4.9745042224772875e+217,
6.4668554892204741e+219,
8.4715806908788206e+221,
1.1182486511960043e+224,
1.4872707060906857e+226,
1.9929427461615188e+228,
2.6904727073180504e+230,
3.6590428819525489e+232,
5.0128887482749920e+234,
6.9177864726194886e+236,
9.6157231969410894e+238,
1.3462012475717526e+241,
1.8981437590761709e+243,
2.6953641378881629e+245,
3.8543707171800731e+247,
5.5502938327393044e+249,
8.0479260574719917e+251,
1.1749972043909107e+254,
1.7272458904546389e+256,
2.5563239178728654e+258,
3.8089226376305698e+260,
5.7133839564458547e+262,
8.6272097742332400e+264,
1.3113358856834524e+267,
2.0063439050956823e+269,
3.0897696138473508e+271,
4.7891429014633941e+273,
7.4710629262828942e+275,
1.1729568794264145e+278,
1.8532718694937350e+280,
2.9467022724950384e+282,
4.7147236359920616e+284,
7.5907050539472190e+286,
1.2296942187394494e+289,
2.0044015765453026e+291,
3.2872185855342959e+293,
5.4239106661315887e+295,
9.0036917057784375e+297,
1.5036165148649991e+300,
2.5260757449731984e+302,
4.2690680090047051e+304,
7.2574156153079990e+306
};
double
table_factorial (unsigned n)
{
if (n < sizeof factorials / sizeof factorials[0])
return factorials[n];
return -1.;
}
double
iterative_factorial (unsigned n)
{
unsigned p;
double answer = 1;
for (p = 0; p <= n; p++)
{
if (p == 0)
answer = 1;
else
answer *= p;
}
return answer;
}
double
recursive_factorial (unsigned input)
{
double d = input;
if (input <= 1)
return 1;
return d * recursive_factorial (--input);
}
#ifdef UNIT_TEST
#include <stdio.h>
int
main (void)
{
unsigned i;
for (i = 0; i < 171; i++)
{
printf ("%u %30.20e %30.20e %30.20e\n",
i,
table_factorial (i),
iterative_factorial (i),
recursive_factorial (i)
);
}
}
#endif
karl malbrain
Dann Corbit <dco...@solutionsiq.com> wrote in message
news:0nz74.1499$pf1.2784@client...
> "Lawrence Kirby" <fr...@genesis.demon.co.uk> wrote in message
> news:945730...@genesis.demon.co.uk...
> > In article <itv74.33$ue.1...@nntp1-sf.pbi.net> kar...@acm.org writes:
> >
> > ...
> >
> > >> The key point regarding recursion is that the smaller problems have
the
> > >> same form as the larger one i.e. can be solved using the same
> algorithm.
> > >> There must also come a point where the problem becomes simple enough
to
> > >> solve directly i.e. without further recourse to recursion.
> > >
> > >You're confusing PROBLEM with SOLUTION. Recursion REDUCES a SOLUTION
of
> a
> > >`larger' problem into smaller COMPLEXITY using the same SOLUTION, until
> the
> > >answer appears as a THING-IN-ITSELF. Karl M
> >
> > I'm not confusing anything, it is quite possible for recursion to
> > be part of a problem definition and/or part of the specification
> > and implementation of a solution.
>
> Pedagogic example:
>
>
> The definition is clearly recursive. It may somehow be possible to turn
it
> into iteration, but I have never seen anything but a recursive
> implementation. I suspect it would be very difficult to create one.
Maybe
> Karl can make one for us.
To explain the difference between PROBLEM and SOLUTION, why don't we start
with something simpler, the SUCCESSOR FUNCTION. You probably think of it
being defined RECURSIVELY.
About 200 years ago it was becaming obvious that while nature REPRODUCED
through MULTIPLICATION and RE-DIVISION, the distribution of wealth was
LINEAR. What are the founders of Microsoft less one IOTA? The SAME thing
they were before, too wealthy to count. What's one temporary programmer at
the end of a Microsoft `Job'? Replaced by the NEXT ONE.
Does this make ANY sense, what-so-ever?? Karl M
Dann Corbit
news:3859AF83...@gateway.net...
>
>
> Dann Corbit wrote:
> >
> > <du...@nobrain.com> wrote in message
news:3858774B...@nobrain.com...
> > > I think the subject is pretty self explanatory.
> >
language.
> > Instead, news:comp.programming would be a more sensible lodging place
for
> > this particular query.
> >
>
> [SNIP]
>
> Psst ... I wonder if we should tell Dann where he CROSS posted this
> reply? :-)
No need, the cross-post was mine and intentional.
m...@here.com
> dco...@solutionsiq.com (Dann Corbit) wrote in
> <0nz74.1499$pf1.2784@client>:
>>Ackermann's function.
>>
>>The definition is clearly recursive. It may somehow be possible to
>>turn it into iteration, but I have never seen anything but a
>>recursive implementation. I suspect it would be very difficult to
>>create one. Maybe Karl can make one for us.
>>
> Sorry to veer OT ...
> When you speak of converting recursion to iteration, do you mean
> without using stacks? I ask because I thought any recursive function
> can be expressed as an iterative one by just using stacks explicitly,
> rather than using the function environment on the compilers run-time
> stack. Ie one essentially does part-of what the compiler was doing
> before. So logically, I guess it is still "recursive", that is
> "defined in terms of itself", but by managing the stack oneself,
> it is more efficient. If this is the case, what is the definition of
> iterative?
One can usually turn recursive routines into iterative ones
without using stacks. The resulting source code is usually
longer and sometimes harder to understand.
Mark McIntyre
wrote:
>
>To explain the difference between PROBLEM and SOLUTION, why don't we start
>with something simpler, the SUCCESSOR FUNCTION. You probably think of it
>being defined RECURSIVELY.
>
>About 200 years ago it was becaming obvious that while nature REPRODUCED
>through MULTIPLICATION and RE-DIVISION, the distribution of wealth was
>LINEAR. What are the founders of Microsoft less one IOTA? The SAME thing
>they were before, too wealthy to count. What's one temporary programmer at
>the end of a Microsoft `Job'? Replaced by the NEXT ONE.
>
>Does this make ANY sense, what-so-ever?? Karl M
>
Karl one thing which would make sense would be if you stopped
pointlessly capitalizing words. Every email you send contains
capitalized words and they serve no useful purpose.
Also while your posts may be interesting in comp.programming they have
zero relevance to comp.lang.c. Can I suggest that you take them off
clc?
Mark McIntyre
Lawrence Kirby
lo...@bigfoot.com "Andy L" writes:
>dco...@solutionsiq.com (Dann Corbit) wrote in
><0nz74.1499$pf1.2784@client>:
>
>>Ackermann's function.
>>
>>The definition is clearly recursive. It may somehow be possible to
>>turn it into iteration, but I have never seen anything but a
>>recursive implementation. I suspect it would be very difficult to
>>create one. Maybe Karl can make one for us.
>>
>
>Sorry to veer OT ...
>
>When you speak of converting recursion to iteration, do you mean
>without using stacks?
The implementation of a recursively defined problem can be done
using some form of LIFO datastructure, and LIFO datastructures
are often referred to as stacks. Many recursive problems inherently
require a degree of state to be held such that you can't eliminate
this.
>I ask because I thought any recursive function
>can be expressed as an iterative one by just using stacks explicitly,
>rather than using the function environment on the compilers run-time
>stack. Ie one essentially does part-of what the compiler was doing
>before.
For something to be recursive you need a level of abstraction or
support for recursion in the underlying language: you need to have
the capability of defining an entity that you can refer to recursively.
C endows the function with this capability, also C's type system
has this capability and through structures, unions and pointers allows
you to define recursive datastructures. Other languages don't allow
this, e.g. Fortran 77 (I'm not familiar enough with Fortran 90 to say).
Machine code generally doesn't support recursion, at least not on
typical architectures, the building blocks (instructions) are far too
basic to encompass such a notion. You can of course simulate stacks
and other datastructures in machine code. When you compile a
recursive program to machine code you are effectively converting it
to a non-recursive (iterative if you like) form.
>So logically, I guess it is still "recursive", that is
>"defined in terms of itself", but by managing the stack oneself,
But it isn't defined in terms of itself. It is defined in terms of
a executing number of discrete operations (none of which are
remotely recursive: loading values, storing values, incrementing and
decrementing values that are used as addresses etc.) which produce the
desired results. You may be able to apply a level of abstraction in
describing the code i.e. by creating an artificial framework: define
a group of instructions as an abstract unit, define an interface and
conclude that code within the unit makes calls to that interface. However
that is artificial, it isn't inherent in the code. In C functions are
a fundamental part of the language and inherently support recursion.
In machine code generally the best you can do is simulate a set of
operations that look like recursion when you stand back from them
and try to apply a level of abstraction.
>it is more efficient. If this is the case, what is the definition of
>iterative?
True iteration is essentially specifying a problem by a series of
ordered steps. For the purposes of this discussion it means
little more than something that isn't recursive.
edw...@entropic.co.uk
> About 200 years ago it was becaming obvious that while nature
> REPRODUCED through MULTIPLICATION and RE-DIVISION, the distribution
> of wealth was LINEAR. What are the founders of Microsoft less one
> IOTA? The SAME thing they were before, too wealthy to count.
> What's one temporary programmer at the end of a Microsoft `Job'?
> Replaced by the NEXT ONE.
> Does this make ANY sense, what-so-ever?? Karl M
Sadly, no.
Regards,
--
Edwin Young
James Hu
<fr...@genesis.demon.co.uk> wrote:
>Machine code generally doesn't support recursion, at least not on
>typical architectures, the building blocks (instructions) are far too
>basic to encompass such a notion. You can of course simulate stacks
>and other datastructures in machine code.
This is only true for those machine codes that do not directly support
the "call subroutine" instruction (and many modern CPUs do). This
instruction will implicitly store the current value of the instruction
pointer for you so that a "return" from the subroutine will
automatically take you back to the point in the code at which the
subroutine was called. If a subroutine issues a "call subroutine"
using its own entry point as the argument, then I don't see how that
can be interpreted as anything but recursion.
--
James C. Hu <j...@cs.wustl.edu> Computer Science Doctoral Candidate
http://www.cs.wustl.edu/~jxh/ Washington University in Saint Louis
>>>>>>>>>>>>> I use *SpamBeGone* <URL:http://www.internz.com/SpamBeGone/>
Lawrence Kirby
kar...@acm.org "karl malbrain" writes:
...
>About 200 years ago it was becaming obvious that while nature REPRODUCED
>through MULTIPLICATION and RE-DIVISION, the distribution of wealth was
>LINEAR. What are the founders of Microsoft less one IOTA? The SAME thing
>they were before, too wealthy to count. What's one temporary programmer at
>the end of a Microsoft `Job'? Replaced by the NEXT ONE.
Arfle Barfle Gloop?
>Does this make ANY sense, what-so-ever?? Karl M
You already know the answer to that.
Malcolm
fr...@genesis.demon.co.uk (Lawrence Kirby) wrote:
> In article <8EA3768C4lor...@127.0.0.1>
> lo...@bigfoot.com "Andy L" writes:
> >dco...@solutionsiq.com (Dann Corbit) wrote in
> ><0nz74.1499$pf1.2784@client>:
> >
> Machine code generally doesn't support recursion, at
> least not on
> typical architectures, the building blocks
> (instructions) are far too
> basic to encompass such a notion. You can of course
> simulate stacks
> and other datastructures in machine code. When you
> compile a
> recursive program to machine code you are effectively
> converting it
> to a non-recursive (iterative if you like) form.
A machine cannot generate a truly recursive function
because no known physical structure is actually recursive.
There always has to be some stack somewhere, so recursion
will always stop at some point.
(Interestingly, some people speculate that the Universe is
in fact a black hole. There may be a recursive structure to
the cosmos, so if Hawking is right and it is possible to
get data out of black holes ...)
A lot of machines do provide a call-subroutine instruction,
but obviously this is only making the CPU do the work of
updating the call stack.
God is also recursive. "I am who I am" is a classic
recursive definition.
> -----------------------------------------
> Lawrence Kirby | fr...@genesis.demon.co.uk
> Wilts, England | 7073...@compuserve.com
> -----------------------------------------
* Sent from AltaVista http://www.altavista.com Where you can also find related Web Pages, Images, Audios, Videos, News, and Shopping. Smart is Beautiful
raw...@my-deja.com
j...@cs.wustl.edu wrote:
> On Wed, 22 Dec 99 02:41:54 GMT, Lawrence Kirby
> <fr...@genesis.demon.co.uk> wrote:
> >typical architectures, the building blocks (instructions) are far too
> >basic to encompass such a notion. You can of course simulate stacks
> >and other datastructures in machine code.
>
> the "call subroutine" instruction (and many modern CPUs do). This
> instruction will implicitly store the current value of the instruction
> pointer for you so that a "return" from the subroutine will
> automatically take you back to the point in the code at which the
> subroutine was called. If a subroutine issues a "call subroutine"
> using its own entry point as the argument, then I don't see how that
> can be interpreted as anything but recursion.
But the point of the argument is that the subroutine isn't really an
entity that is defined in the machine code; the code of several
subroutines might be intermingled, for example. And if recursion
means that an entity (like a subroutine) is defined partly in terms
of itself, the machine code entities (individual instructions) are
thus too simple to support recursion.
On the other hand, one can consistently treat function definitions
in C as simply associating the function entry point with the function
name, since the distinction between a function and a pointer to the
function is not very significant; a similar argument would then seem
to apply. (If a C function calls itself through a function pointer
variable, is it recursive? Does it cease to be recursive if the
value of that variable changes?)
And one could imagine a machine code which actually enforced some
sort of partitioning into functions, perhaps requiring each
subroutine to be in a separate segment and to be called at a single
entry point through some segment descriptor list; the Intel 386
permits something along these lines in protected mode.
From yet another point of view, you can consider that each instruction
of a machine code program is an entity whose behavior is defined in
terms of what its opcode/arguments do plus the behavior of its
possible successor instruction(s); then any instruction in a loop
is recursive, since after unraveling the definition of its behavior,
we discover that it is partly defined in terms of ... its own
behavior (when the loop returns to that same instruction). (In
some cases, this would actually amount to reversing the tail
recursion optimization that produced a loop from compiling a
recursive function definition.)
I prefer to use "recursive" to mean "computable", or "computable
total function", in fine mathematical tradition, since it permits
me to rise above the whole mess.
--
MJSR
Sent via Deja.com http://www.deja.com/
Before you buy.
Lawrence Kirby
j...@cs.wustl.edu "James Hu" writes:
>On Wed, 22 Dec 99 02:41:54 GMT, Lawrence Kirby
><fr...@genesis.demon.co.uk> wrote:
>>Machine code generally doesn't support recursion, at least not on
>>typical architectures, the building blocks (instructions) are far too
>>basic to encompass such a notion. You can of course simulate stacks
>>and other datastructures in machine code.
>
>This is only true for those machine codes that do not directly support
>the "call subroutine" instruction (and many modern CPUs do). This
>instruction will implicitly store the current value of the instruction
>pointer for you so that a "return" from the subroutine will
>automatically take you back to the point in the code at which the
>subroutine was called. If a subroutine issues a "call subroutine"
>using its own entry point as the argument, then I don't see how that
>can be interpreted as anything but recursion.
Recursion is defining a problem interms of simpler forms of the same
problem with ultimately a termination condition. If I say
f(0) = 1
f(x) = x * f(x-1)
then that is a recursive definition. If I say
f(x) = f(x)
then that is a meaningless definition. I suppose you could call it recursive
in some sense if you wanted to (I wouldn't) but it isn't really helpful.
For something to be recursive and not degenerate you need some sort of
per-invocation input parameters and usually independent internal state
(though not necessarily for tail recursive code). Normal JSR/BSR type
instructions don't have these basic characteristics although it is
not impossible to create an architecture that might be considered
to support recursion. That's more of a CISC than a RISC approach though.
--
Lawrence Kirby
donald.mcl...@talk21.com.invalid "Malcolm" writes:
...
>A machine cannot generate a truly recursive function
>because no known physical structure is actually recursive.
>There always has to be some stack somewhere, so recursion
>will always stop at some point.
It depends on whether the details (and indeed existence of the
stack are visible or hidden at the level of abstraction you
are working at. At the C source level the function call
and auto variable creating mechanism is not explicit and
it creates a level of abstraction that supports the
concept of recursion. At the machine code level instructions
are usually defined in terms of exactly ehat bits get moved where
what registers get incremented, decremented and so on. This
is too low a level to apply the concept of recursion.
>(Interestingly, some people speculate that the Universe is
>in fact a black hole. There may be a recursive structure to
>the cosmos, so if Hawking is right and it is possible to
>get data out of black holes ...)
>A lot of machines do provide a call-subroutine instruction,
>but obviously this is only making the CPU do the work of
>updating the call stack.
>God is also recursive. "I am who I am" is a classic
>recursive definition.
But a degenerate and essentially meaningless one (at least from a
scientific/mathematical/computational point of view, I've no
desire to tread on religious feet!).
James Hu
<fr...@genesis.demon.co.uk> wrote:
>In article <slrn861u6...@jamespc.ungerhu.com>
> j...@cs.wustl.edu "James Hu" writes:
>>If a subroutine issues a "call subroutine" using its own entry point
>>as the argument, then I don't see how that can be interpreted as
>>anything but recursion.
>Recursion is defining a problem interms of simpler forms of the same
>problem with ultimately a termination condition.
That is too restrictive a definition. For one thing, recursion is not
required to be associated with a "problem". Also, recursion does not
require a termination condition anymore than a loop requires one. The
expansion of the acronym GNU is recursion that is not associated with
a problem and for which there is no termination condition.
>If I say
>
> f(0) = 1
> f(x) = x * f(x-1)
>
>then that is a recursive definition.
Yes.
>If I say
>
> f(x) = f(x)
>
>then that is a meaningless definition.
No, it is not meaningless. It is a tautology.
>I suppose you could call it recursive in some sense if you wanted to
>(I wouldn't) but it isn't really helpful.
Then you wouldn't consider this recursive either?
f(x) = 1 + 1/(1 + f(x))
If you follow the recursive definition, you will find that:
1
f(x) = 1 + -----------------
1
2 + -------------
1
2 + ---------
1
2 + -----
.
2 + .
.
Although the problem is not defined as a simpler version of itself (it
is identical), and there is no termination condition, the recursive
definition itself is still well defined.
>For something to be recursive and not degenerate you need some sort of
>per-invocation input parameters and usually independent internal state
>(though not necessarily for tail recursive code).
You are assuming that recursively defined subroutines can not have any
side effects.
"call subroutine" maintains independent internal state in that it
knows how to get back to the caller. In principle, any other state
can be globals that are initialized outside the context of the
recursive subroutine.
Oh, this is crossposted to comp.lang.c, so ...
ObC:
#include <stdio.h>
#include <math.h>
#include <float.h>
typedef struct continued_fraction
{
int x;
struct continued_fraction *next;
}
continued_fraction;
static continued_fraction two = { 2, &two };
static continued_fraction one = { 1, &two };
static continued_fraction *sqrt_2 = &one;
static double
evaluate_r (continued_fraction *cf, double P, double Q, double Pp, double Qp)
{
if (1 < (Q * DBL_EPSILON) * Qp)
return P/Q;
return evaluate_r (cf->next, cf->x * P + Pp, cf->x * Q + Qp, P, Q);
}
static double
evaluate (continued_fraction *cf)
{
return evaluate_r (cf, 1, 0, 0, 1);
}
int
main (void)
{
printf ("%f\n%f\n", evaluate (sqrt_2), sqrt (2));
return 0;
karl malbrain
James Hu <j...@cs.wustl.edu> wrote in message
news:slrn861u6...@jamespc.ungerhu.com...
> On Wed, 22 Dec 99 02:41:54 GMT, Lawrence Kirby
> <fr...@genesis.demon.co.uk> wrote:
> >Machine code generally doesn't support recursion, at least not on
> >typical architectures, the building blocks (instructions) are far too
> >basic to encompass such a notion. You can of course simulate stacks
> >and other datastructures in machine code.
>
> This is only true for those machine codes that do not directly support
> the "call subroutine" instruction (and many modern CPUs do). This
> instruction will implicitly store the current value of the instruction
> pointer for you so that a "return" from the subroutine will
> automatically take you back to the point in the code at which the
> using its own entry point as the argument, then I don't see how that
> can be interpreted as anything but recursion.
The results of machine codes are analyzed MATERIALLY as concrete
things-in-themselves. The machine code for the SUCCESSOR FUNCTION is
INCREMENT. The other machine code at the heart of a RECURSIVE SOLUTION is
GOTO. Karl M
Quanyi Sun
Tak-Shing Chan wrote:
> I love recursion! While we are still at Ackerman functions:
Remember recursion IS expensive if you know how a function/program
is executed by computer. My advice is to avoid recursion if you can.
> /*
> * From the BRAIN DAMAGED (TM) Exam Library Version 0.1
> *
> * Print this out using obscure fonts, and put this in a test
> * that asks the poor student to give the output for a(3, 3).
> * Access to computers is not allowed. Assume non-ANSI C which
> * allows the use of underscores as variable names.
> */
>
> #define _ 1
>
> int a(int __, int ___)
> {
> return !__?___+_:!___?a(__-_,_):a(__-_,a(__,___-_));
> }
If you write C codes in such a style, you will sooner or later be fired.
> On Mon, 20 Dec 1999, Dann Corbit wrote:
>
> > "Lawrence Kirby" <fr...@genesis.demon.co.uk> wrote in message
> > news:945730...@genesis.demon.co.uk...
> > > In article <itv74.33$ue.1...@nntp1-sf.pbi.net> kar...@acm.org writes:
> > >
> > > ...
> > >
> > > >> The key point regarding recursion is that the smaller problems have the
> > > >> same form as the larger one i.e. can be solved using the same
> > algorithm.
> > > >> There must also come a point where the problem becomes simple enough to
> > > >> solve directly i.e. without further recourse to recursion.
> > > >
> > > >You're confusing PROBLEM with SOLUTION. Recursion REDUCES a SOLUTION of
> > a
> > > >`larger' problem into smaller COMPLEXITY using the same SOLUTION, until
> > the
> > > >answer appears as a THING-IN-ITSELF. Karl M
> > >
> > > I'm not confusing anything, it is quite possible for recursion to
> > > be part of a problem definition and/or part of the specification
> > > and implementation of a solution.
> >
> > Pedagogic example:
> >
> > Ackermann's function.
> >
> > The definition is clearly recursive. It may somehow be possible to turn it
> > into iteration, but I have never seen anything but a recursive
> > implementation. I suspect it would be very difficult to create one. Maybe
> > Karl can make one for us.
> >
> > The same is true of many real-life (non-contrived) examples.
> > --
> > C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> > "The C-FAQ Book" ISBN 0-201-84519-9
> > C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
> > C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
Quanyi Sun
Tak-Shing Chan
> Remember recursion IS expensive if you know how a function/program
> is executed by computer. My advice is to avoid recursion if you can.
How to remove recursion from Ackerman function without using an
explicit stack? Please enlighten me on this.
> If you write C codes in such a style, you will sooner or later be fired.
This is a false statement. What if the job has *nothing* to do
with C (e.g. musician, animator, DBA, HR director, etc.)?
Karl Heinz Buchegger
Quanyi Sun wrote:
>
> Remember recursion IS expensive if you know how a function/program
> is executed by computer. My advice is to avoid recursion if you can.
>
Bad advice.
Better advice: learn to use recursion to your benefit.
Remember: the teaching examples (factorial, fibonacci, ...)
have little to do with real world recursive problems. In
real world you seldom have the choice to transform a
recursive problem (which can be solved easily recursive)
into an iterative version.
So better learn to work with recursions.
-----------------------------------------------------------
Karl Heinz Buchegger
kbuc...@gascad.at