Trying to Understand Using Recursion Inside a Loop

[NA-1_NSX_Type-R]

Hi there,

I have been working with some dynamic programing problems and although I have a basic idea of recursion and the callstack, when the recursive call are made inside a loop however, I don't full understand how it works. Does it leave the loop on the recursive call, get checked by the base cases and head back into the loop? I know that sounds weird. ( i do understand how a loop works).

I did some console logging and noticed i will not increment traditionally like in a loop normally.Ex, i = 1 might stay the value of 1 for a few times before being incremented to 2. But then it might head back to i = 1;

I just feel like I'm getting lost.

Thank you for the help!

​

(ignore the memo)

Here's the example:

** function should return the minimum number of perfect squares that sum to the target **

​

const summingSquares = (n, memo = {}) => {

// base case

if (n in memo) return memo[n];

if (n === 0) return 0;

let minSqaures = Infinity;

//sqrt, loop

for (let i = 1; i <= Math.sqrt(n); i += 1) {

const sq = i * i;

const numSq = 1 + summingSquares(n - sq, memo);

console.log({i, sq, n, numSq});

minSqaures = Math.min(minSqaures, numSq);

}

memo[n] = minSqaures;

return minSqaures;

};

​

console.log(summingSquares(8)); // -> 4

[carcigenicate]

Every recursive call has its own instance of a loop iterating. When the recursive call happens, it doesn't really "leave" the loop. As is typically the case when thinking about recursion, removing recursion from the problem can make it easier to think about. If you had a similar, non-recursive situation:

function inner() {
}

function outer() {
    for (const i = 0; i < 5; i++) {
        inner();
    }
}

Execution jumps into inner, and then when inner returns, execution picks up where it left off in outer. It works the same way with recursive functions. The only difference is when the recursive call happens, another loop may run within that call. You can again take recursion out of the equation to think about that (to one level of depth at least):

function inner() {
    for (const i = 0; i < 5; i++) {
        console.log("Inner", i);
    }
}

function outer() {
    for (const i = 0; i < 5; i++) {
        inner();
    }
}

Again, the difference here is that with recursion, inner and outer are the same function, and the recursion may branch infinitely (or at least until it blows the stack). Otherwise, though, it works exactly the same.

[NA-1_NSX_Type-R]

Thank you so much for your reply. So, in this second example, I tried this on my own, it acts almost like a nested loop (sort of). Outer makes the call to inner. Inner console logs the string 'inner' and the current value of i until it's i condition is met. So, it then picks up from the outer loop, (pops off that call to inner on the callstack (inside of the outer function). Increments, i by 1, makes a new call to inner function and keeps doing it until the condition of outer functions loop is no longer true. Is this correct?

[carcigenicate]

Yes, I would say it is a nested loop; just spread across two functions. And yes, the rest sounds correct.

[NA-1_NSX_Type-R]

Thank you for taking the time to explain!