Pranav Kasetti
Software Developer
Recursive Algorithms vs Dynamic Programming
Context: Why do we typically convert Recursive algorithms to DP?
Unoptimised Recursive Algorithms can repeat calculations on the same data. We can easily get an exponentially growing number of recursive computations as the input size grows, which we optimise with DP.
The idea behind Dynamic Programming is to increase the efficiency of fundamentally recursive problems through caching of data. Dynamic Programming flips the problem from a top-down recursive solution to a bottom-up solution using tabulation. We avoid repeating expensive calculations and can sometimes also improve space efficiency without a recursive call stack.
We can implement top-down DP through a different caching technique called memoization, but we sacrifice space efficiency because we still have a recursive solution. I focus on tabulation here for optimal space efficiency.
Why make this post?
There are many posts out there for how DP improves exponential Recursive algorithms to linear complexity. I focus in this post on a rare case where a recursive solution is more efficient than DP.
Example Problem Statement
Given a string s, return the longest palindromic substring in s.
/* Example Functionality:
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "ac" Output: "a"
*/
Suboptimal DP Solution Idea
Given a string, represented as var input: [Character], build a var table of size input.count by input.count, so that table[i][j] == 1 if the substring starting from input[i] of length j + 1 is a palindrome, and table[i][j] == 0 if the substring is not a palindrome.
To calculate table[i][j], check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true.
Build the table bottom up with a palindrome detector that detects all the lower length palindromes first. Use the table to build the higher length palindrome. Cache the longest palindrome found so far during this enumeration.
Return the longest length palindrome after iterating through all substrings.
Suboptimal Dynamic Programming Solution
func longestPalindromeDP(_ st: String) -> String {
let n = st.count
var st = Array(st)
// Palindrome table initialised to no palindromes.
var table: [[Bool]] = Array(repeating: Array(repeating: false, count: st.count), count: st.count)
// All single character strings are valid palindromes.
var maxLength = 1
var i = 0
while (i < n) {
table[i][i] = true
i += 1
}
// check for sub-string of length 2.
var start = 0
i = 0
while i < n - 1 {
if (st[i] == st[i + 1]) {
table[i][i + 1] = true
start = i
maxLength = 2
}
i = i + 1
}
// Check for lengths greater than 2.
// k is length of substring
var k = 3
while k <= n {
// Fix the starting index
i = 0
while i < (n - k + 1) {
// Get the ending index of
// substring from starting
// index i and length k
let j = i + k - 1
// checking for sub-string from
// ith index to jth index iff
// st[i + 1] to st[(j-1)] is a
// palindrome
if table[i + 1][j - 1], st[i] == st[j] {
table[i][j] = true
if (k > maxLength) {
start = i
maxLength = k
}
}
i = i + 1
}
k = k + 1
}
return String(Array(st[start ..< (start + maxLength)]))
}
NOTE: This solution is adapted into Swift from GeeksForGeeks.
Complexity
Time: O(n^2)
Space: O(n^2)
We use O(n^2) space complexity to cache the results in a table.
Note that n^2 time complexity is more optimal than the n^3 Brute Force solution. However, the space complexity is still suboptimal.
Recursive Solution Idea
Build palindromes from the innermost characters outwards for each possible midpoint. Consider palindromes with an even and with an odd number of characters separately.
Using this traversal technique, we don't need to cache data because we don't repeat calculations and we only need to track the longest palindrome found thus far.
Recursive Solution
func helper(_ input: inout [Character], _ idx: Int, _ result: inout String) {
// Edge case
if input.isEmpty {
return
}
// Terminate recursion
if idx == input.count {
return
}
// Build palindromes
var left = idx
var right = idx + 1
var palindrome = String(input[idx])
while left >= 0, right < input.count {
if input[left] == input[right] {
palindrome = String(input[left...right])
} else {
break
}
left -= 1
right += 1
}
left = idx - 1
right = idx + 1
var palindromeTwo = String(input[idx])
while left >= 0, right < input.count {
if input[left] == input[right] {
palindromeTwo = String(input[left...right])
} else {
break
}
left -= 1
right += 1
}
if palindromeTwo.count > palindrome.count {
palindrome = palindromeTwo
}
if palindrome.count > result.count {
result = palindrome
}
}
func longestPalindrome(_ input: String) -> String {
var result: String = ""
var input = Array(input)
for i in 0 ..< input.count {
helper(&input, i, &result)
}
return result
}
NOTE: I independently developed this algorithm without referencing GeeksForGeeks.
Complexity
Time: O(n^2)
Space: O(1)
We only use O(1) space complexity because the method call stack gets reset to size 0 when invoking every additional helper(..) call.
Summary
Dynamic Programming is a powerful technique to optimise combinatorial enumeration time complexity for many problems, but may not always produce the most optimal solution.
In this post, I outline a recursive solution that didn't require caching and thus improved the space complexity of the DP solution. This is counterintuitive because the traditional recursion solution is optimised with DP.
So we can see that coming up with the right overall solution strategy can optimize the efficiency of DP solutions. Don't always assume DP is the best solution.