# Confused about why the recursive version is so much more complicated than the iterative with a memo

• The iterative version with a memo:

``````def num_decodings(s)
return 0 if s.length == 0
n = s.length
memo = Array.new(n+1,0)
memo[n] = 1
memo[n-1] = s[n-1]=="0" ? 0 : 1
(0...n-1).to_a.reverse.each do |i|
next if s[i] == "0"
memo[i] = s[i...(i+2)].to_i <= 26 ? memo[i+1] + memo[i+2] : memo[i+1]
end
return memo[0]
end
``````

The recursive version: As you can see the base case is incredibly complicated.

``````def num_decodings(s)
#puts "s: #{s}"
return 0 if s.length == 0
return 0 if s[0] == "0"
return 1 if s.length == 1
return 1 if s.length == 2 && s[1] == "0" && s.to_i <= 26
return 0 if s.length == 2 && s[1] == "0" && s.to_i > 26
return 2 if s.length == 2 && s.to_i <= 26
return 1 if s.length == 2
@ways ||= {}
return @ways[s] if @ways[s]
if s[0..1] == "10"
@ways[s] = num_decodings(s[2..-1])
elsif s[0..1].to_i <= 26
@ways[s] = num_decodings(s[1..-1]) + num_decodings(s[2..-1])
else
@ways[s] = num_decodings(s[1..-1])
end
#puts @ways
return @ways[s]
end
``````

Can someone help me understand why the recursive solution has such a complicated base case when the memoized version is much cleaner?

I'm assuming it's because my recursive base cases are not simplified enough but maybe there's another reason.

• I think you have a little too much logic going on. This could be shortened a bit more I'm sure.

``````public int help(String s, int inc) {
if (s.length() == 0) return inc;
else if (s.charAt(0) == '0') return 0;
else if (s.length() >= 2 && (s.charAt(0) == '1' || s.charAt(0) == '2' && s.charAt(1) <= '6')) return help(s.substring(1), 1) + help(s.substring(2), 1);
return help(s.substring(1), 1);
}
``````
``}``

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.