Java exam prep - Recursion task -

this task:

use recursion find 13th member of array every member multiplication of last 2 members minus second member. first 2 members 3 , 3.

this came with:

public class zadatak2 {      int array[] = {3,3,0,0,0,0,0,0,0,0,0,0,0};      public zadatak2(){         find13(2);     }      public int find13(int index){         if (index == 13){             system.out.println("member 13: " + array[index-1]);             return 0;         }         else{             array[index] = array[index-1] * array[index-2] - array[1];             system.out.println(index + " : " + array[index]);             return find13(index + 1);         }      } } 

console output see index in array : value :

2 : 6 3 : 15 4 : 87 5 : 1302 6 : 113271 7 : 147478839 8 : 1947758222 9 : 465247871 10 : 818773103 11 : -459621106 12 : 383828239 member 13: 383828239 

but pretty sure made mistake or there better solution. appreciated.

as kevin w. said in comment, in future, "if want review code... use codereview stackexchange". however, here few suggestions.

firstly, keep in mind, problem have lot calculating fibonacci sequence, , there plenty of examples of using recursion calculate members of sequence.

secondly, way built recursive function makes limited being used find 13th number in sequence. begin @ start of sequence , work way 13th number, , doing iterative solution problem minor tweaks make work via recursion.

a better approach generalize function can pass sequence member number parameter, , function calculate via recursion. way start @ target member number , through recursion, members required make member. allows function used calculate number in sequence, not 13th number. has added benefit code can both shrunk , more.

this code:

// index member number; 1 based e.g. index of 1 gives first number in sequence int find(int index) {     if (index == 1 || index == 2)         return 3;      return (find(index - 1) * find(index - 2)) - find(2); } 

when solving problems recursion, method used start problem want solve , break down (as shown in code above), rather start subproblems find larger problem (as code shows).

when applying recursion sequence, write out mathematical definition of sequence first, , must returned recursive function. example, in problem, definition is

a[n] = (a[n-1] * a[n-2]) - a[2]

now take @ solution wrote. returning precisely sequence definition, in terms of recursive function. base case @ beginning of function initial member(s) required calculate rest of sequence. encourage work algorithm through on paper , play see happening.

as final note, algorithm horrendous in terms of run time. there 3 recursive calls per call find(), means finding 13th member on order of 3^13, exponential. exponential algorithms terrible algorithms, , should avoided.

if recursion examined closely can see in order calculate a[n], code calculates a[n-1] , a[n-2]. in order calculate a[n-1], a[n-2] , a[n-3] both calculated, meaning a[n-2] calculated twice. observation important because went down 1 level of recursion. there total of 3^13 member calculations occurring when there should 13 (for 13 members). of time performing same calculations millions of times horrendous waste , makes exponential algorithms awful.

so if stored each of members function calculates? technique called dynamic programming, , answers subproblems stored on way solving larger problem calculations not performed multiple times. solution implementing dynamic programming is:

// variable persists across function calls such instance field int[] array = new int[20];    // giving memory in case want calculate other members array[0] = -1;      //invalid member of sequence since 1-based array[1] = 3; array[2] = 3;  //set rest of numbers values letting know have not been set/found/calculated yet (int = 3; < 20; i++) {     array[i] = -1; }  // index member number; 1 based e.g. index of 1 gives first number in sequence int find(int index) {     if (array[index] != -1)   //if calculated member, return         return array[index];      //store answer     array[index] = (find(index - 1) * find(index - 2)) - find(2);     return array[index]; } 

with code, can call find() number , calculate you, instead of 13th number.

lastly, , importantly, kevin w. pointed out in comment, presence of negative number member means getting numbers big ints. luka milosevic says 13th member number x10^90, big long even. doubles can work long don't need more 20 or digits of precision, because of @ least 90 digits in answer, doubles not accurate enough. fortunately java has class called biginteger, can store large of numbers want, regardless of size. in order obtain answer, have use them, unless want math manually. documentation biginteger here.