/* Author: LukArToDo Created: 31.jan 2020 Edit: 06.feb 2020 -> added Hofstadter-Conway Sequence Description: solution of the task -> https://www.sololearn.com/post/230643/?ref=app */ import java.util.*; import java.util.function.*; public class RecursionVersusLoop { static HashMap map; static Function recursive; static Consumer loop; static BiFunction recursiveA; static BiConsumer loopA; public static void main(String[] args) { Ackermann(2L,1L); HofstadterConway(10); Factorial(10); Fibonnaci(10); Hofstadters(10); Prime(10); Recamans(10); } static void display(String label, String format1, String format2, boolean cardinal) { System.out.println(label); map.forEach((k,v) -> System.out.printf(format2, cardinal?String.format(format1, k)+(k==1?"st:":k==2?"nd:":k==3?"rd:":"th:") : String.format(format1, k), v[0], v[1])); System.out.println(); } static void Ackermann(long m, long n) { HashMap, long[]> mapA= new HashMap, long[]>(); recursiveA = (x,y)->{ long acker; if (x == 0) acker= y+1; else if (y == 0) acker=recursiveA.apply(x-1,1L); else acker= recursiveA.apply(x - 1, recursiveA.apply(x, y - 1)); mapA.put(Arrays.asList(x,y), new long[] {acker}); return acker; }; loopA = (x,y) ->{ Stack> stack= new Stack>(); stack.push(Arrays.asList(x,y)); while (!stack.isEmpty()) { List head= stack.peek(); if (head.get(0)==0 ) { mapA.put(head,new long[] {mapA.get(head)[0],head.get(1) + 1}); stack.pop(); } else if (head.get(1)==0) { List next= Arrays.asList(head.get(0)-1,1L); if(mapA.containsKey(next)&&mapA.get(next).length ==2){ mapA.put(head, new long[] {mapA.get(head)[0],mapA.get(next)[1]}); stack.pop(); } else stack.push(next); } else { List next= Arrays.asList(head.get(0), head.get(1)-1); if(mapA.containsKey(next)&&mapA.get(next).length ==2) { List next1= Arrays.asList(head.get(0)-1, mapA.get(next)[1]); if(mapA.containsKey(next1)&&mapA.get(next1).length ==2) { mapA.put(head,new long[] {mapA.get(head)[0],mapA.get(next1)[1]}); stack.pop(); } else stack.push(next1); } else stack.push(next); } } }; recursiveA.apply(m,n); loopA.accept(m,n); System.out.println("Ackermann Algorithm:"); mapA.forEach((k,v)-> System.out.printf("%8s%6d%6d\n", String.format("A%s",k),v[0],v[1])); System.out.println(); } static void HofstadterConway (long n){ map= new HashMap(); recursive = x -> { if(map.containsKey(x)) return map.get(x)[0]; if(x<=2) { map.put(x, new long[] {1L}); return map.get(x)[0]; } map.put(x, new long[] {recursive.apply(recursive.apply(x-1)) + recursive.apply(x - recursive.apply(x-1))}); return map.get(x)[0]; }; loop = x ->{ for(long i =1; i<=x; i++) { map.put(i, new long[] {map.get(i)[0], i<=2 ? 1L : map.get(map.get(i-1)[1])[1] + map.get(i- map.get(i-1)[1])[1]}); } }; recursive.apply(n); loop.accept(n); display("Hofstadter-Conway Sequence:","HC(%d)","%6s%6d%6d\n", false ); } static void Factorial (long n){ map= new HashMap(); recursive = x -> { if(x==0) { map.put(x, new long[] {1L}); return map.get(x)[0]; } map.put(x, new long[] {x* recursive.apply(x-1)}); return map.get(x)[0]; }; loop = x ->{ long i, result=1; for(i =0; i<=x; i++) { result*= i==0 ? 1: i; map.put(i, new long[] {map.get(i)[0], result}); } }; recursive.apply(n); loop.accept(n); display("Factorial Algorithm:","F(%d)", "%6s%"+(n+2)+"d%"+(n+2)+"d\n", false ); } static void Fibonnaci (long n){ map= new HashMap(); recursive = x -> { if(map.containsKey(x)) return map.get(x)[0]; if(x<=1) { map.put(x, new long[] {x}); return map.get(x)[0]; } map.put(x, new long[] {recursive.apply(x-2)+ recursive.apply(x-1)}); return map.get(x)[0]; }; loop = x ->{ for(long i =0; i<=x; i++) { map.put(i, new long[] {map.get(i)[0], i<=1 ? i : map.get(i-2)[1] + map.get(i-1)[1]}); } }; recursive.apply(n); loop.accept(n); display("Fibonnaci Numbers:","F(%d)","%6s%6d%6d\n", false ); } static void Hofstadters (long n){ map= new HashMap(); recursive = x -> { if(map.containsKey(x)) return map.get(x)[0]; if(x<=2) { map.put(x, new long[] {1}); return map.get(x)[0]; } map.put(x, new long[] {recursive.apply(x-recursive.apply(x-1)) + recursive.apply(x-recursive.apply(x-2))}); return map.get(x)[0]; }; loop = x ->{ for(long i =1; i<=x; i++) { map.put(i, new long[] {map.get(i)[0], i<=2 ? 1 : map.get(i-map.get(i-1)[1])[1] + map.get(i-map.get(i-2)[1])[1]}); } }; recursive.apply(n); loop.accept(n); display("Hofstadter's Q-Sequence:","Q(%d)","%6s%6d%6d\n", false ); } static void Prime (long n){ map= new HashMap(); recursive = x -> { if(x==1) { map.put(x,new long[]{2L,0}); return map.get(x)[0]; } long lastPrime = recursive.apply(x-1); boolean flag=false; while(!flag){ lastPrime+= lastPrime==2 ? 1 : 2; flag=true; for(long[] l : map.values()){ if(lastPrime%l[0]==0){ flag=false; break; } } } map.put(x, new long[] {lastPrime,0}); return map.get(x)[0]; }; loop = x ->{ long num=2, j, count=1; boolean isPrime; while(count<=x) { isPrime=true; for(j=2;j<=(int)Math.sqrt(num); j+= j==2?1:2){ if(num%j==0) { isPrime = false; break; } } if(isPrime) { map.put(count, new long[] {map.get(count)[0],num}); count++; } num += num==2 ? 1 : 2; } }; recursive.apply(n); loop.accept(n); display("Prime Numbers:","%d","%6s%6d%6d\n",true ); } static void Recamans (long n){ map= new HashMap(); recursive = x -> { if(x==0) { map.put(x, new long[] {x}); return map.get(x)[0]; } final long recam=recursive.apply(x-1)-x; map.put(x, new long[] {recam<0 || map.values().stream().anyMatch(v-> v[0]==recam)? recam+ x*2:recam}); return map.get(x)[0]; }; loop = x ->{ HashSet set = new HashSet(); long prev = 0, curr, i; for (i = 0; i<= x; i++){ curr = prev - i; if (curr < 0 || set.contains(curr)) curr = prev + i; set.add(curr); map.put(i, new long[] {map.get(i)[0], curr}); prev = curr; } }; recursive.apply(n); loop.accept(n); display("Recaman's Sequence:","R(%d)","%6s%6d%6d\n", false ); } }

Recursion vs Loop