大神们过来了帮帮我（关于Scanner和引用引用传递的知识）

大神们过来了帮帮小弟我（关于Scanner和引用引用传递的知识）
题目如下；
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
数据规模与约定
1 <= n <= 1,000,000。

我的代码；

import java.util.Scanner;
public class Case03 
{

	public static void main(String[] args) 
	{
		Scanner input = new Scanner(System.in);
		System.out.println("请输入一个正数");
		int n = input.nextInt();
		int count=0;
		if (n>=1&&n<=1000000) 
		{
			int a =  count(n);
			System.out.println("余数为"+a);
		}
		else
			System.out.println("请输入1~1000000之间的数");
	}
		public static int count(int n)
		{
			if (n!=1&&n!=2) 
			{
				return (count(n-1)+count(n-2))%10007;
			}
			else
				return 1;
		}
} 

正确代码如下；

import java.util.Scanner;
public class My09
{
    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt() ;  
        int[] a = new int[num+2] ;
        a[1] = a[2] = 1;
        if (num == 1) {
            a[num] = 1 ;
        }else if (num == 2) {
            a[num] = 1 ;
        }else {
            for (int i = 3; i <= num; i++) 
            {
                a[i] = (a[i - 1] + a[i - 2]) % 10007;
            }
        }
        System.out.println(a[num]);
    }	
}

问题如下；
1、在第二个代码中当num=1000000000时，为什么会出现这样的的错误的？这的数也没有超出int类型啊！，那是什么原因了？
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at org.ixh.cui.My09.main(My09.java:10)

2、为什么当输入的整数越大时第一个代码的运行速度会变的那么慢，而第二个代码没什么明显的变化，这是什么原因了？
请大神们具体说明情况！！！
------解决思路----------------------
1. 计算的数据量太大，导致 java虚拟机堆溢出，可以在run -> run configurations -> Arguments 的VM arguments里设置启动参数，把栈内存分配大点试试。比如，加上 –Xms128m –Xmx512m –XX:PermSize=64m –XX:MaxPermSize=128m
2. 我感觉，大量的递归调用，在不断的压栈过程中，栈容量越来越大，运行速度就会越来越慢，最后抛出栈溢出异常
------解决思路----------------------
尽量不要使用递归算法，它会不断保存当前现场然后进入下一个代码段，不断重复，然后还要依次返回
中间这些现场变量的保存是很消耗内存的
用一般循环的方式不存在这个问题，只需要指定的几个变量空间就可以了

------解决思路----------------------
1.应该是开不了这么大的数组    放在main函数外面可以   全局变量
2.第二个是先把所有的都算出来，存在数组中，需要哪一个输出哪一个，时间复杂度是线性的，速度快。而第一个用递归，每找一个都要重新计算并且递归要调用栈什么什么的很麻烦。。。
个人也是小白，不对的地方批评指正