Recursive procedure (to display a linked list)

[Olsi009]

Hi again, this is a simple programme that I can't make work :S in turbo pascal.

Write a program to create a new list and then display it through a Recursive Procedure ( and use 'p' as a local variable).

This is what I could do but considering I hate procedures and functions it gives me the 'OverFlow' error.

I think the procedure of creation is ok but the recursive one must be chaged.
Any help?

[B]Program[/B] List56;
[B]Uses[/B] CRT;
[B]Type[/B]
student=^pointer;
pointer=[B]record[/B]
name:string[10];
next:student;
[B]end;[/B]

Var org, p1 :student;

[B]Procedure[/B] Cr8List;
[B]Begin[/B]
[B]new[/B](p1);
org:=nil;
p1:=org;
[B]Writeln[/B]('Type the names of the students,( hit enter to stop).');
[B]Writeln;[/B]
[B]writeln;[/B]
[B]Write[/B]('Name: ');
[B]readln([/B]p1^.name);
[B]While[/B] p1^.name <> '' [B]do[/B]
[B]Begin[/B]
p1^.next:=org;
org:=p1;
[B]Write[/B]('Name: ');
[B]new[/B](p1);
[B]readln[/B](p1^.name);
[B]end;
end;[/B]

Procedure RecursiveDisplay(p:student);
[B]begin[/B]
[B]while [/B]p<> [B]nil do[/B]
[B]begin[/B]
[B]Writeln[/B]('Name: ',p^.name);
p:=p^.next;
AfishimRekursiv(p);
dispose(p);
[B]end;
end;[/B]
[B]Begin[/B]
CLRSCR;
Cr8List;
p1:=org;
RecursiveDisplay(p1);
[B]end.[/B]

[Duoas]

I think that you need to increase your stack size.

You can do it from the Options -> Compiler -> Memory Sizes menu or use the $M directive at the top of your code.

{$M 32768, 655360}  { Twice the default stack size, default heap size }
program fooey;
begin
  writeln( 'Hello world!' )
end.

Let me know if this helps.

[fayyaz]

Helo Olsi009
i think that some of your programs statements is in a wrong Order I try to correct them and write the new programe as below

Program List56;
Uses CRT;
Type
student=^pointer;
pointer=record
name:string[10];
next:student;
end;

Var Head,org, p1 :student;
Name:String;

Procedure Cr8List;
Begin
//creating the first node of link list
new(p1);
readln(p1^.name);
P1.Next:=Nil; //The Next pointer of last node mast be nil
Head:=P1;// Head points to the first node of link list
Org:=P1; // Org is a temporary Pointer
Writeln('Type the names of the students,( hit enter to stop).');
Writeln;
writeln;
Write('Name: ');
// Creating The rest of the link list
While p1^.name <> '' do
Begin
new(p1);//Create New node
P1.Next:=Nil;// because it is the last created node, it's next pointer mast be nil
Org.Next:=P1;// make a link between previous node and new node
Org:=P1 // Move temporary pointer to last node
Write('Name: ');
readln(p1^.name);
End;
end;

Procedure RecursiveDisplay(p:student);
begin
If P<>Nil Then
Begin
Writeln('Name: ',p^.name);
RecursiveDisplay(p.next);
End
End;

end;
Begin
CLRSCR;
Cr8List;
RecursiveDisplay(Head);
end.

I havent run this programe But I think it mast be work correctly

[Olsi009]

Hi fayyaz,
The program works very well and the list is displayed in the exact order (same with the creation). I just added some '^' to the pointers but it works perfectly. thank you

Also Douas thank you cuz my memory size was 16384 - pitty :P

[brijkiran]

hi,
plz help me guys , i hav to give an seminar on "the recursive procedure with link list" (pascal) in college......i need some explanation how it works....

[jeme]

hi i wnat program is calculate adding two number by bostfix
thank you very much......

[fayyaz]

Hi Brijkiran

If you explain that what you want exactly to know I can help you.

[fayyaz]

Hi jeme
please Exactly declare What is input and output of your program. it is beter that you give an example about that

[brijkiran]

Helo...!
hi fayyaz,
actually, i have to explain it in the seminar, that we hav 2 give in the college, i hav to give the presentation for 10 minutes on it, i m giving the presentation for first time...
so plz tell me the pts that shud i mentioned for the explanation...(i need to explain it with the initial leve, as we are just started learning)
and i need a full program coding to explain...'recursion with link list'.... i m getting it throughly, i m not so good in cocecp of recursion...
so if can u plz provide me a program
....thanks for the help...

[brijkiran]

Helo...!
hi fayyaz,
actually, i have to explain it in the seminar, that we hav 2 give in the college, i hav to give the presentation for 10 minutes on it, i m giving the presentation for first time...
so plz tell me the pts that shud i mentioned for the explanation...(i need to explain it with the initial leve, as we are just started learning)
and i need a full program coding to explain...'recursion with link list'.... i m getting it throughly, i m not so good in cocecp of recursion...
so if can u plz provide me a program
....thanks for the help...

[Duoas]

If you are going to give a seminar it is a good idea to know what you are talking about.

Do you know what a linked list is? Do you know how to implement one in the abstract? Can you implement one in C/C++/Pascal/whatever you like? Do you know the difference between singly-linked and doubly-linked lists? Do you know the advantages and disadvantages of using a linked list?

Do you know what recursion is? Do you know its pitfalls? Do you know how to convert a recursive procedure to one that uses a loop? (While you are at it, read up on tail-call recursion.)

Here is a recapitulation of the very first post (with some errors fixed):

program a;
type
  pStudent = ^tStudent;
  tStudent = record
    name: string;
    next: pStudent
    end;

function getStudentsFromUser: pStudent;
  var
    head: pStudent;
    curr: pStudent;
    name: string;
  begin
  head := nil;
  writeln( 'Enter student names, one per line.' );
  writeln( 'When done, enter a blank line' );

  { Get the first name }
  readln( name );
  name := trim( name );

  while name <> '' do
    begin
    { Add a new student to the list }
    if head = nil
      then begin
           { Create the first node in the list }
           new( head );
           curr := head
           end
      else begin
           { Tack a new node on the existing list }
           new( curr^.next );
           curr := curr^.next
           end;

    { Fill the node with data }
    curr^.name := name;
    curr^.next := nil;

    { Get the next name }
    readln( name );
    name := trim( name )
    end;

  { Return the new list }
  result := head
  end;

procedure RecursiveDisplay( students: pStudent );
  begin
  while students <> nil do
    begin
    writeln( 'Name: ', students^.name );
    students := students^.next;
    RecursiveDisplay( students )
    end
  end;

function freeStudents( students: pStudent ): pStudent;
  var
    next: pStudent;
  begin
  while students <> nil do
    begin
    next := students^.next;
    dispose( students );
    students := next
    end;
  result := nil
  end;

var
  students: pStudent;
begin
  students := getStudentsFromUser;
  RecursiveDisplay( students );
  students := freeStudents( students )
end.

You'll need to do some serious reading to learn more. Hope this helps.

[brijkiran]

ok, i studied so far, i know abt link list of different type, but m not gettin the theory of recursion with linklist

[brijkiran]

ok, i studied so far, i know abt link list of different type, but m not gettin the theory of recursion with linklist

[brijkiran]

and i m very thankful to u for helping me alot.......

[Duoas]

The theory on recursion over lists is actually pretty simple. The idea is this:

If you can do something to the head of a list in relation to the rest of the list, you can do it to the whole list.

Let's have an example. Suppose you have a list of numbers. 1 4 -7 19 42 0 8 The question I'll pose is: What is the sum of the numbers in the list?

We'll need a consumer function: one that takes a list of numbers and converts it into a single number. [B]function[/B] sum_list( ls: [B]array of integer[/B] ): [B]integer[/B]; Initially, of course, we call our function with the whole list: sum_list( [1, 4, -7, 19, 42, 0, 8] ); The sum can be considered thus: 1 + sum_list( [4, -7, 19, 42, 0, 8] ); Consider for a second what we did. The sum of the whole list is the same as adding the first element of the list to the sum of the rest of the list.

So then, what is the sum of the rest of the list? You guessed it: the same darn thing. Keep doing it until the list runs out and you'd get something like: 1 + 4 + -7 + 19 + 42 + 0 + 8 + sum_list( [] ); At this point, we can safely say that the sum of nothing (the empty list) is nothing (zero). So sum_list( [] ); should return zero.

In mathematics, what we have done to the list is called induction. We have used induction to partition the list into a structure that defines itself. The implementation is called recursion. Armed with our idea, we can write (or implement) our recursive routine thus:

function sum_list( ls: array of integer ): integer;
  begin
  if length( ls ) = 0
    then result := 0
    else result := ls[ 0 ] + sum_list( copy( ls, 1, high( s ) ) )
  end;

If Pascal supported tail-recursion, this procedure would be tail-recursive. (Pascal doesn't so it isn't, but you should recognize the reasons why: no state information is required between each generation. In other words, once you set result you are done with the routine; no other calculations are required, and there is no need to create a new stack frame for the recursive function call. The difference is that in Pascal, given a large enough list, you'd eventually run out of memory using recursion, but in a language that supports tail-recursion you would never run out of memory using recursion.)

Now for a technical annoyance: Due to restrictions on the way Delphi handles open arrays, we'll have to modify our procedure just a little so that it will actually compile and run. Instead of peeling numbers of the front of the list we'll just peel them off of the back:

function sum_list( ls: array of integer ): integer;
  begin
  if length( ls ) = 0
    then result := 0
    else result := ls[ high( ls ) ] + sum_list( slice( ls, high( ls ) ) )
  end;

The order you use to induct the array often matters, but since addition is commutative, it doesn't make any difference for this function.

So, if we compile and test our routine:

begin
  writeln( 'The sum is ', sum_list( [1, 4, -7, 19, 42, 0, 8] ) )
end.

(Make sure to compile an $apptype console program.) When the program is run, you'll see the correct:

The sum is 67

One more. This time the question is: What is the largest number in the list?

For now I will leave this as an exercise for you. There are several things to consider:

1. [B]function[/B] min_list( ls: [B]array of integer[/B] ): [B]integer[/B]; Would it be possible for my function to employ tail-recursion (ignoring the fact that there isn't any tail-recursion in Pascal)? Why or why not? Explain any problems.
2. [B]procedure[/B] min_list_2( ls: [B]array of integer[/B]; [B]var[/B] largest: [B]integer[/B] ); (Where largest is the largest value found so far.)
   Would this fix the problems in #1? Would it introduce any new problems? How would you choose the initial value of largest? (Hint: there are two ways to choose. Find both.)
3. Would it be OK to have one routine call the other? Why or why not?

Well, I hope this helps.

[brijkiran]

thanks yaar, u helped me alot to prepare my presentation,..........and i m now understand the full concept of it....... today is the day, i m goin to give my presentation, so hope 4 the best....and thanx once again....