title: Dissecting a permutation algorithm in swift
body: <p>I was looking for a string permutation algorithm and I found this one. </p>
  
  <pre><code>    import Foundation
  
      func permuteHelper(_ str:String, _ chosen:String){
          var chosen = chosen
          var str = str
          if str.count == 0 {
              print(chosen)
          } else {
              for index in str.indices {
                  //choose
                  let charac = str[index]
                  chosen.append(charac)
                  str.remove(at: index)
                  // explore
                  print("call recursion")
                  permuteHelper(str, chosen)
                  print("return from recursion")
                  //unchoose
                  str.insert(charac, at: index)
                  chosen.removeLast()
              }
          }
      }
  
      func permute(_ str:String){
          permuteHelper(str, "")
      }
  
      var str = "ABC"
      permute(str)
  </code></pre>
  
  <p>I run it and then it prints the execution:</p>
  
  <pre><code>call recursion
  call recursion
  call recursion
  ABC
  return from recursion
  return from recursion
  call recursion
  call recursion
  ACB
  return from recursion
  return from recursion
  return from recursion
  call recursion
  call recursion
  call recursion
  BAC
  return from recursion
  return from recursion
  call recursion
  call recursion
  BCA
  return from recursion
  return from recursion
  return from recursion
  call recursion
  call recursion
  call recursion
  CAB
  return from recursion
  return from recursion
  call recursion
  call recursion
  CBA
  return from recursion
  return from recursion
  return from recursion
  Program ended with exit code: 0
  </code></pre>
  
  <p>In the first 8 lines it has the <em>first cycle</em> with the result: <code>ABC</code>. It looks stranger to me that it make <code>3</code> <code>call recursion</code>, shows the result and then complete <code>2</code> <code>return from recursion</code> and starts a new cycle.</p>
  
  <p><strong>My question is:</strong></p>
  
  <p>It is not suppose to came back to <em>third</em> <code>return from recursion</code> before starts a new cycle?</p>
  
  <p><strong>==>> UPDATE</strong></p>
  
  <p>After add a level parameter in permuteHelper <code>func permuteHelper(_ str:String, _ chosen:String, _ level:Int)</code> as Martin R suggested. It looks like the algorithm complete a cycle after print two permutations. As follow:</p>
  
  <pre><code>call recursion Level: 1
  call recursion Level: 2
  call recursion Level: 3
  ABC
  return from recursion Level: 3
  return from recursion Level: 2
  call recursion Level: 2
  call recursion Level: 3
  ACB
  return from recursion Level: 3
  return from recursion Level: 2
  return from recursion Level: 1
  call recursion Level: 1
  call recursion Level: 2
  call recursion Level: 3
  BAC
  return from recursion Level: 3
  return from recursion Level: 2
  call recursion Level: 2
  call recursion Level: 3
  BCA
  return from recursion Level: 3
  return from recursion Level: 2
  return from recursion Level: 1
  call recursion Level: 1
  call recursion Level: 2
  call recursion Level: 3
  CAB
  return from recursion Level: 3
  return from recursion Level: 2
  call recursion Level: 2
  call recursion Level: 3
  CBA
  return from recursion Level: 3
  return from recursion Level: 2
  return from recursion Level: 1
  Program ended with exit code: 0
  </code></pre>