Fibonacci sequence in C#. Efficient code?

Project Euler Problem 2 (spoiler)

Page 1 of 1

6 Replies - 4222 Views - Last Post: 16 October 2010 - 01:13 PM Rate Topic: ***-- 2 Votes

#1 EvLSnoopY  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 16
  • View blog
  • Posts: 93
  • Joined: 24-November 09

Fibonacci sequence in C#. Efficient code?

Posted 15 October 2010 - 06:44 PM

I recently got into solving the Project Euler Problems. And I just solved the following question:

Quote

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.


Here's the C# code I came up with to solve this problem:
        static int valueOne = 1;
        static int valueTwo = 1;
        static int result = 0;
        static List<int> resultList = new List<int>();
        static int sum = 0;
         
        static void Main(string[] args)
        {
            int count = Environment.TickCount;
            Fibonacci(30);
            foreach ( int i in resultList )
            {
                if ( i % 2 == 0 )
                {
                    sum += i;
                }
            }

            Console.WriteLine(sum.ToString("n0"));
            Console.WriteLine(Environment.TickCount - count + "ms.");
            Console.ReadLine();
        }

        /// <summary>
        /// Creates a Fibonacci Sequence.
        /// </summary>
        /// <param name="terms">
        /// Is the amount of numbers to be added
        /// to the sequence.
        /// </param>
        private static void Fibonacci(int terms)
        {
            result = valueOne + valueTwo;
            resultList.Add(result);
            terms--;

            if ( terms != -1 )
            {
                valueOne = valueTwo;
                valueTwo = result;
                Fibonacci(terms);
            }

            return;
        }


I'm curious as to what solutions you guys come up with. And tell me what you guys think of my solution and if there's any improvements that I can make to my code. Hopefully my post will spark up some good conversation.

Is This A Good Question/Topic? 0
  • +

Replies To: Fibonacci sequence in C#. Efficient code?

#2 janne_panne  Icon User is offline

  • WinRT Dev
  • member icon

Reputation: 428
  • View blog
  • Posts: 1,047
  • Joined: 09-June 09

Re: Fibonacci sequence in C#. Efficient code?

Posted 15 October 2010 - 08:52 PM

Here is a method which I used. Since it was only for that project euler, I didn't really pay attention to code reusability:

        public static void Problem2() {
            long sum = 2;
            int i = 1;
            int j = 2;
            int k;
            while (true) {
                k = i + j;
                i = j;
                j = k;
                if (j > 4000000)
                    break;
                if (j % 2 == 0)
                    sum += j;
            }

            Console.WriteLine(sum);
        }



But about your code:
I wouldn't use Fibonacci as recursive method because it just makes debugging more complicated if something goes wrong. It also makes the logic harder to read in my opinion. Also the use of recursive method might require you to give lots of arguments to the function or use lots of class wide variables instead of just function wide. So in my opinion recursive method should be the last option in many cases. Then you can also return the resultList object rather than have it declared in class scope.

And you don't need empty return statement if your function returns void. But of course it doesn't really matter.
Was This Post Helpful? 1
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Fibonacci sequence in C#. Efficient code?

Posted 16 October 2010 - 03:22 AM

For project Euler stuff, I usually use Python, mostly because it has arbitrary sized numbers as default. I tried doing some in C. In C#, the answers will be pretty close to what you'd see in Java.

Avoid recursion. Be aware that a lot of numbers are much larger than 32 or even 64 bit and you'll to have to deal.

If you answered the question and have an account, you can then look at the posts where people show off their answers.
Was This Post Helpful? 0
  • +
  • -

#4 EvLSnoopY  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 16
  • View blog
  • Posts: 93
  • Joined: 24-November 09

Re: Fibonacci sequence in C#. Efficient code?

Posted 16 October 2010 - 06:04 AM

I looked at other peoples posts and it seemed like a lot of people did what janne_panne wrote. I too came up with the same solution as janne_panne at first, but the reason why I decided to go with a recursive method is because I wanted to come up with another way to solve the problem. I've been watching videos on YouTube and reading about technical interviews. And the interviewer almost always they asks if there is another way to solve the said problem.

With all that said, I keep hearing people say to avoid recursion at all costs. Could someone elaborate on that for me please?
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Fibonacci sequence in C#. Efficient code?

Posted 16 October 2010 - 06:51 AM

Well, not at all costs. Rather, it's good for some solutions, but not others.

Fibonacci is actually a classic example for recursion, because you can basically do a one or two liner for the function. However, it's also a worse case scenario for recursion. To find a solution it continually increases requirements, never decreases, until the last call.

What a mean is this:
Fib(5):
   Fib(4):
      Fib(3):
         Fib(2):
            Fib(1):
               Fib(0):



Each call to a function comes with a little overhead. It's not enough to be worried about, normal programs generally don't dig down so deep enough in a call stack for any repercussions to be had. Recursive functions can and often do.

You call a function that declares some variables. When that function calls itself, it stores data needed to find itself again, pushes some variables on the stack, and fires. Note, it hasn't released the variables.

Say each call to a particular function costs 30 bytes of stack. That's nothing, really, you'd normally never even think about it. However, call yourself enough times and you will fill up that stack. A loop, on the other hand, doesn't build like that and is fairly stable on resources.
Was This Post Helpful? 1
  • +
  • -

#6 EvLSnoopY  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 16
  • View blog
  • Posts: 93
  • Joined: 24-November 09

Re: Fibonacci sequence in C#. Efficient code?

Posted 16 October 2010 - 10:05 AM

Ahh...I see, very well said Baavgai. Thanks for the info. I feel like a complete noob asking this but how do I go about figuring out how much a function costs? do I start off by counting the value of each variable in the function?

For example, if i had 4 integer variables in a function, an int is 4 bytes each so 4*4=16 bytes. Is this the right way to go about doing this?
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Fibonacci sequence in C#. Efficient code?

Posted 16 October 2010 - 01:13 PM

The terms you want to familiarize yourself with are stack and heap. However, unless you're doing Assembly, C, or other low level things, you wont usually find people getting too bothered those kinds of architectural considerations. One of the reasons you use a high level language is so you don't have to worry.

C#, like all .NET managed code, runs on a virtual machine called the CLR. The .NET framework provides "garbage" collection and memory management, among other things. It's hard to precisely gage how recursion might impact the environment. In functional languages, like F#, special considerations are actually made for certain types of recursion.

All you need really know is this; there is over head associate with recursion. The more you do it, the more over head. You, as the programmer, don't have as much control over it as you might like. Simply knowing this should be enough to guide your choices.

Recursion is used in tree walking and divide and conquer algorithms. A nice graphic fill will use recursion. It's used where it provides an elegant solution and the set size manageable. If the set size can get over large, like a game heuristic, other methods will be used even if recursion is the most elegant.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1