title: How to understand the relationship between tail recursion and for loop in DFS
body: <p>I'm trying to implement the "subset" algorithm using DFS. And I found both the following two programs work:</p>
  
  <pre><code>def DFS(nums, begin, path, res):
      res.append(path[:])
  
      for i in range(begin, len(nums)):
          path.append(nums[i])
          DFS(nums, i + 1, path, res)
          path.pop()
  
  
  def DFS_2(nums, begin, path, res):
      if begin == len(nums):
          res.append(path[:])
          return
  
      path.append(nums[begin])
      DFS_2(nums, begin + 1, path, res) #choose the current element
      path.pop()
      DFS_2(nums, begin + 1, path, res) #not choose the current element
  </code></pre>
  
  <p>test code is:</p>
  
  <pre><code>nums = [i for i in range(1, 4)]
  res = []
  path = []
  
  DFS_2(nums, 0, path, res)
  print(res)
  
  res2 = []
  DFS(nums, 0, path, res2)
  print(res2)
  </code></pre>
  
  <p>Output is:</p>
  
  <p>DFS_2:  <code>[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]</code></p>
  
  <p>DFS:    <code>[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]</code></p>
  
  <p>I can understand <code>DFS_2</code>, since in each recursion, I have two choices - choose the current element or not choose the current element. But I'm having difficulty understanding function <code>DFS</code>. How to understand the <code>for</code> loop in that function <code>DFS</code>? My guess is that there is tail recursion in function <code>DFS_2</code>, which is the reason why function <code>DFS</code> and <code>DFS_2</code> are equivalent to each other, but I'm not sure about the details.</p>
  
  <p>Any hints are appreciated.</p>