CODEWITHSUNDEEP
c#recursionfibonacci
Rajesh Naik
Rajesh Naik

Reputation: 417

Fibonacci Series recursive c# method

I have hard time writing a method which returns a fibonacci series using recursion.

My iterative method is as follows:

public static string Fibonacci(int n)
{

    if (n < 2)
        return "1";
    int[] numbers = new int[n];
    numbers[0]=0;
    numbers[1]=1;
    for (int i = 2; i < n; i++)
    {
        numbers[i] = numbers[i - 1] + numbers[i - 2];

    }
    return string.Join(" ", numbers);
}

I want above method to be changed to recursive call but with same signature ie return type is string and it returns Fibonacci series e.g 0,1,1,2,3,5,8,13,21,34,55

I googled but everywhere I see its done using Console.WriteLine() i.e. values are printed to screen but not returned as string from function.

Thanks

Upvotes: 0

Views: 4788

Answers (1)

Peter Duniho
Peter Duniho

Reputation: 70691

There are, of course, many examples of Fibonacci algorithms on the web, recursive and otherwise. Naturally, the key to a recursive implementation is to take the results from the recursive call, combine that with the current result, and then return that to the caller.

So let's start with the basic Fibonacci idea, with a recursive method that just writes out the numbers as they are generated:

void Fibonacci(int iMinus2, int iMinus1, int count)
{
    if (count == 0) return;

    int current = iMinus2 + iMinus1;

    Console.WriteLine(current);

    Fibonacci(iMinus1, current, count - 1);
}

So then the question is, how do we adjust the above so that it returns a string instead of just writing out the numbers one at a time. Again, remember that the key is to always have a way to combine the current result with the combined result of the previous calls. In this case, that means we want to convert the current number to a string, and prepend that string to the string returned by the recursive call (which is all the numbers after the current number:

string Fibonacci(int iMinus2, int iMinus1, int count)
{
    if (count == 0) return null;

    int current = iMinus2 + iMinus1;
    string nextNumbers = Fibonacci(iMinus1, current, count - 1);

    return nextNumbers != null ?
        current.ToString() + ", " + nextNumbers : current.ToString();
}

Note: the above is a bit more complicated than I'd suggested, because it handles avoiding the addition of a comma when there are no more next numbers. There are other ways to implement this, but I prefer implementing recursive methods such that the terminating condition is handled by the callee rather than the caller.

I leave it as an exercise for the reader to deal with calling the above, and with how to deal with short sequences (i.e. the degenerate case where one is looking at only the first or first two numbers in the sequence). :)


Note: your question sounds a lot like a homework question. If so: these are appropriate on Stack Overflow, but I can't emphasize enough that Stack Overflow should not be considered a substitute for your teacher. We are happy to provide advice and help on homework questions, but it's important that you maintain a relationship with your teacher and seek advice from them so that they better understand where you are having trouble.

Upvotes: 2

Related Questions