previous | start

---

The Efficiency of Recursion

• Can you always speed up a recursive solution by changing it into a loop?
• Frequently, the iterative and recursive solution have essentially the same performance.
• For example:

  bool is_palindrome(string s)
  {
     int start = 0;
     int end = text.length() - 1;
     while (start < end)
     {
        if (s[start] != s[end] return false;
        start++;
        end--;
     }
     return true;
  
  }
  

• The iterative and the recursive solutions to the palindrome problem run at about the same speed.
• There are quite a few problems that are dramatically easier to solve recursively that iteratively.
• Solving the permutation problem iteratively yields code that is complex, but no faster.

---

previous | start