Must we do it recursively?

The code below uses Binet's Formula for $F_n = \displaystyle\frac{\big( \frac{1+\sqrt{5}}{2}\big)^n-\big( \frac{1-\sqrt{5}}{2}\big)^n}{\sqrt{5}}$

and the fact that $\displaystyle\big( \frac{1-\sqrt{5}}{2}\big)^n$ is essentially 0 at $n = 10^{12}$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int main(){@autoreleasepool{
        long double five = sqrtl(5) ;
        long double number = powl(10,12)*log10l((1+five)/2) ;
        number -= log10l(five) ;

        number = number - floorl(number) ;

        number += 9 ;

        NSLog(@"%.21Lg", powl(10,number)) ;

    }
    return 0;
}

Also note that for number n in base 10, the number of digits is $\log_{10}{n}$ and the first digits are representative of your precision with $\displaystyle 10^{( \log_{10}{n}) - \lfloor\log_{10}{n}\rfloor}$