C#•4mo ago

recursion

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

81 Replies

riggerOP•4mo ago

ive got this so far but thats it

danilwaffle•4mo ago

you miss THE thing recursion

jcotton42•4mo ago

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

riggerOP•4mo ago

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

jcotton42•4mo ago

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

riggerOP•4mo ago

...

jcotton42•4mo ago

plus the base cases 1 and 0

danilwaffle•4mo ago

i actually forgot this

riggerOP•4mo ago

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

danilwaffle•4mo ago

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

jcotton42•4mo ago

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

riggerOP•4mo ago

mkay

jcotton42•4mo 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

riggerOP•4mo ago

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

riggerOP•4mo ago

so is this fine?

riggerOP•4mo ago

im ngl im barely understanding my own code

jcotton42•4mo 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

riggerOP•4mo ago

idek what that is! but thanks

jcotton42•4mo ago

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

riggerOP•4mo 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•4mo ago

it gives 2, not 3

riggerOP•4mo ago

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

jcotton42•4mo 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

riggerOP•4mo ago

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

jcotton42•4mo ago

yes

riggerOP•4mo ago

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

jcotton42•4mo ago

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

riggerOP•4mo ago

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

riggerOP•4mo ago

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

jcotton42•4mo ago

were you told to use an array?

riggerOP•4mo 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•4mo 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

riggerOP•4mo 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•4mo ago

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

riggerOP•4mo ago

OOOH x++ right wait no uh

riggerOP•4mo ago

...?

jcotton42•4mo ago

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

riggerOP•4mo ago

so... uh

jcotton42•4mo ago

there's a second int variable in that code snippet

riggerOP•4mo ago

int[100]?? or i

jcotton42•4mo ago

i

riggerOP•4mo ago

right

riggerOP•4mo ago

so.. this?

jcotton42•4mo ago

you're still setting [x] every time

riggerOP•4mo ago

oops

riggerOP•4mo ago

so this?

riggerOP•4mo ago

what does this even do 😭

jcotton42•4mo ago

try it and see

riggerOP•4mo ago

jcotton42•4mo 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

riggerOP•4mo ago

this is new

riggerOP•4mo ago

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

jcotton42•4mo ago

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

riggerOP•4mo ago

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

jcotton42•4mo 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

riggerOP•4mo ago

jcotton42•4mo ago

those are not valid indicies, so you get an IndexOutOfRangeException

riggerOP•4mo ago

so i start with 2

jcotton42•4mo ago

yes, you already set what 0 and 1 are anyhow

riggerOP•4mo ago

ok im trying it again moment of truth

jcotton42•4mo 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)

riggerOP•4mo 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•4mo ago

$code

MODiX•4mo 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/

riggerOP•4mo 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]);
    }
}

riggerOP•4mo ago

and these r my outputs

Moonlit•4mo 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•4mo ago

your functions appear to disagree with each other

riggerOP•4mo 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•4mo ago

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

jcotton42•4mo ago

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

riggerOP•4mo ago

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

jcotton42•4mo 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

riggerOP•4mo ago

YOURE A GODSEND 🙏

riggerOP•4mo 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•4mo 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

riggerOP•4mo 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•4mo 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•4mo ago

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

Moonlit•4mo 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?