data structure
Author Message data structure

Q1.Describe a recurssive algorithm that counts the number of  nodes in a

--
Posted via http://www.*-*-*.com/

Mon, 12 Sep 2005 23:38:19 GMT  data structure

Quote:

> Q1.Describe a recurssive algorithm that counts the number of  nodes in a

What is the address of your teacher? Then I'll mail it directly to him.

Tue, 13 Sep 2005 01:21:41 GMT  data structure

Quote:

> Q1.Describe a recurssive algorithm that counts the number of  nodes
>    in a singly linked list.

why?

but think of the factorial-algorithm, which often is used as an
introduction to recursion.
have a look at your textbook ;-)

something like this:

function fact(i: integer): integer;
begin
if i=0 then fact := 1
else fact := i * fact(i-1)
end;

if you understand this one (not really useful, like yours), you should
be able to answer the question yourself.

jochen

Tue, 13 Sep 2005 07:44:22 GMT  data structure

Quote:

> > Q1.Describe a recurssive algorithm that counts the number of  nodes
> >    in a singly linked list.

> why?

> but think of the factorial-algorithm, which often is used as an
> introduction to recursion.
> have a look at your textbook ;-)

> something like this:

> function fact(i: integer): integer;
> begin
>   if i=0 then fact := 1
>   else fact := i * fact(i-1)
> end;

> if you understand this one (not really useful, like yours), you should
> be able to answer the question yourself.

Recursion is not useful for these kind of tasks, especially in TP
where the stack is limited. It will create {*filter*} bugs that show only
when the data is sufficiently large. I think it is sad that they
actually teach these. The worst is the recursive algorithm to calculate
Fibbonacci numbers.

Osmo

Wed, 14 Sep 2005 17:13:23 GMT  data structure

Quote:

> > Q1.Describe a recurssive algorithm that counts the number of  nodes
> >    in a singly linked list.

> why?

> but think of the factorial-algorithm, which often is used as an
> introduction to recursion.
> have a look at your textbook ;-)

> something like this:

> function fact(i: integer): integer;
> begin
>   if i=0 then fact := 1
>   else fact := i * fact(i-1)
> end;

> if you understand this one (not really useful, like yours), you should
> be able to answer the question yourself.

> jochen

I am no programming expert, but I do not believe your function
fact(i: integer): integer will work!  If you put the value of 2 into i, how will
the computer know what fact(i-1) is?  It will need this to multiply 2 with.
Mathematically it is correct, but you need to pump i up to the target value to
be able to calculate the factorial of a number.    Am I correct?
I believe you need a loop in there:
function fact(i: integer): integer;
j: integer
begin
for  j=0 to i do              ; where factorial(i) is being calculated
if j=0 then fact := 1    ; it would be more efficient to put this outside
the loop
else fact := j * fact
end;
end;

Is this correct?
Roy Cornish

Fri, 23 Sep 2005 02:53:05 GMT  data structure

Quote:

>> > Q1.Describe a recurssive algorithm that counts the number of  nodes
>> >    in a singly linked list.

>> why?

>> but think of the factorial-algorithm, which often is used as an
>> introduction to recursion.
>> have a look at your textbook ;-)

>> something like this:

>> function fact(i: integer): integer;
>> begin
>>   if i=0 then fact := 1
>>   else fact := i * fact(i-1)
>> end;

>> if you understand this one (not really useful, like yours), you should
>> be able to answer the question yourself.

>     I am no programming expert,

Quote:
> but I do not believe your function
>fact(i: integer): integer will work!  If you put the value of 2
>into i, how will the computer know what fact(i-1) is?

Because is will invoke 'fact' again, with 'i-1' as its argument,
etc, etc, etc. Eventually it will 'i-1' will be zero and at that

stage 'fact' will return 1, and complete the pending multiply
etc, etc, etc.

Quote:
>It will need this to multiply 2 with.
>Mathematically it is correct, but you need to pump i up to the target value to
>be able to calculate the factorial of a number.    Am I correct?
>     I believe you need a loop in there:
>function fact(i: integer): integer;
>j: integer
>begin
>   for  j=0 to i do              ; where factorial(i) is being calculated
>     if j=0 then fact := 1    ; it would be more efficient to put this outside
>the loop
>     else fact := j * fact
>  end;
>end;

>  Is this correct?

Yes.

Robert
--
Robert AH Prins

Sat, 24 Sep 2005 05:18:07 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages