Борьба с рекурсией

Question

Я изо всех сил пытался научиться рекурсии.Это решение для нахождения суммы первых n чисел.Но что, если мы хотим, чтобы наш первый номер был 0?Может кто-нибудь помочь мне написать рекурсивный алгоритм, который суммирует первые n чисел, если первое число начинается с 0?

Таким образом, вместо first_even_numbers_sum (5) будет сумма [2,4,6,8,10].Его [0,2,4,6,8] и решаемо рекурсивно.

def first_even_numbers_sum(n)
  return 2 if n == 1
  n*2 + first_even_numbers_sum(n-1)
end


first_even_numbers_sum(4)

Answer 1

Я бы предложил следующее.

def add_em_up(n)
  return 1 if n == 2
  n - 1 + add_em_up(n - 1)
end

При написании рекурсий, если это часто полезно - даже для опытных Rubiests - добавить несколько puts операторов, чтобы увидеть, что происходит. Давайте сделаем это.

def add_em_up(n)
  puts "entered add_em_up(#{ n })"
  puts "returning 1 when n = #{ 2 }" if n == 2
  return 1 if n == 2
  puts "calling add_em_up(#{ n - 1 }) when n = #{ n }"
  t = n - 1 + add_em_up(n - 1)
  puts "returning #{ n } - 1 + #{t - n + 1} = #{t} when n = #{ n }"
  t
end

add_em_up(5)
  #=> 10   
entered add_em_up(5)
calling add_em_up(4) when n = 5
entered add_em_up(4)
calling add_em_up(3) when n = 4
entered add_em_up(3)
calling add_em_up(2) when n = 3
entered add_em_up(2)
returning 1 when n = 2
returning 3 - 1 + 1 = 3 when n = 3
returning 4 - 1 + 3 = 6 when n = 4
returning 5 - 1 + 6 = 10 when n = 5

Вы можете использовать отступы, чтобы сделать вещи еще яснее.

INDENT = 3
$col = 0

def add_em_up(n)
  s = " " * $col
  puts "#{ s }entered add_em_up(#{ n })"
  puts "#{ s }returning 1 when n = #{ 2 }" if n == 2
  $col -= INDENT if n == 2
  return 1 if n == 2
  puts "#{ s }calling add_em_up(#{ n - 1 }) when n = #{ n }"
  $col += INDENT
  t = n - 1 + add_em_up(n - 1)
  puts "#{ s }returning #{ n } - 1 + #{t - n + 1} = #{t} when n = #{ n }"
  $col -= INDENT
  t
end

add_em_up(5)
  #=> 10   
entered add_em_up(5)
calling add_em_up(4) when n = 5
   entered add_em_up(4)
   calling add_em_up(3) when n = 4
      entered add_em_up(3)
      calling add_em_up(2) when n = 3
         entered add_em_up(2)
         returning 1 when n = 2
      returning 3 - 1 + 1 = 3 when n = 3
   returning 4 - 1 + 3 = 6 when n = 4
returning 5 - 1 + 6 = 10 when n = 5

Обратите внимание, что в первой версии этого метода (без отступа) можно заменить

t = n - 1 + add_em_up(n - 1)
puts "returning #{ n } - 1 + #{t - n + 1} = #{t} when n = #{ n }"
t

с

(n - 1 + add_em_up(n - 1)).
  tap { |t| puts "returning #{ n } - 1 + #{t - n + 1} = #{t} when n = #{ n }" }

или (как указано в комментарии)

(n - 1 + add_em_up(n - 1)).yield_self { |t| 
  puts "returning #{ n } - 1 + #{t - n + 1} = #{t} when n = #{ n }"; t }

Здесь и в более общем смысле метод Object # tap очень полезен для отладки. Object # yield_self (новинка в Ruby v2.5) - еще один полезный метод.