title: How Recursion Works Inside a For Loop
body: <p>I am new to recursion and trying to understand this code snippet. I'm studying for an exam, and this is a "reviewer" I found from Standford' CIS Education Library (From Binary Trees by Nick Parlante).</p>
  
  <p>I understand the concept, but when we're recursing INSIDE THE LOOP, it all blows! Please help me. Thank you.  </p>
  
  <p>countTrees() Solution (C/C++)</p>
  
  <pre><code>/*
   For the key values 1...numKeys, how many structurally unique
   binary search trees are possible that store those keys.
   Strategy: consider that each value could be the root.
   Recursively find the size of the left and right subtrees.
  */
  
  int countTrees(int numKeys) {
      if (numKeys &lt;=1) {
          return(1);
      }
  
      // there will be one value at the root, with whatever remains
      // on the left and right each forming their own subtrees.
      // Iterate through all the values that could be the root...
  
      int sum = 0;
      int left, right, root;
  
      for (root=1; root&lt;=numKeys; root++) {
          left = countTrees(root - 1);
          right = countTrees(numKeys - root);
          // number of possible trees with this root == left*right
          sum += left*right;
      }
  
      return(sum);  
  }  
  </code></pre>