Segmentation Fault when trying to use a recursive concept

[orangemediumgreen]

Dear all, 

I am quite new to Pascal and I am trying to make a program, which returns the fibonacci number. For educational reasons, I try to solve this recursively.

For example: fib(16) --> 987

But when I run the code... I get a segmentation fault. 

Thank you in advance!

Edit: I am using the fpc as a compiler if that matters.


Here is the sourcecode of the function:

Code: [Select]

function fib(var g:integer):integer;
var
v1,v2:integer;
begin

if g=0 then
begin
fib:=0;
end;

if g=1 then
begin
fib:=1;
end

else

begin
v1:=g-1;                   // OT: Additional question ^^
v2:=g-2;                   // Why can't I just call...
fib:= fib(v2)+fib(v1);     // fib:= fib(g-2)+fib(g-1);
end;                               // If I do so, I get: Error: Variable identifier expected.

end;

[bylaardt]

try this:

Code: [Select]

function fib(const sequential_position:longint):Longint;
begin
  if sequential_position<1 then
    result:=0
  else if sequential_position<3 then
    result:=1
  else
    result:=fib(sequential_position-1)+fib(sequential_position-2);
end;


[orangemediumgreen]

Hello bylaardt,

thank you for your suggestion.

But I still get the segmentation fault, even when I run your code ...

By the way: I had to replace "result" with "fib". I know that result is a keyword, but not for me. Do you use the free pascal compiler, too?

Code: [Select]

function fib(const sequential_position:longint):Longint;
begin
  if sequential_position<1 then
    fib:=0
  else if sequential_position<3 then
    fib:=1
  else
    fib:=fib2(sequential_position-1)+fib(sequential_position-2);
end;

[howardpc]

bylaardt's code runs here for parameter values between 0 and 46.
Higher values cause an EIntOverflow exception (since the type is constrained to longint).
You could use int64 to calculate further values (more slowly).
If you have a small stack setting, it is possible that highly recursive routines will exceed the stack memory allocation, though normal OS defaults are usually adequate on modern computers.

[bylaardt]

what "For educational reasons" means?
do you want learn a pascal dialect from the 80's? for historical reasons?
set the function result with the same name was the standard, but i can remember when or why the result features was implemented.

use result.
let the rest to history books.

and howardpc are right, new version to better results:

Code: [Select]

function fib(const sequential_position:byte):Int64;
begin
  if sequential_position<1 then
    fib:=0
  else if sequential_position<3 then
    fib:=1
  else
    fib:=fib2(sequential_position-1)+fib(sequential_position-2);
end;

[taazz]

Hello bylaardt,

thank you for your suggestion.

But I still get the segmentation fault, even when I run your code ...

By the way: I had to replace "result" with "fib". I know that result is a keyword, but not for me. Do you use the free pascal compiler, too?

Code: [Select]

function fib(const sequential_position:longint):Longint;
begin
  if sequential_position<1 then
    fib:=0
  else if sequential_position<3 then
    fib:=1
  else
    fib:=fib2(sequential_position-1)+fib(sequential_position-2);
end;

1) Change the compiler mode in your unit to something newer eg delphi or objfpc.
2) what fib2 does and why not call fib?

[orangemediumgreen]

First of all: Thanks for your comments.

The "2" in "fib2"slipped in while copying - Sorry. Of course that must be just "fib" .

what "For educational reasons" means?

That means that I am learning Pascal for my course of studies and we should also know about recursion.

Change the compiler mode in your unit to something newer eg delphi or objfpc

I just tried this and now I can use at least "result". But I still get a segmentation fault.

So I assume its the compiler... I will try to add gpc to gcc. Maybe that one is better or more up-to-date. I will post here if it worked.

Thank you all for your comments and suggestions!

[taazz]

can you upload a complete project using the mentioned function and raises the segmentation fault? Also I can't seem to find any information on what compiler/IDE used to write and compile the code please provide this information too with the complete project.

[orangemediumgreen]

Hello taazz,

this is the complete code I have. I am saving this code as a .pas file and I compile it in the terminal manually.

(I am running a Ubuntu Linux 14.10): fpc ./fibonacci_n.pas
Output is:

Code: [Select]

Free Pascal Compiler version 2.6.4+dfsg-3 [2014/07/13] for x86_64
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling ./fibonacci_n.pas
Linking fibonacci_n
/usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
38 lines compiled, 0.1 sec
Accordingly, I tried using "fpc -MOBJFPC ./fibonacci_n.pas"  or "fpc -MDELPHI ./fibonacci_n.pas"

Code: [Select]

program fibonacci_n;

function fib(const g:integer):integer;
var
v1,v2:integer;
begin

if g=0 then
begin
fib:=0;
end;

if g=1 then
begin
fib:=1;
end

else

begin
v1:=g-1;
v2:=g-2;
fib:= fib(v2)+fib(v1);
end;

end;

var

n:integer;
ergebnis:integer;

begin
write('Fibonacci Number? ... :');
readln(n);
ergebnis:=fib(n);
writeln(ergebnis);
end.

[Bart]

Code: [Select]

program fibonacci_n;

function fib(const g:integer):integer;
var
v1,v2:integer;
begin

if g=0 then
begin
fib:=0;
end;

if g=1 then
begin
fib:=1;
end

else

begin
v1:=g-1;
v2:=g-2;
fib:= fib(v2)+fib(v1);
end;

end;

var

n:integer;
ergebnis:integer;

begin
write('Fibonacci Number? ... :');
readln(n);
ergebnis:=fib(n);
writeln(ergebnis);
end.

If g = 2 then it will start calculating fib(-2) and since all fib calls (except fib(1)) will eventually call fib(2), it will run out of control and crash the heap.

For me it crashes when trying to calculate fib(-1047738), there are at that time  523871 copies of fib() on the stack.

Fix is easy:

Code: [Select]

...
if g=0 then
begin
fibonacci:=0;
end  // << it needs an else here
        else
if g=1 then
begin
fibonacci:=1;
end

else
...

Fib(43) =   433494437  [cals = 1402817465, maxd = 43]
It takes 1402817465 calls to fib,
At max there were 43 copies of fib() on the stack.

Fib(44) crashes:
Runtime eror 215: Arithmetic overflow error

Also note that in this approach (fib:= fib(v2)+fib(v1)) you actually calculate the value of the lowest one twice.

Bart

[orangemediumgreen]

That's it!

AWESOME!

Thank you so much!

Such a bad mistake, but thanks to you it's solved.

Although I am not quite sure yet why that should be and still the result is correct...

Code: [Select]

If g = 2 then it will start calculating fib(-2)
I want to analize that too. (For educational reasons  )

Once again: Thank you! (And all the others too!  )

[Bart]

Compare this alternative approach:

Code: [Select]

function LucasGenN(L1, L2, N: Int64): Int64;
var
  i, LucMin1, LucMin2: Int64;
begin
  if (N < 0) then RunError(201); //range check error
  if N = 1 then
  begin
    Result := L1;
  end
  else if N = 2 then
  begin
    Result := L2;
  end
  else
  begin
    LucMin1 := L2;
    LucMin2 := L1;
    i := 2;
    while (i <> N) do
    begin
      Inc(i);
      Result := LucMin2 + LucMin1;
      LucMin2 := LucMin1;
      LucMin1 := Result;
    end;
  end;
end; 

Fibonacci numbers are a specialization of Lucas numbers:
Fibonacci(N) = LucasGenN(1,1,N)

It is way faster: Fib(43): 13370 ms, LucasGenN(1,1,43): < 1 ms.
The difference in time grows exponentially.

Using UInt64 to allow higher values:

Code: [Select]

Fibonacci(50)     = 12586269025, 606639 ms (> 10 minutes!)  [40730022147 calls to fib(), max 50 copies on stack]
LucasGenN(1,1,50) = 12586269025, <1 ms


Bart

[Bart]

There are other ways to calculate fibonacci(n):
See: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression.

Code: [Select]

function ufloor(x : extended) : UInt64;
begin
   //input must be >= 0
   result:=Trunc(x);
end;

function fastfib(n: UInt64): UInt64;
const
  phi = (Extended(1.0) + sqrt(5))/2;
var
  Ext: Extended;
begin
  Ext := (power(phi, n) / sqrt(5)) + 0.5;
  Result := ufloor(Ext);
end;

Due to loss of precision using floating point values however, the results are incorrect starting at FF(85):

Code: [Select]

70 LucasGenN:      190392490709135 , FF:      190392490709135
71 LucasGenN:      308061521170129 , FF:      308061521170129
72 LucasGenN:      498454011879264 , FF:      498454011879264
73 LucasGenN:      806515533049393 , FF:      806515533049393
74 LucasGenN:     1304969544928657 , FF:     1304969544928657
75 LucasGenN:     2111485077978050 , FF:     2111485077978050
76 LucasGenN:     3416454622906707 , FF:     3416454622906707
77 LucasGenN:     5527939700884757 , FF:     5527939700884757
78 LucasGenN:     8944394323791464 , FF:     8944394323791464
79 LucasGenN:    14472334024676221 , FF:    14472334024676221
80 LucasGenN:    23416728348467685 , FF:    23416728348467685
81 LucasGenN:    37889062373143906 , FF:    37889062373143906
82 LucasGenN:    61305790721611591 , FF:    61305790721611591
83 LucasGenN:    99194853094755497 , FF:    99194853094755497
84 LucasGenN:   160500643816367088 , FF:   160500643816367088
85 LucasGenN:   259695496911122585 , FF:   259695496911122586 *
86 LucasGenN:   420196140727489673 , FF:   420196140727489674 *
87 LucasGenN:   679891637638612258 , FF:   679891637638612260 *
88 LucasGenN:  1100087778366101931 , FF:  1100087778366101934 *
89 LucasGenN:  1779979416004714189 , FF:  1779979416004714193 *
90 LucasGenN:  2880067194370816120 , FF:  2880067194370816127 *

The LucasGenN generated numbers are correct (because they use precise integer maths only).
You can check on http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibCalcX.html.

Lucas numbers (and therefore, also Fibonacci numbers) are fun.

You need a "BigInteger" library to calculate fibonacci numbers > 92.
Fibonacci(92) =  7540113804746346429, and
Fibonacci(93) = 12200160415121876738, which does not fit into an UInt64 anymore.

Bart

[orangemediumgreen]

Hello Bart,

thanks again for these VERY interesting alternatives! I will definitively check them out the next days... Perhaps at the weekend, when I have time

Lucas numbers (and therefore, also Fibonacci numbers) are fun.

Yes... really intriguing

[BobDog]

Here are Fibonacci and factorial(as a bonus?) stand alone functions (No libs. required).
The table of Fibonacci numbers above seems to be one out, I followed the Wiki definition, which of course could  be one out also.
The starting position of Fibonacci seems to be in question (again).

Code: Pascal  [Select][+][-]

1.  
2. program FibonacciAndFactorial;
3.  
4. uses
5. SysUtils,DateUtils;  { only for the timer }
6.  
7.  
8. Function Fibonacci(n :longint): ansistring;  {standalone}
9. var
10.  n_,x:longint;
11.  addup,addcarry,diff,LL:longint;
12.  sl,l,term:ansistring;
13.  slp,lp,termp:pchar;
14.  label
15.  skip;
16.  
17.  Type  
18.   TA = Array[0..19] of longint;
19.  
20.   var
21.   addqmod,addbool:TA;
22.  
23.   begin  // set look up arrays
24.   term:='';
25.    for x:=0 to 9 do
26.    begin
27.    Addqmod[x]:=x+48;
28.    addqmod[x+10]:=x+48;
29.    addbool[x]:=0;
30.    addbool[x+10]:=1;
31.    end;
32.         {first few terms according to Wiki}
33.     if (n=1) then
34.     begin
35.       fibonacci:='0';
36.       exit;
37.       end;
38.  
39.     if (n=2) or (n=3) then
40.     begin
41.     fibonacci:='1';
42.     exit;
43.     end;
44.  
45.     if (n=4) then
46.         fibonacci:= '2'
47.         else
48.         begin
49.         sl:='1';
50.          l:='2' ;
51.     For x := 1 To n-4  do
52.     begin
53.     LL:=Length(l);
54.     diff:=0;
55.     if LL <> length(sl) then  diff:=1 ;
56.        addcarry:=0;
57.         term:='0'+l ;
58.          slp:=@sl[1];   // set pointers //
59.           lp:=@l[1];
60.        termp:=@term[1];
61.  
62.       For n_ :=LL-1 downTo diff do
63.       begin
64.             addup:=ord(slp[n_-diff])+ord(lp[n_])-96 ;
65.             ord(termp[n_+1]):=ADDQmod[addup+addcarry] ;
66.             addcarry:=ADDbool[addup+addcarry];
67.         end;  {next n_}
68.  
69.            If addcarry=0 Then
70.              begin
71.            if termp[0]='0' then term:=copy(term,2,length(term)-1) ;
72.            goto skip;
73.              end;
74.  
75.         If n_= 0      Then
76.           begin
77.           ord(termp[0]):=addcarry+48  ;
78.           goto skip;
79.           end;
80.            addup:=ord(lp[0])-48;
81.            ord(termp[1]):=ADDQmod[addup+addcarry];
82.            addcarry:=ADDbool[addup+addcarry];
83.         ord(termp[0]):=addcarry+48  ;
84.        if (addcarry=0) then
85.        begin
86.          if termp[0]='0' then  term:=copy(term,2,length(term)-1)
87.        end;
88.    skip:
89.         sl:=l ;
90.         l:=term;
91.         end;    {next x}
92.  
93.     fibonacci:=term;
94.  
95.     end;  {end if else}
96.     end;  {function fibonacci}
97.  
98.  
99.    function factorial(num:longint):ansistring ; {standalone}
100.    type
101.      AT = array[0..99] of longint;
102.      var
103.      _mod,_div:at;
104.      fact,a,b,c:ansistring;
105.        pa,pb,pc:pchar;
106.      n,carry,ai:smallint;
107.     la,lb,i,j,z:longint;
108.  
109.       begin {create lookup  tables}
110.      for z:=0 to 99 do
111.      begin
112.      _mod[z]:= (z mod 10) +48;
113.      _div[z]:=  z div 10;
114.       end;  {created lookup tables}
115.        fact:='1';
116.       for z:=1 to num do
117.          begin
118.        a:=fact;Str(z,b);la:=Length(a);lb:=length(b);
119.        Setlength(c,la+lb);
120.        FillChar(c[1],la+lb,#48);
121.         pa:=@a[1]; {set pointers }
122.         pb:=@b[1];
123.         pc:=@c[1];
124.       for i:=la-1 downto 0 do
125.       begin
126.          carry:=0;ai:=ord(pa[i])-48 ;
127.       for j:= lb-1 downto 0 do
128.       begin
129.         n :=ai*(ord(pb[j])-48)+(ord(pc[i+j+1])-48)+carry;
130.         carry :=_Div[n];ord(pc[i+j+1]):=_Mod[n];
131.       end; {next j}
132.        ord(pc[i]):=ord(pc[i])+carry ;
133.       end; {next i}
134.       fact:=c;
135.       if c[1]='0' then fact:=copy(c,2,length(c)-1) ;
136.       end;{next z}
137.        factorial:=fact;
138.       end;  {function factorial}
139.  
140.  
141.    //  ======== test functions fibonacci and factorial ========= //
142.    var
143.     D1,D2: TDateTime;
144.      ans:ansistring;
145.      num:longint;
146.       z:integer;
147.  
148.     begin
149.      {=================== Test Fibonacci  ============}
150.      num:=50000;
151.     writeln('Hang on...  creating fibonacc1 ',num);
152.  
153.      d1:=Now ;
154.      ans:= Fibonacci(num);
155.      d2:=Now;
156.       writeln(ans);
157.       Writeln( MilliSecondsBetween(D1, D2), ' milliseconds');
158.  
159.      writeln('Press enter to continue...');
160.       readln;
161.  
162.       for z:=1 to 200 do
163.       begin
164.       writeln('fib  ',z,'   ',fibonacci(z));
165.       end;
166.  
167.       writeln('Press enter to continue...');
168.       readln;
169.  
170.        {=================== Test factorial  ============}
171.        num:= 5000;
172.        writeln('factotial ',num,'  =  ');
173.        D1:=now;
174.        ans:=  factorial(num);
175.        D2:=now;
176.        writeln(ans);
177.        writeln( MilliSecondsBetween(D1, D2), ' milliseconds');
178.        writeln('Done, press enter to end');
179.        readln;
180.        end.
181.  
182.  
183.  
184.  
185.  
186.