Jump to content




Recent Status Updates

View All Updates

Developed by Kemal Taskin
Photo
- - - - -

Fibonacci with no recursion for fun

fibonacci recursion

  • Please log in to reply
14 replies to this topic

#1 HAL 9000

HAL 9000

    CC Newcomer

  • Just Joined
  • PipPip
  • 11 posts

Posted 23 June 2008 - 12:27 AM

I made a non recursive Fibonacci function in C for fun because it can't solve 100 fast with recursion.
Did anyone else besides me do it this way
#include<stdio.h>

/*prototypes*/
double fib(int n);

int main(void)
{
	int i;
	
	for(i = 0;i <= 100;++ i)
	{
		printf("%1.0f \n",fib(i));
	}

	return 0;
}

/*non recursive fibonacci function*/
double fib(int n)
{
	double prev = -1;
	double result = 1;
	double sum;
	int i;
	
	for(i = 0;i <= n;++ i)
	{
		sum = result + prev;
		prev = result;
		result = sum;
	}
	
	return result;
}

Edited by HAL 9000, 23 June 2008 - 12:32 AM.

  • 0

#2 samy

samy

    CC Newcomer

  • Just Joined
  • PipPip
  • 13 posts

Posted 23 June 2008 - 03:36 AM

Hi HAL 9000!

Your code looks good. I have not tried your code but it seems to be working. I want to ask a question (just for sharing fun along with you) as to how long your code can extent i.e until what number.
  • 0

#3 WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderator
  • 16,935 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 23 June 2008 - 08:03 AM

I tend to do factorials, permutations, and combinations in loops for the same reason.
  • 0
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#4 samy

samy

    CC Newcomer

  • Just Joined
  • PipPip
  • 13 posts

Posted 24 June 2008 - 03:21 AM

Hi WingedPanther!

Would you like to share the fun with us by giving the program for factorials, permutations, and combinations?
  • 0

#5 John

John

    CC Mentor

  • Moderator
  • 4,450 posts
  • Location:New York, NY

Posted 24 June 2008 - 03:50 AM

I made a non recursive Fibonacci function in C for fun because it can't solve 100 fast with recursion.
Did anyone else besides me do it this way

#include<stdio.h>

/*prototypes*/
double fib(int n);

int main(void)
{
	int i;
	
	for(i = 0;i <= 100;++ i)
	{
		printf("%1.0f \n",fib(i));
	}

	return 0;
}

/*non recursive fibonacci function*/
double fib(int n)
{
	double prev = -1;
	double result = 1;
	double sum;
	int i;
	
	for(i = 0;i <= n;++ i)
	{
		sum = result + prev;
		prev = result;
		result = sum;
	}
	
	return result;
}

A few months ago, I posted this:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;

//Non-recrusive: O(1)
unsigned long fib(int n)
{
     return (1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n));
}

//Recrusive: O(n)
unsigned long fib2(int n)
{
    if(n <= 2) return 1;
    else return fib2(n - 1) + fib2(n - 2);
}

//Iterative: O(n)
unsigned long fib3(int n)
{
    int u = 0;
    int v = 1;
    int i, t;

    for(i = 2; i <= n; i++)
    {
        t = u + v;
        u = v;
        v = t;
    }
    return v;        
}

Edited by dargueta, 26 November 2010 - 02:12 PM.
Fixed code tags

  • 0

#6 WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderator
  • 16,935 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 24 June 2008 - 09:27 AM

Hi WingedPanther!

Would you like to share the fun with us by giving the program for factorials, permutations, and combinations?


int factorial(int n){
  int fact=1;
  for (int i=1;i<=n;i++) fact*=i;
  return fact;
}

int permutation(int n,r){
  int perm=1;
  for (int i=n-r+1;i<=n;i++) perm*=i;
  return perm;
}

int combination(int n,r){
  return permutation(n,r)/factorial(r);
}

  • 0
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#7 samy

samy

    CC Newcomer

  • Just Joined
  • PipPip
  • 13 posts

Posted 25 June 2008 - 03:53 AM

Hi WingedPanther!

Your code is awesome. I think you have a great mind.

Good going. :cool:
  • 0

#8 WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderator
  • 16,935 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 25 June 2008 - 09:06 AM

It's a side-effect of being a mathematician: math algorithms come REALLY easily to me.
  • 0
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#9 samy

samy

    CC Newcomer

  • Just Joined
  • PipPip
  • 13 posts

Posted 26 June 2008 - 04:27 AM

Hi WingedPanther!

I think you love mathematics. Have you tried some thing like derivatives or integrations, sine, cosine, etc.
  • 0

#10 WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderator
  • 16,935 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 26 June 2008 - 07:41 AM

I've got a master's in math... yes, I love math :)
  • 0
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#11 G_Morgan

G_Morgan

    CC Devotee

  • Just Joined
  • PipPipPipPipPipPip
  • 442 posts

Posted 26 June 2008 - 08:54 AM

Out of interest why are you returning a double?

//edit - the OP that is.//
  • 0

#12 Roman Y

Roman Y

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 196 posts

Posted 26 November 2010 - 07:21 AM

hehe was searching the web yesterday in search for none recursive fibonacci function all of the sites that I've come thought of none recursive as iterative, but what I meant was a none recursive from the mathematical point of view. Anyway I have developed the function in my math class today. So here is the function (I'm not writing the whole file just the function should work in most languages with standard libraries):
double fibonacci(int n)
{
	return (((1/sqrt(5))*(pow((1+sqrt(5))/2, n)) - ((1/sqrt(5))*(pow((1-sqrt(5))/2, n)))));
}

and it should also be faster than the iterative and recursive functions (programming wise).
  • 0





Also tagged with one or more of these keywords: fibonacci, recursion