# # @ Javier Felipe Toribio 2020-01-29 # # challenge by John Wells # # Recursion Versus Loop # # Pick one or more of the following choices and # solve with both recursion & loop. Choices are: # Ackermann Algorithm, Factorial Algorithm, # Fibonacci Numbers, Hofstadter's Q-Sequence, # Prime Number List, Recamán's Sequence, plus # any suggestions you or others can think of. # # Display ten values of each side by side. # If you hit SoloLearn's timeout, you can solve # less values or randomly pick the set of # algorithms to perform. # But, you must test to be sure what you picked # will complete. # # Output should be formatted into columns for # each choice. Strings for the call or cardinal # count should be right justified in their # column. Integers for results should be right # justified in their columns. # # Note: picture got truncated. See my code for # complete output. # https://code.sololearn.com/c6r7equ7Gbr1 # # Mihai Apostol added Hofstadter-Conway so I did # also. # ########################################## # Class to display two columns with the # recursive and iterative results ########################################## class Visualizer WIDTH = 34 W=WIDTH/2 attr_accessor :image # Constructor # Name of function, prefix letter, # recursive list and iterative list # special indexes in idxs (if any) def initialize(title,sign,list1,list2,idxs=[]) w = idxs.empty? ? W : W - 1 max = [list1.size,list2.size].min if sign.nil? num = ["1st".rjust(5),*(2..max).map{|i|"#{i.to_s.rjust(3)}th"}] else num = (1..max).map {|i| "#{sign}(#{idxs.empty? ? i.to_s.rjust(2) : idxs[i-1]})"} end header = title + "Recursive".rjust(6+W-title.size) + "Iterative".rjust(W) img = (0..max-1).inject(header) do |img,i| img + "\n" + num[i] + " " + "#{list1[i].to_s.rjust(w) + list2[i].to_s.rjust(w)} " end @image = img end end ########################################## # Factorial ########################################## # Recursive def fac(n,res=1) n <= 1 ? res : fac(n-1,n*res) end # Iterative def fac_iter(n) (res = (1..n).inject(&:*)).nil? ? 1 : res end ########################################## # Fibonacci ########################################## # Recursive def fib(n,i=2,e=[0,1]) i>n ? e[n] : fib(n,i+1,e< 0 and n = 0 # A(m-1,A(m,n-1)) if m > 0 and n > 0 # ######################################### class Ackerman < Memo # Recursive function def A(m,n) m==0 ? n+1 : m>0 && n==0 ? a(m-1,1) : a(m-1,a(m,n-1)) end # Iterative function def A_iterative(m,n) s = [m] until s.empty? m = s.pop if m == 0 n += 1 elsif n == 0 s.push(m-1) n = 1 else s.push(m-1) s.push(m) n -= 1 end end n end # Constructor def initialize super(Proc.new {|arg1,arg2| A(arg1,arg2)}) alias :a :mf2 end end ########################################## # Hofstadter's Q-Sequence # # Q1 = Q2 = 1 # # Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)) # ########################################## class Hofstadter_Q_Sequence < Memo # Recursive function def Q(n) n==1 || n==2 ? 1 : q(n-q(n-1))+q(n-q(n-2)) end # Iterative function def Q_iteractive(n) s = [0,1,1] (3..n).each do |i| s[i] = s[i-s[i-1]] + s[i-s[i-2]] end s[n] end # Constructor def initialize super(Proc.new {|arg| Q(arg)}) alias :q :mf end end ########################################## # Recaman's Sequence # # 0 if n = 0 # # a(n-1) - n if a(n-1) - n > 0 and is # not already in the sequence # # a(n-1) + n otherwise # ########################################## class Recamans_Sequence < Memo # Recursive function def R(n) n==0 ? 0 : r(n-1)-n > 0 && !@memo.values().include?(r(n-1)-n) ? r(n-1)-n : r(n-1)+n end # Iterative function def R_iterative(num) # value for n=0 val = 0 seq = [] (1..num).each do |n| if val-n > 0 && ! seq.include?(val-n) val -= n else val += n end seq << val end val end # Constructor def initialize super(Proc.new {|arg| R(arg)}) alias :r :mf end end ########################################## # Hofstadter-Conway Sequence # # 1 if n=1 or n=2 # a(a(n-1)) + a(n-a(n-1)) otherwise # ########################################## class Hofstadter_Conway < Memo # Recursive function def A(n) n==1 || n==2 ? 1 : a(a(n-1))+a(n-a(n-1)) end # Iterative function def A_iteractive(n) s = [0,1,1] (3..n).each do |i| s[i] = s[s[i-1]] + s[i-s[i-1]] end s[n] end # Constructor def initialize super(Proc.new {|arg| A(arg)}) alias :a :mf end end ########################################## # Prime # Show prime number 'pos' ########################################## # Recursive function def prime(pos,n=2,p=2) if pos > 0 is = [2,3,5].include?(n) || (n>3 && n%2!=0 && n%3!=0 && ! 5.step(Math.sqrt(n),6). any?{|i| n%i==0 || n%(i+2)==0}) return prime(is ? pos-=1 : pos, n+1, is ? n : p) end p end # Iterative function def prime_iterative(pos) c = pos n = 2 p = 2 loop do is = [2,3,5].include?(n) || (n>3 && n%2!=0 && n%3!=0 && ! 5.step(Math.sqrt(n),6). any?{|i| n%i==0 || n%(i+2)==0}) break if c <= 0 if is c -= 1 p = n end n += 1 end p end ######################################### # TESTS ######################################### # Show recursive and iterative calculations def show(title,letter,rec_fun,iter_fun,min,max) lr=[] li=[] (min..max).each do |i| lr << rec_fun.call(i) li << iter_fun.call(i) end v = Visualizer.new(title,letter,lr,li) puts v.image puts end # Show recursive and iterative calculations # with two arguments def show_2_ranges(title,letter, rec_fun,iter_fun, min1,max1,min2,max2) lr=[] li=[] idxs=[] (min1..max1).each do |i| (min2..max2).each do |j| lr << rec_fun.call(i,j) li << iter_fun.call(i,j) idxs << "#{i},#{j}" end end v = Visualizer.new(title,letter,lr,li,idxs) puts v.image puts end ######################################### # MAIN PROGRAM ######################################### ack = Ackerman.new hofs = Hofstadter_Q_Sequence.new rec = Recamans_Sequence.new hofcon = Hofstadter_Conway.new show_2_ranges("Ackermann","A", ack.method( :A),ack.method( :A_iterative), 0,3,0,3) show("Factorial","F", method( :fac),method( :fac_iter), 1,10) show("Fibonacci","F", method( :fib),method( :fib_iter), 0,9) show("Hofstadter-Q","Q", hofs.method(:Q),hofs.method(:Q_iteractive), 1,10) show("Prime",nil, method( :prime),method( :prime_iterative), 1,10) show("Recaman","R", rec.method( :R),rec.method( :R_iterative), 1,10) show("Hofstadter-C","a", hofcon.method(:A),hofcon.method(:A_iteractive), 1,10)

[challenge] recursive vs iterative