Post Reply 
Fibonacci sequence by recursive algorithm fail
04-20-2015, 06:42 PM (This post was last modified: 04-21-2015 02:27 PM by compsystems.)
Post: #1
Fibonacci sequence by recursive algorithm fail
The Fibonacci sequence by recursive algorithm fail in program type CAS, why?

http://en.wikipedia.org/wiki/Fibonacci_number

HPPrime CAS CODE
Code:

#CAS
    fibo(n):=
    BEGIN
        // versión 0.0.1 April 20
            If n≤1 Then 
                    Return n;
            Else
                    Return (fibo(n-1)+fibo(n-2));
            End;
    END;
#end

fibo(16) → "Error: Bad argument count"

HPPrime NUM CODE
Code:
EXPORT fibo(n)
BEGIN
  // versión 0.0.1 April 20
    If n≤1 Then 
        Return n;
    Else
        Return (fibo(n-1)+fibo(n-2));
    End;
END;
fibo(16) → 987


TI68K CODE
Code:

fibo(n)
Func
  Local tm
  ©startTmr() → tm
  If n≤1 Then
      Return n
  Else
      Return fibo(n-1)+fibo(n-2)
      ©checkTmr( sc )
  EndIf
EndFunc
fibo(16) → 987

other algorithms

http://www.hpmuseum.org/forum/thread-316...=Fibonacci
Find all posts by this user
Quote this message in a reply
04-20-2015, 07:57 PM (This post was last modified: 04-20-2015 07:57 PM by Tim Wessman.)
Post: #2
RE: Fibonacci sequence by recursive algorithm fail
The CAS is case sensitive. There is no function or keyword called "Return"
Code:

#CAS
    fibo(n):=
    begin
        // versión 0.0.1 April 20
            if n≤1 then 
                    return n;
            else
                    return (fibo(n-1)+fibo(n-2));
            end
    end;
#end

TW

Although I work for the HP calculator group, the views and opinions I post here are my own.
Find all posts by this user
Quote this message in a reply
04-20-2015, 09:26 PM (This post was last modified: 04-20-2015 09:43 PM by compsystems.)
Post: #3
RE: Fibonacci sequence by recursive algorithm fail
catalog shows only one, in capitals RETURN, plus the code with tabulation fails, but left aligned says that syntax OK, but fails to run again.

Who has run successfully?

Please improve part of tabulation (compiler)
Find all posts by this user
Quote this message in a reply
04-20-2015, 09:58 PM (This post was last modified: 04-20-2015 10:01 PM by Didier Lachieze.)
Post: #4
RE: Fibonacci sequence by recursive algorithm fail
(04-20-2015 09:26 PM)compsystems Wrote:  Who has run successfully?
I just entered it on my Prime and it's working fine with one addition: there is a missing ";" after the first "end" in your code. And I used the space key for the indentation and didn't get any error.
Find all posts by this user
Quote this message in a reply
04-20-2015, 11:45 PM
Post: #5
RE: Fibonacci sequence by recursive algorithm fail
TIM and compsystems:

The program runs fine using RETURN (i.e., in capitals). Be sure to put the ; as mentioned by Didier.

Bill_G
Find all posts by this user
Quote this message in a reply
04-21-2015, 12:25 AM
Post: #6
RE: Fibonacci sequence by recursive algorithm fail
I think that one other thing to take into account is that, for the CAS function, the recursive function calls setting (CAS settings, page 2, line 3) must be set to a number at least that of the parameter value n in fibo(n). Default setting seems to be 9, to fibo(10) returns "Running non recursive evaluator."
Find all posts by this user
Quote this message in a reply
04-21-2015, 05:13 AM
Post: #7
RE: Fibonacci sequence by recursive algorithm fail
(04-20-2015 11:45 PM)Bill_G Wrote:  TIM and compsystems:

The program runs fine using RETURN (i.e., in capitals). Be sure to put the ; as mentioned by Didier.

Bill_G

Font type differentiation of names is a trap that catches all practitioners.
Find all posts by this user
Quote this message in a reply
04-21-2015, 05:49 AM
Post: #8
RE: Fibonacci sequence by recursive algorithm fail
(04-20-2015 07:57 PM)Tim Wessman Wrote:  The CAS is case sensitive. There is no function or keyword called "Return"
Code:

#CAS
    fibo(n):=
    begin
        // versión 0.0.1 April 20
            if n≤1 then 
                    return n;
            else
                    return (fibo(n-1)+fibo(n-2));
            end
    end;
#end

Font type differentiation of names is a trap that catches all practitioners.
Find all posts by this user
Quote this message in a reply
04-21-2015, 01:57 PM
Post: #9
RE: Fibonacci sequence by recursive algorithm fail
I think a case could be made that a CAS program is not a good construct for this kind of algorithm. Personally, I think that CAS programs are better suited for CAS exclusive purposes (remaining within the CAS environment).

I get that recursive activity is the point of this presentation, but the steps involved are better implemented in a Home program, rather than a CAS variable. The CAS approach, in this case, is a bit like building a pipeline to a beer brewery across town, rather than just using containers to get the desired beer home.

Here is a simple means to the same end, which can be embellished as necessary, or if needed as a subroutine, all the while avoiding CAS restrictions :

Code:

EXPORT fibo(n)
BEGIN
  return n!;  // or substitute Gamma(n+1) for n! 
END;
Find all posts by this user
Quote this message in a reply
04-21-2015, 02:20 PM (This post was last modified: 04-21-2015 03:31 PM by compsystems.)
Post: #10
RE: Fibonacci sequence by recursive algorithm fail
Sorry for my bad English

I found the real problem, works well (CAS PROG) if everything is written in lowercase or all uppercase and, in single shift and does not work (if then else end → If  Then Else End)

HP TEAM must review the compiler (CAS PROG) for next versión of firmware, the following code is successfully compiled, but fails to run, you must verify that the commands are well written

Code:
#CAS
    fibo_cas(n):=
    begin
        // version 0.0.2 April 22
            If n≤1 Then 
                    return(n);
            Else
                    return(fibo_cas(n-1)+fibo_cas(n-2));
            End;
    end;
#end

fibo_cas(16) → "Error: Bad argument count" ? What affects capitalized If, the algorithm?

-------

I found a serious problem, if two functions prog HOME or prog CAS, has the same name appears only version HOME. The only solution is to support working directories for next versión of firmware (DIR nameDir .... EndDir) do you agree?

PROBLEM WITH TWO FOLLOWING CODES, try it yourself
Code:
#CAS
    fibo(n):=
    begin
        // version 0.0.2 April 22
            if n≤1 then 
                    return(n);
            else
                    return(fibo(n-1)+fibo(n-2));
            end;
    end;
#end


Code:
export fibo(n)
begin
  // versión 0.0.2 April 22
    if n≤1 then 
        return n;
    else
        return fibo(n-1)+fibo(n-2);
    end;
end;




---------------------

OK codes
Code:
#CAS
    fibo_cas(n):=
    begin
        // version 0.0.2 April 22
            if n≤1 then 
                    return(n);
            else
                    return(fibo_cas(n-1)+fibo_cas(n-2));
            end;
    end;
#end

fibo_cas(16) → 987.0


Code:
export fibo_home(n)
begin
  // versión 0.0.2 April 22
    if n≤1 then 
        return n;
    else
        return fibo_home(n-1)+fibo_home(n-2);
    end;
end;

Or

Code:
export fibo_home2(n)
Begin
  // versión 0.0.1 April 22
    If n≤1 Then 
        Return n;
    Else
        Return fibo_home2(n-1)+fibo_home2(n-2);
    End;
End;

(04-21-2015 01:57 PM)DrD Wrote:  I think a case could be made that a CAS program is not a good construct for this kind of algorithm. Personally, I think that CAS programs are better suited for CAS exclusive purposes (remaining within the CAS environment).

Just to use one type CAS program if the output is symbolic is obligatory, if only numerical output is optional

For example the following code can not code as HOME program

Code:
#CAS
     printSymbolic Algebraic ():=
     BEGIN
         // versión 0.0.1 April 14 2015 for HP-Prime by compSystems
         print; //© Clear Terminal Window (I/O)
         print( "hpPrime Terminal View, Symbolic Algebraic Printing" );
         print( "" );
         print( "Expr1:" ); f(x):=x^3-2*x^2+1*x-1;
         print( x^3-2*x^2+1*x-1 );
         print( f(x) );
         
         print( "" );
         print( "Expr2:" );
         print( x^3-2*x^2+1*x-1 | x=y );
         print( f(y) );
         
         print( "" );
         print( "Press any key to continue" ); freeze; wait;
         print( "Expr3:" ); g(x):=1/(x+3);
         print( g(x) );
         
         print( "Expr4:" );
         print( "f(g(x))=" );
         print( f(g(x)) );
         
         print( "g(f(x))=" );
         print( g(f(x)) );
          
         print( "Expr4:");
         print( (x^4-x^3-6*x^2+11*x-6)/x^6+(x^3-6*x^2+11*x-6 | x=y) );
         return "Done"
     END;
 #end

a tip, if the return command have parentheses, returns the output is in exact format, otherwise the approx
Code:
#CAS
    fibo_cas(n):=
    begin
        // version 0.0.2 April 22
            if n≤1 then 
                    return n;
            else
                    return fibo_cas(n-1)+fibo_cas(n-2);
            end;
    end;
#end
Find all posts by this user
Quote this message in a reply
04-21-2015, 04:00 PM
Post: #11
RE: Fibonacci sequence by recursive algorithm fail
(04-21-2015 02:20 PM)compsystems Wrote:  
(04-21-2015 01:57 PM)DrD Wrote:  I think a case could be made that a CAS program is not a good construct for this kind of algorithm. Personally, I think that CAS programs are better suited for CAS exclusive purposes (remaining within the CAS environment).

Just to use one type CAS program if the output is symbolic is obligatory, if only numerical output is optional

For example the following code can not code as HOME program

Code:
#CAS
     printSymbolic Algebraic ():=
     BEGIN
         // versión 0.0.1 April 14 2015 for HP-Prime by compSystems
         print; //© Clear Terminal Window (I/O)
         print( "hpPrime Terminal View, Symbolic Algebraic Printing" );
         print( "" );
         print( "Expr1:" ); f(x):=x^3-2*x^2+1*x-1;
         print( x^3-2*x^2+1*x-1 );
         print( f(x) );
         
         print( "" );
         print( "Expr2:" );
         print( x^3-2*x^2+1*x-1 | x=y );
         print( f(y) );
         
         print( "" );
         print( "Press any key to continue" ); freeze; wait;
         print( "Expr3:" ); g(x):=1/(x+3);
         print( g(x) );
         
         print( "Expr4:" );
         print( "f(g(x))=" );
         print( f(g(x)) );
         
         print( "g(f(x))=" );
         print( g(f(x)) );
          
         print( "Expr4:");
         print( (x^4-x^3-6*x^2+11*x-6)/x^6+(x^3-6*x^2+11*x-6 | x=y) );
         return "Done"
     END;
 #end

For me it is not completely clear what you are trying to do. However, I synthesized your larger program into just this fragment, which (I think) is what you may be asserting, and it IS in HOME mode. The general idea is interaction with string / expression / number. You can accomplish the rest of your program with similar workflow:

Code:

EXPORT Algy()
BEGIN
  local x:=3;  //  Just making an example here

// versión 0.0.1 April 14 2015 for HP-Prime by compSystems  
  print(); //© Clear Terminal Window (I/O)
  print("hpPrime Terminal View, Symbolic Algebraic Printing");
  print("");

  //  <<  Cut larger portion of your program to only Expr1 fragment >>
  //  <<  You can build on this theme, if it is suitable.                      >>
  //  <<  I think this may be the general idea you're after(?)            >>

  Expr1:="x^3-2*x^2+1*x-1"; 
  print(Expr1+ " "+" = "+EXPR(Expr1));  // EXPR is in help doc's

  //  Of course, you can perform ANY defined operation(s), the above is just an example.

  return "Done";
END;
Find all posts by this user
Quote this message in a reply
04-22-2015, 02:37 AM
Post: #12
RE: Fibonacci sequence by recursive algorithm fail
(04-21-2015 01:57 PM)DrD Wrote:  I think a case could be made that a CAS program is not a good construct for this kind of algorithm. Personally, I think that CAS programs are better suited for CAS exclusive purposes (remaining within the CAS environment). I get that recursive activity is the point of this presentation, but the steps involved are better implemented in a Home program, rather than a CAS variable. The CAS approach, in this case, is a bit like building a pipeline to a beer brewery across town, rather than just using containers to get the desired beer home.

Actually, CAS is REQUIRED for calculating Fibonacci numbers with more than 12 digits. CAS supports integers of almost unlimited length. Home is limited to a mere 12 digits.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
04-22-2015, 10:20 AM
Post: #13
RE: Fibonacci sequence by recursive algorithm fail
(04-21-2015 01:57 PM)DrD Wrote:  Here is a simple means to the same end, which can be embellished as necessary, or if needed as a subroutine, all the while avoiding CAS restrictions :

Code:

EXPORT fibo(n)
BEGIN
  return n!;  // or substitute Gamma(n+1) for n! 
END;

Fibonacci numbers and the factorial are different, aren't they?

Marcus von Cube
Wehrheim, Germany
http://www.mvcsys.de
http://wp34s.sf.net
http://mvcsys.de/doc/basic-compare.html
Find all posts by this user
Quote this message in a reply
04-22-2015, 12:41 PM
Post: #14
RE: Fibonacci sequence by recursive algorithm fail
Quite right.

Code:

// ======================================
//  Fibonacci Sequence Generator
//
//  Input: length of sequence
//  Output: Fibonacci List
//
// ======================================

EXPORT fibo(n)
BEGIN

  local j:=3;  
  HDigits:=0;
  L1:={0};
  
  if n==0 then return L1; end; 
  if n==1 then return concat(L1,1); end;

  print();
  L1:={0,1};
  repeat    
    L1:=concat(L1,L1(j-1)+L1(j-2));
    j:=j+1;
  until j==n+1;
  print(L1);
  
END;
Find all posts by this user
Quote this message in a reply
04-23-2015, 02:21 AM
Post: #15
RE: Fibonacci sequence by recursive algorithm fail
Code:
#CAS
    nfibo_cas(n):=
    begin
        // /!\ n = N+
        //    version 0.0.3 April 22
        if n≤1 then
            return(n);
            else
            return(nfibo_cas(n-1)+nfibo_cas(n-2));
        end;
    end;
#end

nfibo_cas(28) → 317811
nfibo_cas(30) → BUSY → 832040
nfibo_cas(100) → running non recursive evaluator

What means the above output?

nfibo_cas(100) → ¨ERROR MEMORY¨ (ti68k calcs)
Find all posts by this user
Quote this message in a reply
04-23-2015, 06:44 AM
Post: #16
RE: Fibonacci sequence by recursive algorithm fail
If you run a recursive program, at each recursive call, the environment is saved on a stack. But this stack can not grow dynamically, therefore if you want to do more embedded recursive calls, you must change the way evaluation is done (and save environment in the heap).
Find all posts by this user
Quote this message in a reply
04-23-2015, 02:09 PM
Post: #17
RE: Fibonacci sequence by recursive algorithm fail
but better display a message that says, ¨stack overflow¨ or something similar.

I consider it a BUG that the program editor, says that the compilation was successful without checking the syntax of each command, each are sensitive to lowercase and uppercase, I took a long time to detect that had to write, If Then End as if then end or IF THEN END
Find all posts by this user
Quote this message in a reply
04-23-2015, 06:58 PM
Post: #18
RE: Fibonacci sequence by recursive algorithm fail
(04-23-2015 02:09 PM)compsystems Wrote:  but better display a message that says, ¨stack overflow¨ or something similar.
Stack overflow would be misinterpreted as an error.
Find all posts by this user
Quote this message in a reply
04-24-2015, 08:37 PM (This post was last modified: 04-24-2015 08:37 PM by compsystems.)
Post: #19
RE: Fibonacci sequence by recursive algorithm fail
¨Runtime Error: Maximum recursion depth (stack) exceded¨

Who proposes another best output message?
Find all posts by this user
Quote this message in a reply
04-25-2015, 06:12 AM
Post: #20
RE: Fibonacci sequence by recursive algorithm fail
No, because running non recursive evaluator is not a runtime error, your program will still run (it will run slower).
You can't expect a recursive Fibonacci program to finish with n=100 (unless you have some remember table), because the time required is proportionnal to Fibonacci(100) that's about 1e20.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)