Is there a name for a deep nested recursive algorithm like this?
Anonymous in /c/coding_help
984
report
I'm writing a recursive algorithm that has a nested recursive call inside a nested recursive call three times like this: `functionCall(functionCall(functionCall(functionCall(a, b), c),d),e)`.<br><br>Is there a term for this usage of recursion? It feels like a "Russian Doll" algorithm, or a "box in a box in a box" algorithm, or like a matryoshka doll.<br><br><br>EDIT: Okay, I didn't expect so many replies, so I'll post the code for those of you who want to see it. This is a function to check if a deep nested object tree can be flattened into a one-to-one mapping, where each path ("location") in the tree corresponds to a specific key in a "flatHash" object. The function will recursively grow both the tree and the hash until it finds something that breaks the one-to-one mapping rule, in which case it returns false (meaning the tree can't be flattened into a 1:1 mapping of locations to keys), or it returns a true if it can (meaning it CAN be flattened).<br><br>```javascript<br>function virtualScrollIsStrictlyOneToOneMapping(tree: VirtualScrollTree, flatHash: VirtualScrollFlatHash): boolean {<br> return functionCall(<br> virtualScrollTreeArrayExpand(tree), <br> functionCall(<br> virtualScrollTreeArrayLocationPaths(tree), <br> functionCall(<br> virtualScrollTreeArrayExpand(tree), <br> virtualScrollFlatHashKeys(flatHash)<br> )<br> )<br> )<br>}<br><br>function functionCall(a: VirtualScrollTreeArrayLocationLeafs, b: VirtualScrollFlatHashKey[]): boolean {<br> const iterations = Math.max(a.length, b.length);<br> let coordinatedIndex = -1;<br><br> for (let i = 0; i < iterations; i++) {<br> const locationLeaf = a[i];<br> const hashKey = b[i];<br> const locationLeafLength = locationLeaf.length;<br> const hashKeyLength = hashKey.length;<br><br> if (locationLeafLength > hashKeyLength) {<br> return false;<br> } else if (locationLeafLength === hashKeyLength) {<br> if (locationLeafEvery(locationLeaf, hashKeyEvery(hashKey))) {<br> coordinatedIndex += 1;<br> } else {<br> return false;<br> }<br> } else { // locationLeafLength < hashKeyLength<br> if (locationLeafEvery(locationLeaf, hashKeyEvery(hashKey))) {<br> return functionCall(<br> locationLeafExpand(locationLeaf),<br> functionCall(<br> a,<br> functionCall(<br> locationLeafExpand(locationLeaf),<br> hashKeyShift(hashKey)<br> )<br> )<br> )<br> } else {<br> return false;<br> }<br> }<br> }<br><br> return true;<br>}<br><br>function locationLeafEvery(locationLeaf: VirtualScrollTreeArrayLocationLeaf, fn: (a: string, i: number) => boolean): boolean {<br> return locationLeaf.every(fn);<br>}<br><br>function hashKeyEvery(hashKey: VirtualScrollFlatHashKey, fn: (a: string, i: number) => boolean): (a: string, i: number) => boolean {<br> return (locationLeafItem, locationLeafItemIdx) => fn(hashKey[locationLeafItemIdx], locationLeafItemIdx);<br>}<br><br>function locationLeafExpand(locationLeaf: VirtualScrollTreeArrayLocationLeaf): VirtualScrollTreeArrayLocationLeaf[] {<br> const locationLeafLength = locationLeaf.length;<br> const expansionIndex = locationLeafLength - 1;<br> const lastLeafItem = locationLeaf[expansionIndex];<br> const lastLeafItemTreeArray = lastLeafItem.virtualScrollTreeArray;<br> const lastLeafItemTreeArrayLength = lastLeafItemTreeArray.length;<br><br> if (lastLeafItemTreeArrayLength <= 0) {<br> throw new Error("Recursive functionCall: locationLeafExpand failed");<br> }<br><br> let expansion = [ ];<br><br> for (let i = 0; i < lastLeafItemTreeArrayLength; i++) {<br> expansion.push([...locationLeaf.slice(0, expansionIndex), lastLeafItemTreeArray[i]])<br> }<br><br> return expansion;<br>}<br><br>function hashKeyShift(hashKey: VirtualScrollFlatHashKey): VirtualScrollFlatHashKey[] {<br> const hashKeyLength = hashKey.length;<br> let expansion = [];<br><br> for (let i = 0; i < hashKeyLength; i++) {<br> expansion.push(hashKey.slice(i));<br> }<br><br> return expansion;<br>}<br>```<br><br>Please note that the type definitions and external functions are not included in the code snippet here.
Comments (18) 35598 👁️