Implementing Fibonacci sequence through Recursion

help
1

I have just started studying about recursion and wanted to implement the Fibonacci sequence problem.

Here, I am trying to find the nth number in the Fibonacci sequence. The code snippet is as below:

int static fibonacciRecursion(int n) {
		if(n == 1 || n == 0)
			return n; // or return 1; line of concern
		else
			return fibonacciRecursion(n-1) + fibonacciRecursion(n-2);
	}

I am confused at the return statement of base condition. Should it be

return n;

or

return 1;

Also, I find it hard to come up with the structure of recursive solutions to problems.

Is there any specific way of approaching them?
What are your experiences?
Any specific resources that helped?

Thanks in advance! :slightly_smiling_face:

2

return n

Write down the fibonacci series and trace your program

You are welcome!

1 Like
3

Thanks!

return n; it is then.

And when I was asking about approaches to solving a problem using recursion, I was talking in general about ALL questions that could be solved by recursion. I understood this Fibonacci one and then wrote this code.

I am intrigued about how you all think when coming up with a recursion solution. Do you find the iterative solution and then try to make a recursive one?

Is that all?

4 
int static fibonacciRecursion(int n) {
                 if(n==0)
                            return 0
		if(n == 1 || n == 2)
			return 1; // or return 1; line of concern
		else
			return fibonacciRecursion(n-1) + fibonacciRecursion(n-2);
	}
5

That actually depends. Normally the 1st fibonacci number is considered to be 1 and the 0th is considered 0, then you would return n. But every so often, we use 0 based indexing, as in the fib[0] being the first term, in which case you would return 1 for both.

If you want to become better at recursion, don’t think about whether the function is correct. Assume your function is correct for the previous terms. Then try to prove that if the algorithm gives the correct answer for the other terms I’m calling, will my algorithm be correct here also.

Also check whether you may be calling the same function twice. In which case you should also keep a table storing all the values you already know.

Your current implementation is exponential in time. Since
T(n)=T(n-1)+T(n-2), where T(n) denotes the time taken to find the nth fibonacci number. When n is sufficiently large, it’s takes O(x^n), where
x^n=x^{n-1}+x^{n-2} which is equivalent to x^2=x+1, hence x\approx 1.6. If you remember the answers, your running time falls to O(n) since you are only computing the answer for each term once, and there are n terms.
Hope this helps.

2 Likes
6

Hey @abhishek_vk thanks for the code!

I am really thinking, will it ever reach to the condition of
if(n==0) ?

Won’t it return when n = 1 or 2 ?

7

Thanks @everule1 !

I guess, I will be looking at some more questions based on recursion as well as calculating the complexities.

8

no just if user gives input n = 0 , then what happens ?
Fibo series is 0, 1 , 1 , 2 , 3 , 5 - - - -

9

Oh. Okay. I think it depends on what indexing the user chooses. If it is 0 based then yes. Thanks man :slight_smile:

1 Like