java - Time efficient recursion for Magical Number -

i solving magical number problem number @ nth position sum of previous 3 numbers, minus 1. example: 0 1 1 1 2 3 5 9 16.... , on.

i solved in 2 ways.

code 1) using recursion

int magicnumber(int n){     int f = 0;     if (n == 1)         return 0;     else if (n > 1 && n <= 4)         return 1;     else         f = (magicnumber(n-1) + magicnumber(n-2) + magicnumber(n-3)) - 1;     return f; } 

code 2) using array

void magicnumber(int n){     long arr[] = new long[100];     int i=1;     for(i = 1; <= n; i++)     {         if(i==1)             arr[i] = 0;         else if(i>1&&i<=4)             arr[i] = 1;         else             arr[i] = (arr[i-1] + arr[i-2] + arr[i-3]) - 1;     }     system.out.println("result : "+arr[n]); } 

code 1 works fine when provide small integer number program, hangs input of bigger integer numbers , code 2 runs fine without problem.

so need suggestions, how can improve performance of recursion program code 1?

you can speed recursion this:

int magicnumber2(int n, int a, int b, int c){   if (n <= 1) return a;   return magicnumber2(n - 1, b, c, + b + c - 1); }  int magicnumber(int n) {   magicnumber2(n, 0, 1, 1); }