is my work correct?...simple function

This is a discussion on is my work correct?...simple function within the C Programming forums, part of the General Programming Boards category; a recursive function int fibo(int n) that returns the nth fibonacci number. i dont really quite get this..so here goes ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    21

    is my work correct?...simple function

    a recursive function int fibo(int n) that returns the nth fibonacci number.

    i dont really quite get this..so here goes


    Code:
    int fibo (int n)
    {
    
    return fibo(n-1) + fibo(n-2);
    
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,451
    You need a simple case to stop the recursion.
    Like
    if ( n <= 1 ) return n;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    You need something like this:
    Code:
    if (n <= 1) 
    {
         return 1;
    }
    If you want to stop it at the logical point. Thus the function would be written as this:
    Code:
    int fibo(int n)
    {
         if (n <= 1)
         {
              return 1;
         }
         return fibo(n-1) + fibo(n-2);
    }
    Also, keep in mind that this is zero based, thus fibo(5) returns 8, not 5.
    Edit: Sorry Salem, didn't see your reply
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  4. #4
    Registered User
    Join Date
    Oct 2006
    Posts
    21
    thanks guys...i understand now

    but need to check if my last code is correct..pls read first


    1.function int isPrime(int n ) that returns 1 if n is a prime and 0 otherwise.

    done this already but if needs any corrections here it is:

    Code:
    int isPrime (int n)
    {
    
    if (n%2 != 0)
    
    return 1;
    
    else 
    
    return 0;
    
    }
    2. a recursive function int fibo (int n) that returns the nth fibonacci number

    done this already...thanks for the corrections!

    3. A function int isFiboPrime (int n) that checks whether the nth fibonacci number is a prime.
    This function must call the 1 & 2 functions

    so heres my code:

    Code:
    int isFiboPrime (int n)
    {
    
    if ( fibo(n) ! isPrime(n) )
    printf ("Not Prime");
    
    else
    
    printf ("Prime");
    
    }
    is this correct?

  5. #5
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    isPrime doesn't check for, say, division by three. You need to check for division probably up to half the number. For example, check if 21 is prime. Your function says it is, but if you check for three, you'll realize it's not. In code:
    Code:
    int isPrime (int n)
    {
         for (int i = 2; i <= (n/2); i++)
         {
              if (n%i == 0)
              {
                   return 0;
              }
         }  
    }
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    21
    hmmm i see so it was only for division by 2...i didnt know that...thanks for the correction

    but how about my third function...is it correct?
    Last edited by enjoyincubus; 11-09-2006 at 07:02 AM.

  7. #7
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    Try this:
    Code:
    int isFiboPrime (int n)
    {
         int temp = fibo(n);
         if (isPrime(temp) == 1)
              return 1;
         else
              return 0;
    }
    edit: sorry, you wanted to printf:
    Code:
    void  isFiboPrime (int n)
    {
         int temp = fibo(n);
         if (isPrime(temp) == 1)
              printf ("Prime");
         else
              printf ("Not Prime");
    }
    Last edited by manutd; 11-09-2006 at 07:12 AM.
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  8. #8
    Registered User
    Join Date
    Oct 2006
    Posts
    21
    aaww..i didnt thought of this before...i guess i need more practice

    btw will my answer still works?...

    thanks for corrections

    EDIT: OT, a manchester united fan?...hehe im going for chelsea this season...

  9. #9
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    I don't think so. It will check isPrime, but I don't think (I could be wrong) it would take into acount the fibo(n) call. Also, my method is clearer and makes for more readable code.
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  10. #10
    Registered User
    Join Date
    Oct 2006
    Posts
    21
    ok thans...gonna check this out....

    thanks for the corrections...

    really thanks

  11. #11
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    That's what we're here for!
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  12. #12
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    If no number from 2 to sqrt(n) can divide evenly into n, then n is prime.

    Code:
    for test = 2; test * test < n; ++test
    {
        if n divisible by test  /* not prime, return failure */
    }
    /* n passed all tests, return success */
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  13. #13
    s_p
    s_p is offline
    Registered User
    Join Date
    Nov 2006
    Posts
    1
    I would like to make a small modification to the last post on calculating primes to improve its efficieny. Trying to divide n only by numbers between 2 to sqrt(n) reduces a lot of work, however we can reduce that too, by half if we skip all even numbers other than 2.

    Code:
    int isPrime (int n)
    {     
        if (n == 2)
             return 1;      
        if( n % 2 == 0)
              return 0;      // all even numbers except 2 are non primes
                    
        for (int i = 3; i * i <n; i+=2 )      //check only with odd numbers less than sqrt(n)
        {                          
             if ( n % i == 0)
                 return 0;               
         }
             
         return 1;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  2. Replies: 5
    Last Post: 10-17-2006, 08:54 AM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 08:10 AM
  4. Replies: 2
    Last Post: 06-21-2005, 02:41 PM
  5. Replies: 5
    Last Post: 02-08-2003, 06:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21