Divide and Conquer Fibonacci

Can someone help me understand how to do the Fibonacci using divide and conquer through recursion?
If my input is Fib(6) what exactly am I trying to divide?
saygaproAsked:
Who is Participating?
 
Infinity08Connect With a Mentor Commented:
>> what exactly am I trying to divide?

Divide and conquer doesn't really work for a Fibonacci series, because you'll end up doing everything twice. Rather go for a simple straight recursion (or better yet, just a loop).
0
 
ozoCommented:
f(0) =1
f(1) = 1
f(n) = f(n-1) + f(n-2)
0
 
saygaproAuthor Commented:
I understand the below code but this isn't divide and conquer correct?
I have no clue how to transform this into a divide and conquer algorithm.
Can you give me any other hints?

public static int fib(int n)
{
     if ( n ==1 || n==0)
            return n;
     else
          return fib(n-1) + fib(n-2);
}
0
[Webinar] Improve your customer journey

A positive customer journey is important in attracting and retaining business. To improve this experience, you can use Google Maps APIs to increase checkout conversions, boost user engagement, and optimize order fulfillment. Learn how in this webinar presented by Dito.

 
Hamed ZaghaghiConnect With a Mentor ProgrammerCommented:
fibonacci with divide and conquer !!!!!  imposible!
0
 
ozoConnect With a Mentor Commented:
A more efficient recursion could be
f(2n) = f(n)*(f(n+1)+(f(n-1))
0
 
ozoConnect With a Mentor Commented:
or
f(2n) = f(n+1)²-f(n-1)²
0
 
ozoCommented:

f(2n+1) = f(n+1)²+f(n)²
0
All Courses

From novice to tech pro — start learning today.