C#•3mo ago

recursion

so I need to make a fibonacci sequence using recursion but bro idk how u achieve that??

81 Replies

rigamortusOP•3mo ago

ive got this so far but thats it

danilwaffle•3mo ago

you miss THE thing recursion

jcotton42•3mo ago

well, what's the definition of the fibonacci sequence? in math terms

rigamortusOP•3mo ago

well you add the previous two terms for the new term ya idk how to implement it

jcotton42•3mo ago

so fib(n) = fib(n - 1) + fib(n - 2) right?

rigamortusOP•3mo ago

...

jcotton42•3mo ago

plus the base cases 1 and 0

danilwaffle•3mo ago

i actually forgot this

rigamortusOP•3mo ago

how did i not think of this... so if n = 1 or 0 i just return 0 right

danilwaffle•3mo ago

just make sure to add 0 check so you won't have stack overflow

jcotton42•3mo ago

Wikipedia says fib(0) = 0 and fib(1) = 1

rigamortusOP•3mo ago

mkay

jcotton42•3mo ago

Starting from 0 and 1, the sequence begins[3] 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

< 0 is undefined, I'd throw an exception for that unless you were told you can assume n >= 0

rigamortusOP•3mo ago

I wasn't but they didn't ask me to have validation so I'm gonna save myself the time and just not..

rigamortusOP•3mo ago

so is this fine?

rigamortusOP•3mo ago

im ngl im barely understanding my own code

jcotton42•3mo ago

the () on the return are unnecessary same for the == true on the if I, personally, would write it like this*

// C# convention for methods is PascalCase
static int FibRecurse(int n, bool print = false)
{
    int fib;
    if (n == 0)
    {
        fib = 0;
    }
    else if (n == 1)
    {
        fib = 1;
    }
    else
    {
        fib = FibRecurse(n - 1) + FibRecurse(n - 2);
    }
    
    if (print)
    {
        // WriteLine instead of Write with an \n
        Console.WriteLine("Fibonacci = {0}", fib);
    }
    return fib;
}

// C# convention for methods is PascalCase
static int FibRecurse(int n, bool print = false)
{
    int fib;
    if (n == 0)
    {
        fib = 0;
    }
    else if (n == 1)
    {
        fib = 1;
    }
    else
    {
        fib = FibRecurse(n - 1) + FibRecurse(n - 2);
    }
    
    if (print)
    {
        // WriteLine instead of Write with an \n
        Console.WriteLine("Fibonacci = {0}", fib);
    }
    return fib;
}

*if it weren't for the print I would return directly from the if/else if/else, also would use string interpolation instead of formatting placeholders, but you might not be allowed to use those

rigamortusOP•3mo ago

idek what that is! but thanks

jcotton42•3mo ago

@'brella boy which part are you having trouble understanding?

rigamortusOP•3mo ago

fib = FibRecurse(n - 1) + FibRecurse(n - 2); like i get that the input is having 1 minused then 2 minused then you add that but like lets say i input 3 im gonna get 3 right??? isnt that.. incorrect?? or am i misunderstanding idk i cant wrap my head around this and i kinda need to since im gonna have to do it iteratively after

jcotton42•3mo ago

it gives 2, not 3

rigamortusOP•3mo ago

its not (3-1) + (3-2)..?

jcotton42•3mo ago

fib(3) = fib(2) + fib(1) fib(1) is already defined 1, so fib(2) + 1 fib(2) = fib(1) + fib(0) fib(0) is already defined as 0, so fib(2) = 1 + 0 = 1 fib(3) = 1 + 1 = 2 the function is calling itself

rigamortusOP•3mo ago

OH so essentially it just repeats until it reaches the base case

jcotton42•3mo ago

yes

rigamortusOP•3mo ago

and then it adds those values together oh im really slow wow

jcotton42•3mo ago

this would just be fib = (n - 1) + (n - 2) which is not the Fibonacci sequence

rigamortusOP•3mo ago

so one small issue... i kinda have to do it iteratively now i tried this

rigamortusOP•3mo ago

but nothing happened i despise and do not understand lists so thats probably the issue

jcotton42•3mo ago

were you told to use an array?

rigamortusOP•3mo ago

nope i wasnt told to use anything but i was given a template which was everythig except the for loop i added that myself so i assume i have to do it in that way

jcotton42•3mo ago

:harold: you don't need a list for an iterative solution, why would they make you do that anyhow, look at the variable you're using in the array indexes in the for loop body

rigamortusOP•3mo ago

idk man.. im NOT supposed to use x? bro this is just it i HATE lists i cant visualise them i cant work with them whenever i employ them its WRONG but i know the syntax so atp its just me

jcotton42•3mo ago

well, x isn't changing during the course of that loop right? so you're setting the same array index on every iteration

rigamortusOP•3mo ago

OOOH x++ right wait no uh

rigamortusOP•3mo ago

...?

jcotton42•3mo ago

no, x is the fib number you're looking for

rigamortusOP•3mo ago

so... uh

jcotton42•3mo ago

there's a second int variable in that code snippet

rigamortusOP•3mo ago

int[100]?? or i

jcotton42•3mo ago

i

rigamortusOP•3mo ago

right

rigamortusOP•3mo ago

so.. this?

jcotton42•3mo ago

you're still setting [x] every time

rigamortusOP•3mo ago

oops

rigamortusOP•3mo ago

so this?

rigamortusOP•3mo ago

what does this even do 😭

jcotton42•3mo ago

try it and see

rigamortusOP•3mo ago

jcotton42•3mo ago

int[] fiblist delcares a variable fliblist with a type of int array new int[100] makes an int array of size 100 and then the = assigns that new array to fiblist

rigamortusOP•3mo ago

this is new

rigamortusOP•3mo ago

so fiblist is an array of size 100 mk that was throwing me off ty

jcotton42•3mo ago

yes, with indicies from 0 to 99 (since arrays start from 0)

rigamortusOP•3mo ago

wait so whats the problem with this is it the fact that the array is only size 100

jcotton42•3mo ago

for (int i = 0 your index var starts with 0 but in the loop body, you try to index into i - 1 and i - 2, which is -1 and -2

rigamortusOP•3mo ago

jcotton42•3mo ago

those are not valid indicies, so you get an IndexOutOfRangeException

rigamortusOP•3mo ago

so i start with 2

jcotton42•3mo ago

yes, you already set what 0 and 1 are anyhow

rigamortusOP•3mo ago

ok im trying it again moment of truth

jcotton42•3mo ago

(in case you haven't been taught about exceptions, it's how C# deals with errors, your course will cover them eventually if it's any good)

rigamortusOP•3mo ago

it does surprisingly but anyways i think it worked let me send the full program i didnt before because i dont know what it does 💀

jcotton42•3mo ago

$code

MODiX•3mo ago

To post C# code type the following: ```cs // code here ``` Get an example by typing $codegif in chat For longer snippets, use: https://paste.mod.gg/

rigamortusOP•3mo ago

public class Program
{

    public static void Main()
    {
        Stopwatch sw = new Stopwatch();

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibrecurse(x, false);
            sw.Stop();
            Console.WriteLine("Recursive {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
        Console.WriteLine("\n\n");

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibiterate(x, false);
            sw.Stop();
            Console.WriteLine("Iterative {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
    }
    //
    // Return the xth fibanacci number using recursion
    // If print set to true, print out debug 
    //
    static int fibrecurse(int x, bool print = false)
    {
        int fib = 0;

        if (x == 0){
            fib = 0;
        }

        else if (x == 1){
            fib = 1;
        }


        else{
            fib = fibrecurse(x - 1) + fibrecurse(x - 2);
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fib);
        return (fib);
    }
    //
    // Return the xth fibanacci number using iteration
    // If print set to true, print out debug 
    //
    static int fibiterate(int x, bool print = false)
    {
        int[] fiblist = new int[100];

        fiblist[0] = 0;
        fiblist[1] = 1;

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);
        return (fiblist[x - 1]);
    }
}

public class Program
{

    public static void Main()
    {
        Stopwatch sw = new Stopwatch();

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibrecurse(x, false);
            sw.Stop();
            Console.WriteLine("Recursive {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
        Console.WriteLine("\n\n");

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibiterate(x, false);
            sw.Stop();
            Console.WriteLine("Iterative {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
    }
    //
    // Return the xth fibanacci number using recursion
    // If print set to true, print out debug 
    //
    static int fibrecurse(int x, bool print = false)
    {
        int fib = 0;

        if (x == 0){
            fib = 0;
        }

        else if (x == 1){
            fib = 1;
        }


        else{
            fib = fibrecurse(x - 1) + fibrecurse(x - 2);
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fib);
        return (fib);
    }
    //
    // Return the xth fibanacci number using iteration
    // If print set to true, print out debug 
    //
    static int fibiterate(int x, bool print = false)
    {
        int[] fiblist = new int[100];

        fiblist[0] = 0;
        fiblist[1] = 1;

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);
        return (fiblist[x - 1]);
    }
}

rigamortusOP•3mo ago

and these r my outputs

Moonlit•3mo ago

I've been enjoying reading this and I won't step on Bewares toes, but.. I would suggest that you kind of set a standard of how you want to write and then stick to it. Like either don't includes {} for single lines or do. EG you use 2 different styles here

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);

It'll help you with reading your own code. If you're new I suggest just always including the {}

jcotton42•3mo ago

your functions appear to disagree with each other

rigamortusOP•3mo ago

oh thats cause i literally didnt write the bottom half its a template yeah thats what im not getting did that sound rude? sorry

Moonlit•3mo ago

No no it's fine, I should have been more attentive

jcotton42•3mo ago

I think you want fiblist[x] instead of x - 1 for the iterative yeah

rigamortusOP•3mo ago

funny cause that was a part of the template but ill try it 😭

jcotton42•3mo ago

because right now your array is set up to have index n = fib term n but you're asking for term n - 1 at the end

rigamortusOP•3mo ago

YOURE A GODSEND 🙏

rigamortusOP•3mo ago

THANK YOU one last favour though wait no nvm i think i actually understand for once the two indexes before the index at i get added together oh right i know whats confusing me how comes returning x works if i was working with i the entire time

jcotton42•3mo ago

when you were working with i in that for loop, you were filling up the array with the fibonacci terms but x is the term you were looking for i'm surprised they made you use an array for the iterative solution tho

rigamortusOP•3mo ago

OOOH SO I FILL UP THE ARRAY USING I AND THEN USE X TO ACTUALLY FIND THE POINT IN THE SEQUENCE!! or rather the array thank u!! once again

Moonlit•3mo ago

Console.WriteLine("Iterative {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib); I didn't know you could do this Is there a reason for using this over just passing them directly in? Genuinely curious Like this? Console.WriteLine("Iterative {x}th Fib={fib}, Elapsed={Elapsed}");

jcotton42•3mo ago

did you mean $"..."? string interpolation in any case, that's how you did it before C# 6 added string interpolation

Moonlit•3mo ago

I didn't notice there was no $ on it But yeh Oh I see, interesting

Gaming

Programming

recursion

Did you find this page helpful?