How Recursion Works Inside a For Loop

Question

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).

I understand the concept, but when we're recursing INSIDE THE LOOP, it all blows! Please help me. Thank you.

countTrees() Solution (C/C++)

/*  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 <=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<=numKeys; root++) {         left = countTrees(root - 1);         right = countTrees(numKeys - root);         // number of possible trees with this root == left*right         sum += left*right;     }      return(sum);   }   

Answer 1

Imagine the loop being put "on pause" while you go in to the function call.

Just because the function happens to be a recursive call, it works the same as any function you call within a loop.

The new recursive call starts its for loop and again, pauses while calling the functions again, and so on.

Answer 2

• For recursion, it's helpful to picture the call stack structure in your mind.
• If a recursion sits inside a loop, the structure resembles (almost) a N-ary tree.
• The loop controls horizontally how many branches at generated while the recursion decides the height of the tree.
• The tree is generated along one specific branch until it reaches the leaf (base condition) then expand horizontally to obtain other leaves and return the previous height and repeat.

I find this perspective generally a good way of thinking.