I know that, in computation theory, there are certain functions which
can only be computed with recursion. I cannot understand why.
If f(x) is defined over a finite domain X, we can always compute f(x)
by using a simple lookup table, without any recursion.
If the domain X is infinite, than I think we need recursion for any
nontrivial function. For instance, take f(x,y) = x + y. To calculate
that, we need to recurse over y in some way (either breaking y down by
its digits, or incrementing x y times). Even f(x) = x + 1 requires us
to recurse over all of x digits, until we find a non-9 digit, if we
want to represent the value in any non-unary base.
On Jul 15, 10:42 am, "S. Robert James" <············@gmail.com> wrote:
> I know that, in computation theory, there are certain functions which
> can only be computed with recursion. I cannot understand why.
>
> If f(x) is defined over a finite domain X, we can always compute f(x)
> by using a simple lookup table, without any recursion.
>
> If the domain X is infinite, than I think we need recursion for any
> nontrivial function. For instance, take f(x,y) = x + y. To calculate
> that, we need to recurse over y in some way (either breaking y down by
> its digits, or incrementing x y times). Even f(x) = x + 1 requires us
> to recurse over all of x digits, until we find a non-9 digit, if we
> want to represent the value in any non-unary base.
Can someone help me out here? I'm sure I'm just making a basic
mistake, but I'd really like some help to get me started...
>>>>> "SRJ" == S Robert James <············@gmail.com> writes:
SRJ> I know that, in computation theory, there are certain
SRJ> functions which can only be computed with recursion. I
SRJ> cannot understand why.
Because what you know is wrong: iteration and recursion are
computationally equivalent. If you can express an algorithm
iteratively, you can express it recursively, and vice versa; the
principal difference is that you can maintain some state implicitly in
a recursive expression of the algorithm, but you must maintain all the
state explicitly in an iterative expression of the algorithm.
Charlton
--
Charlton Wilbur
·······@chromatico.net
On Jul 15, 8:09 pm, Charlton Wilbur <·······@chromatico.net> wrote:
> Because what you know is wrong: iteration and recursion are
> computationally equivalent. If you can express an algorithm
> iteratively, you can express it recursively, and vice versa; the
> principal difference is that you can maintain some state implicitly in
> a recursive expression of the algorithm, but you must maintain all the
> state explicitly in an iterative expression of the algorithm.
As a note to this, it's worth noting that not all processors actually
have instructions which support recursion directly. Instead, code for
them typically maintains various stacks itself. It's reasonably
obvious how you compile recursive code for such a system, which helps
to make it clear that the two ideas are actually equivalent.
The RCA 1802 is a well-known example (well-known to me, anyway, since
I wrote code for it...)
--tim
[Topic drift alert...]
Tim Bradshaw <··········@tfeb.org> wrote:
+---------------
| Charlton Wilbur <·······@chromatico.net> wrote:
| > Because what you know is wrong: iteration and recursion are
| > computationally equivalent. If you can express an algorithm
| > iteratively, you can express it recursively, and vice versa; the
| > principal difference is that you can maintain some state implicitly in
| > a recursive expression of the algorithm, but you must maintain all the
| > state explicitly in an iterative expression of the algorithm.
|
| As a note to this, it's worth noting that not all processors actually
| have instructions which support recursion directly. Instead, code for
| them typically maintains various stacks itself. It's reasonably
| obvious how you compile recursive code for such a system, which helps
| to make it clear that the two ideas are actually equivalent.
|
| The RCA 1802 is a well-known example (well-known to me, anyway, since
| I wrote code for it...)
+---------------
And the DEC PDP-8 [for which I wrote lots of code], which was
particularly nasty in that regard in having only one main data
register ("the accumulator" a.k.a. "AC"), and in having as its
only subroutine call an instruction ("JMS") which wrote the value
of the return PC into the *target* subroutine address!! [Yes, this
means that PDP-8 program code must (usually) be write-enabled!]
See <http://www.cs.uiowa.edu/~jones/pdp8/refcard/74.html> and
<http://www.cs.uiowa.edu/~jones/pdp8/man/>.
Nevertheless, very small amounts of macro hackery [together with
a couple of *small* utility subroutines] sufficed to provide the
PDP-8 assembly-language programmer with software-managed stacks,
so that instead of this:
...
JMS FOO / call FOO
...
and this:
FOO: 0 / reserve space to store return PC
...[body of FOO]...
JMP I FOO / return by jumping indirect through entry loc.
one could write this [patterned on the PDP-10 instructions
of the same names]:
...
PUSHJ / call FOO: Push return address on stack then JMP.
FOO
...
and this:
FOO: ...[body of FOO]...
POPJ / return by popping ret. PC off stack then JMP I.
Said another way, despite having no hardware stacks at all,
people were neverthless quite successful at getting Fortran,
Algol [both Algol-60 and an emulation of BALGOL (Burroughs Algol,
the systems-programminbg langauge of the B5500)], MUMPS, FOCAL,
DIBOL (a subset of COBOL), and a bunch of other languages to
run just fine on a PDP-8.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Thomas A. Russ
Subject: Re: Understanding why Recursion is necessary
Date:
Message-ID: <ymiodibn9w4.fsf@sevak.isi.edu>
Charlton Wilbur <·······@chromatico.net> writes:
> >>>>> "SRJ" == S Robert James <············@gmail.com> writes:
>
> SRJ> I know that, in computation theory, there are certain
> SRJ> functions which can only be computed with recursion. I
> SRJ> cannot understand why.
>
> Because what you know is wrong: iteration and recursion are
> computationally equivalent. If you can express an algorithm
> iteratively, you can express it recursively, and vice versa;
Actually, not quite true in theory of computation. Unfortunately, it
was so long ago that I actually took this class, that many of the
details of the hierarchy or computational power have passed out of my
mind.
All that immediately comes to mind is that through the nesting of loops,
you are really limited to polynomial time algorithms, with the
polynomial exponent related to the nesting depth of the loops.
With recursive functions, you can construct exponential time algorithms,
which are clearly in a different complexity class.
> the
> principal difference is that you can maintain some state implicitly in
> a recursive expression of the algorithm, but you must maintain all the
> state explicitly in an iterative expression of the algorithm.
All this means is that you are implementing your own "stack management"
in the iterative version. It is still a recursive function, but one in
which the recursion and stack information is maintained by the
programmer. It is not an iterative function in theoretical sense.
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
>
> All this means is that you are implementing your own "stack management"
> in the iterative version. It is still a recursive function, but one in
> which the recursion and stack information is maintained by the
> programmer. It is not an iterative function in theoretical sense.
>
Why don't you think that all recursion program run in computer are
actually iterative because all the programs are translated into
machine code and run iteratively?
S. Robert James wrote:
> I know that, in computation theory, there are certain functions which
> can only be computed with recursion. I cannot understand why.
First, let's note that the word "functions" means
mathematical functions. It does not mean functions
that can be computed on machines with finite memories,
so the replies that appeal to the finite memory of
some particular machine are not relevant to your
question.
Second, let's note that most mathematical functions
cannot be computed at all. (There are uncountably
many mathematical functions from the integers to the
integers, for example, but only finitely many of them
are computable.)
Third, let's note that "can only be computed with
recursion" means can only be computed using recursion
or by some equally powerful technique. As has been
noted, recursion is equivalent to iteration plus
unbounded stacks. (Recursion is more powerful than
iteration plus a single unbounded stack, however.)
The key idea here is that some computable functions
require unbounded state, and the unbounded state
provided by a single unbounded stack isn't good
enough unless the stack allows examination of any
element of the stack without popping the stack.
I recommend you study the Chomsky hierarchy, as would
be presented by any decent book on computability, e.g.
Michael Sipser's. Here's the abstract:
type 0 languages
= recursively enumerable languages
= formal languages recognizable by a Turing machine
= formal languages recognizable by recursive programs
= formal languages recognizable by iterative programs
with multiple unbounded stacks
= formal languages recognizable by iterative programs
with two variables that are both capable of
holding integers of arbitrarily large size
type 1 languages
= context-sensitive languages
= formal languages recognizable by linear-bounded
Turing machines (i.e. Turing machines whose
maximum tape usage is bounded by a linear function
of the input size)
type 2 languages
= context-free languages
= languages that be described by a context-free grammar
= languages that be described by BNF
= formal languages recognizable by nondeterministic pushdown
automata
type 3 languages
= regular languages
= languages that be described by a regular grammar
= languages that be described by a regular expression
= formal languages recognizable by a finite state automaton
= formal languages recognizable by iterative programs that
have only a finite number of variables, each of which
can take on only a finite number of values
If you take "iterative" to mean iterative programs with
only a finite number of 64-bit variables, then iterative
programs are much less powerful than recursive programs.
If you take "iterative" to mean iterative programs with
at least two variables that can hold an arbitrarily large
integer, then iterative programs are every bit as powerful
as recursive programs.
HTH.
Will
William D Clinger wrote:
> Second, let's note that most mathematical functions
> cannot be computed at all. (There are uncountably
> many mathematical functions from the integers to the
> integers, for example, but only finitely many of them
^^^^^^^^
I think you wanted to type "countably"?
> are computable.)
Matthias Buelow wrote:
> > Second, let's note that most mathematical functions
> > cannot be computed at all. (There are uncountably
> > many mathematical functions from the integers to the
> > integers, for example, but only finitely many of them
> ^^^^^^^^
>
> I think you wanted to type "countably"?
>
> > are computable.)
Yes. Thank you for correcting my mistake.
Will
Thank you for the excellent reply. (And also for clearly defining the
terms of discussion.)
The issue which I'm still stuck on, however, is: What is an example of
a function that is computable on a type 0 language but not type 3?
Examples have been given, such as DFA. But I don't understand:
* If we limit the domain to a finite set, we can certainly use a type
3 to compute it (perhaps using a lookup table).
* If we don't limit the domain to a finite set, but rather wan't to be
able to compute the answer for an infinite domain, don't we always
need a type 1 or type 0? It would seem to me that even something as
simple as addition would require a type 1, and that exponentiation
would require a type 0.
Perhaps you can clarify...?
On Jul 15, 7:20 pm, William D Clinger <········@yahoo.com> wrote:
> S. Robert James wrote:
> > I know that, in computation theory, there are certain functions which
> > can only be computed with recursion. I cannot understand why.
>
> First, let's note that the word "functions" means
> mathematical functions. It does not mean functions
> that can be computed on machines with finite memories,
> so the replies that appeal to the finite memory of
> some particular machine are not relevant to your
> question.
>
> Second, let's note that most mathematical functions
> cannot be computed at all. (There are uncountably
> many mathematical functions from the integers to the
> integers, for example, but only finitely many of them
> are computable.)
>
> Third, let's note that "can only be computed with
> recursion" means can only be computed using recursion
> or by some equally powerful technique. As has been
> noted, recursion is equivalent to iteration plus
> unbounded stacks. (Recursion is more powerful than
> iteration plus a single unbounded stack, however.)
> The key idea here is that some computable functions
> require unbounded state, and the unbounded state
> provided by a single unbounded stack isn't good
> enough unless the stack allows examination of any
> element of the stack without popping the stack.
>
> I recommend you study the Chomsky hierarchy, as would
> be presented by any decent book on computability, e.g.
> Michael Sipser's. Here's the abstract:
>
> type 0 languages
> = recursively enumerable languages
> = formal languages recognizable by a Turing machine
> = formal languages recognizable by recursive programs
> = formal languages recognizable by iterative programs
> with multiple unbounded stacks
> = formal languages recognizable by iterative programs
> with two variables that are both capable of
> holding integers of arbitrarily large size
>
> type 1 languages
> = context-sensitive languages
> = formal languages recognizable by linear-bounded
> Turing machines (i.e. Turing machines whose
> maximum tape usage is bounded by a linear function
> of the input size)
>
> type 2 languages
> = context-free languages
> = languages that be described by a context-free grammar
> = languages that be described by BNF
> = formal languages recognizable by nondeterministic pushdown
> automata
>
> type 3 languages
> = regular languages
> = languages that be described by a regular grammar
> = languages that be described by a regular expression
> = formal languages recognizable by a finite state automaton
> = formal languages recognizable by iterative programs that
> have only a finite number of variables, each of which
> can take on only a finite number of values
>
> If you take "iterative" to mean iterative programs with
> only a finite number of 64-bit variables, then iterative
> programs are much less powerful than recursive programs.
>
> If you take "iterative" to mean iterative programs with
> at least two variables that can hold an arbitrarily large
> integer, then iterative programs are every bit as powerful
> as recursive programs.
>
> HTH.
>
> Will
S. Robert James wrote:
> * If we limit the domain to a finite set, we can certainly use a type
> 3 to compute it (perhaps using a lookup table).
Correct. All finite functions are computed by
finite-state automata.
> It would seem to me that even something as
> simple as addition would require a type 1, and that exponentiation
> would require a type 0.
Consider the following formal languages:
Addition = { a^m b^n c^(m+n) | m and n are natural numbers }
Multiplication = { a^m b^n c^(m*n) | m and n are natural numbers }
Exponentiation = { a^m b^n c^(m^n) | m and n are natural numbers }
Then Addition is a type 2 language, and is decided
by a deterministic pushdown automaton. Multiplication
and Exponentiation, however, are not type 2 languages.
(You can prove this using the pumping lemma.) I think
they are decided by linear-bounded pushdown automata,
but I haven't worked that out.
Will
Another mistake. I wrote:
> I think
> they are decided by linear-bounded pushdown automata,
> but I haven't worked that out.
Please pretend I didn't type "pushdown" there.
Matthias Buelow wrote:
> I'd like to point out that that lookup table you have been mentioning a
> couple times is completely irrelevant to the discussion - it doesn't
> make a difference for the computational models of certain functions if
> they use a lookup table or not, since filling the table would have to be
> included in the discussion, you can't just factor it out.
Any finite lookup table can be wired into the finite-state
part of the automaton, which is why finite lookup tables
come free for all of the computational models we have been
discussing.
Will
On Jul 16, 3:12 pm, William D Clinger <········@yahoo.com> wrote:
> Consider the following formal languages:
>
> Addition = { a^m b^n c^(m+n) | m and n are natural numbers }
> Multiplication = { a^m b^n c^(m*n) | m and n are natural numbers }
> Exponentiation = { a^m b^n c^(m^n) | m and n are natural numbers }
>
> Then Addition is a type 2 language
I don't follow the notation / explanation - can you please elaborate?
S. Robert James wrote:
> * If we limit the domain to a finite set, we can certainly use a type
> 3 to compute it (perhaps using a lookup table).
I'd like to point out that that lookup table you have been mentioning a
couple times is completely irrelevant to the discussion - it doesn't
make a difference for the computational models of certain functions if
they use a lookup table or not, since filling the table would have to be
included in the discussion, you can't just factor it out.
Matthias Buelow <···@incubus.de> writes:
> S. Robert James wrote:
>
>> * If we limit the domain to a finite set, we can certainly use a type
>> 3 to compute it (perhaps using a lookup table).
>
> I'd like to point out that that lookup table you have been mentioning a
> couple times is completely irrelevant to the discussion - it doesn't
> make a difference for the computational models of certain functions if
> they use a lookup table or not, since filling the table would have to be
> included in the discussion, you can't just factor it out.
I don't see why.
Assume I give you this table:
((0.7853982 0.70710677)
(0.78539824 0.7071068)
(0.7853983 0.7071069)
(0.78539836 0.70710695)
(0.7853984 0.70710695)
(0.7853985 0.707107)
(0.78539854 0.70710707)
(0.7853986 0.70710707)
(0.78539866 0.7071071)
(0.7853987 0.7071072))
Why should you involve CL:SIN in this discussion?
Perhaps I got this table my measuring a circle!
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Pascal Bourguignon wrote:
> Assume I give you this table:
[...]
> Why should you involve CL:SIN in this discussion?
> Perhaps I got this table my measuring a circle!
As Prof. Clinger correctly pointed out, for finite sets, it is indeed
irrelevant.
"S. Robert James" <············@gmail.com> writes:
> I know that, in computation theory, there are certain functions
> which can only be computed with recursion. I cannot understand why.
How do you know this? I don't believe it is true.
--
Frode Vatvedt Fjeld
On Jul 15, 10:39 pm, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
> "S. Robert James" <············@gmail.com> writes:
>
> > I know that, in computation theory, there are certain functions
> > which can only be computed with recursion. I cannot understand why.
>
> How do you know this? I don't believe it is true.
>
> --
> Frode Vatvedt Fjeld
As long as you are considering finite numbers, every function can be
defined using loops. And since real computers have finite memory, all
functions( more strictly algorithms ) that can be defined in a
computer program can be defined using loop. Read Niklaus Wirth's
classic "Data Structure + Algorithm = Program", it has an excellent
chapter on recursion and some samples of converting a recursive
program into a loop-based program.
Ray S.
From: Thomas A. Russ
Subject: Re: Understanding why Recursion is necessary
Date:
Message-ID: <ymisl7nnb22.fsf@sevak.isi.edu>
rays <············@gmail.com> writes:
> As long as you are considering finite numbers, every function can be
> defined using loops. And since real computers have finite memory, all
> functions( more strictly algorithms ) that can be defined in a
> computer program can be defined using loop. Read Niklaus Wirth's
> classic "Data Structure + Algorithm = Program", it has an excellent
> chapter on recursion and some samples of converting a recursive
> program into a loop-based program.
Well, doing tree-walks is an example of something that can't effectively
be done using a loop, unless you start explicitly managing your own
stack. Assume a simple binary tree structure such as:
(defstruct tree left value right)
and then a simple traversal function that lists the values in order from
left to right:
(defun list-values (tree)
(unless (null tree)
(list-values (tree-left tree))
(print (tree-value tree))
(list-values (tree-right tree))))
what would an iterative solution look like?
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ wrote:
> Well, doing tree-walks is an example of something that can't effectively
> be done using a loop, unless you start explicitly managing your own
> stack.
Indeed. Although most of our discussion has involved
the Chomsky hierarchy and Turing's notion of computable
functions, which turns the focus upon a program's access
to auxiliary storage, it would be better to use the notion
of expressiveness instead. Your example is similar to
the program used to prove the Patterson-Hewitt theorem,
which asserts that no flowchart program whose computational
primitives are restricted to { a, b, c, d, i } can compute
the same result as
(define (f x)
(if (d x)
(i x)
(c (f (a x))
(f (b x)))))
for all possible interpretations of { a, b, c, d, i }.
I have discussed this result previously [1,2,3,4].
Will
[1] William D Clinger. Posted to comp.lang.lisp,
19 July 2005, 07:11:06 -0700.
[2] William D Clinger. Posted to comp.lang.lisp,
19 July 2005, 09:12:03 -0700.
[3] William D Clinger. Posted to comp.lang.lisp,
19 July 2005, 11:09:10 -0700.
[4] William D Clinger. Posted to comp.lang.lisp,
19 July 2005, 13:21:00 -0700.
···@sevak.isi.edu (Thomas A. Russ) writes:
> rays <············@gmail.com> writes:
>
>> As long as you are considering finite numbers, every function can be
>> defined using loops. And since real computers have finite memory, all
>> functions( more strictly algorithms ) that can be defined in a
>> computer program can be defined using loop. Read Niklaus Wirth's
>> classic "Data Structure + Algorithm = Program", it has an excellent
>> chapter on recursion and some samples of converting a recursive
>> program into a loop-based program.
>
> Well, doing tree-walks is an example of something that can't effectively
> be done using a loop, unless you start explicitly managing your own
> stack. Assume a simple binary tree structure such as:
(shadow 'tree-copy)
> (defstruct tree left value right)
>
> and then a simple traversal function that lists the values in order from
> left to right:
>
> (defun list-values (tree)
> (unless (null tree)
> (list-values (tree-left tree))
> (print (tree-value tree))
> (list-values (tree-right tree))))
>
> what would an iterative solution look like?
For example:
(defun list-values (tree)
(loop
:with stack = (list (list :node tree))
:while stack
:do (destructuring-bind (key tree) (pop stack)
(ecase key
((:print) (print (tree-value tree)))
((:node) (unless (null tree)
(push (list :node (tree-right tree)) stack)
(push (list :print tree) stack)
(push (list :node (tree-left tree)) stack)))))))
C/USER[72]> (list-values
(make-tree
:value 'root
:left (make-tree
:value 'left
:left (make-tree :value 'll)
:right (make-tree :value 'lr))
:right (make-tree
:value 'right
:left (make-tree :value 'rl)
:right (make-tree :value 'rr))))
LL
LEFT
LR
ROOT
RL
RIGHT
RR
NIL
C/USER[73]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> "S. Robert James" <············@gmail.com> writes:
>
>> I know that, in computation theory, there are certain functions
>> which can only be computed with recursion. I cannot understand why.
>
> How do you know this? I don't believe it is true.
Well, we know that recursion <=> iteration+stack, and there are
certain functions that need unlimited memory, for example the
functions that cannot be "computed" by a DFA, but need a Turing
Machine.
The function that takes as input a sequence of parentheses and returns
whether the parentheses are well balanced or not is one such function.
A DFA can only handle sequences of a given maximum length. A TM can
handle sequences of any length.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jul 15, 2:27 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> Well, we know that recursion <=> iteration+stack, and there are
> certain functions that need unlimited memory, for example the
> functions that cannot be "computed" by a DFA, but need a Turing
> Machine.
>
> The function that takes as input a sequence of parentheses and returns
> whether the parentheses are well balanced or not is one such function.
For a finite domain, recursion shouldn't be necessary, correct? We can
use a lookup table.
So, you're talking about computing the function on inputs of any
length. Then don't all nontrivial functions require infininte memory?
What would be a nontrivial function that can work on any size input in
finite memory?
"S. Robert James" <············@gmail.com> writes:
> On Jul 15, 2:27 pm, Pascal Bourguignon <····@informatimago.com> wrote:
>> Well, we know that recursion <=> iteration+stack, and there are
>> certain functions that need unlimited memory, for example the
>> functions that cannot be "computed" by a DFA, but need a Turing
>> Machine.
>>
>> The function that takes as input a sequence of parentheses and returns
>> whether the parentheses are well balanced or not is one such function.
>
> For a finite domain, recursion shouldn't be necessary, correct? We can
> use a lookup table.
> So, you're talking about computing the function on inputs of any
> length. Then don't all nontrivial functions require infininte memory?
> What would be a nontrivial function that can work on any size input in
> finite memory?
You might take a look at a textbook on computational theory; given
that this question was posed to a programming language newsgroup, I
wonder if you're using the term "recursion" in an ambiguous way? To
answer your last specific question above: A function that computes
a specific regular expression, i.e., one that implements a DFA.
S. Robert James wrote:
> So, you're talking about computing the function on inputs of any
> length. Then don't all nontrivial functions require infininte memory?
No computable function requires infinite space, since if it would, it
would not halt (in all cases, at least). I don't know what you mean by
"trivial" functions.
What you probably intend to say is, if there are any functions where the
amount of space used for computing the function is somehow bounded by a
function on the input length, which of course exist, for example regular
languages (defined by the well known regular expressions), context-free
languages (typical compiler grammars), and context-sensitive languages
that can be decided (computed) in that way.
"S. Robert James" <············@gmail.com> writes:
> I know that, in computation theory, there are certain functions which
> can only be computed with recursion. I cannot understand why.
As others have noted, this is not true.
> If f(x) is defined over a finite domain X, we can always compute f(x)
> by using a simple lookup table, without any recursion.
Computers (at least digital ones with finite resources) have finitely
many states, thus all functions implemented on computers have finite
domain, and could be implemented using a lookup table in the Big
Lookup Table Book. However, this would not be feasible or useful,
that's why we are not doing it.
In the context of computer programs, recursion is used because it is
elegant/compact, not because it is the only possible way. It appears
that you are mixing up two orthogonal issues.
> If the domain X is infinite, than I think we need recursion for any
> nontrivial function. For instance, take f(x,y) = x + y. To calculate
> that, we need to recurse over y in some way (either breaking y down by
> its digits, or incrementing x y times). Even f(x) = x + 1 requires us
> to recurse over all of x digits, until we find a non-9 digit, if we
> want to represent the value in any non-unary base.
See comment above.
Tamas
From: Pekka Niiranen
Subject: Re: Understanding why Recursion is necessary
Date:
Message-ID: <469A7AE2.3050801@pp5.inet.fi>
Tamas Papp wrote:
> "S. Robert James" <············@gmail.com> writes:
>
>> I know that, in computation theory, there are certain functions which
>> can only be computed with recursion. I cannot understand why.
>
> As others have noted, this is not true.
Is it?: if you need to parse expressions inside expressions
without knowing the depth beforehand can you do without recursion?:
(a ( b (...unknown amount of bracket limited expressions..) ) )
>
>> If f(x) is defined over a finite domain X, we can always compute f(x)
>> by using a simple lookup table, without any recursion.
>
> Computers (at least digital ones with finite resources) have finitely
> many states, thus all functions implemented on computers have finite
> domain, and could be implemented using a lookup table in the Big
> Lookup Table Book. However, this would not be feasible or useful,
> that's why we are not doing it.
>
> In the context of computer programs, recursion is used because it is
> elegant/compact, not because it is the only possible way. It appears
> that you are mixing up two orthogonal issues.
>
>> If the domain X is infinite, than I think we need recursion for any
>> nontrivial function. For instance, take f(x,y) = x + y. To calculate
>> that, we need to recurse over y in some way (either breaking y down by
>> its digits, or incrementing x y times). Even f(x) = x + 1 requires us
>> to recurse over all of x digits, until we find a non-9 digit, if we
>> want to represent the value in any non-unary base.
>
> See comment above.
>
> Tamas
Pekka Niiranen wrote:
> Tamas Papp wrote:
>> "S. Robert James" <············@gmail.com> writes:
>>
>>> I know that, in computation theory, there are certain functions which
>>> can only be computed with recursion. I cannot understand why.
>>
>> As others have noted, this is not true.
>
> Is it?: if you need to parse expressions inside expressions
> without knowing the depth beforehand can you do without recursion?:
>
> (a ( b (...unknown amount of bracket limited expressions..) ) )
Yes, you can. I've implemented such a parser some time ago with a stack,
take a look at http://www.frank-buss.de/formula/formula.zip from
http://www.frank-buss.de/formula/ and the file Evaluator.cpp.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> Pekka Niiranen wrote:
>
>> Tamas Papp wrote:
>>> "S. Robert James" <············@gmail.com> writes:
>>>
>>>> I know that, in computation theory, there are certain functions which
>>>> can only be computed with recursion. I cannot understand why.
>>>
>>> As others have noted, this is not true.
>>
>> Is it?: if you need to parse expressions inside expressions
>> without knowing the depth beforehand can you do without recursion?:
>>
>> (a ( b (...unknown amount of bracket limited expressions..) ) )
>
> Yes, you can. I've implemented such a parser some time ago with a stack,
> take a look at http://www.frank-buss.de/formula/formula.zip from
> http://www.frank-buss.de/formula/ and the file Evaluator.cpp.
For an easier proof that recursion can be rewritten in terms of
iteration, consider:
(let ((ip -1)
(sp (length memory)))
(tagbody
loop
(incf ip)
(case (aref memory ip)
...)
(go loop)))
S. Robert James wrote:
> I know that, in computation theory, there are certain functions which
> can only be computed with recursion. I cannot understand why.
>
> If f(x) is defined over a finite domain X, we can always compute f(x)
> by using a simple lookup table, without any recursion.
Yeah but you have to compute the table in beforehand, probably by
recursion aswell, so that won't absolve you.