C#•7mo ago

Understanding Recursion for a complete beginner (Fibonacci Series)

Hey everyone, I hope you are doing well I need some help understanding recursion, can someone explain to me how the base case of the Fibonacci sequence would occur? What would be the base case and then the recursive case?

11 Replies

Jimmacle•7mo ago

do you have a specific algorithm that you're looking at?

ArrayOP•7mo ago

cs private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

cs private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

I posted the solution but I'd like to get a better understanding on what is really happening here

Jimmacle•7mo ago

try running through it by hand, trace what happens when you call Fibonacci(2) for example

ArrayOP•7mo ago

Sorry I am very new to coding, what do you mean by trace?

Jimmacle•7mo ago

my classes called it a "desk check" basically run the code by writing out the process on paper so for Fibonacci(2) you'd go through it like Fibonacci(2) -> Fibonacci(2 - 1) + Fibonacci(2 - 2) Fibonacci(2 - 1) -> Fibonacci(1) -> 1 Fibonacci(2 - 2) -> Fibonacci(0) -> 0 Fibonacci(2) -> 1 + 0 Fibonacci(2) = 1

ArrayOP•7mo ago

Sure, my teacher has used the example of recursion through a factorial which is understand a bit What basically happens is that the stack stores the base case as factorial 1 and 0 = 1 then each time you multiply it by 1 more then the factorials below (2 * 1)

Pobiega•7mo ago

the idea is that your fib(2) call makes 2 other fib calls, as such:

Pobiega•7mo ago

it quickly grows a lot more complex 😄

Pobiega•7mo ago

so for Fib(4) there are 8 "internal" fib calls we can easily demonstrate this with the following code

MODiX•7mo ago

Pobiega

REPL Result: Success

var fib4 = Fib(4);

int Fib(int n)
{
    Console.WriteLine($"Fib({n})");
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

var fib4 = Fib(4);

int Fib(int n)
{
    Console.WriteLine($"Fib({n})");
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

Console Output

Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(1)
Fib(0)

Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(1)
Fib(0)

Compile: 453.561ms | Execution: 76.074ms | React with ❌ to remove this embed.

Gaming

Programming

Understanding Recursion for a complete beginner (Fibonacci Series)