I am trying to wrap my head around recursive functions. I've tried a number of entry level exercises with no success. For example, I put this code into JS fiddle. I intended for it to take the sum of all numbers from 1 to n.
function sumAll(n) {
if (n == 1 ) {
return 1;
} else if (n > 1) {
return sumAll(n--) + n;
}
}
console.log(sumAll(3));
feeding 3 to the function should give me '6'. I get an error, though.
The -- suffix operator will evaluate to the original value of n, and the subtraction from n will happen afterwards (which is also not desired as you still want to do + n). That means the recursive call gets the same value for n as the caller, and so you don't get closer to the end...
Don't use -- here, but -1:
function sumAll(n) {
if (n == 1 ) {
return 1;
}
else if (n > 1) {
return sumAll(n-1) + n;
}
}
console.log(sumAll(3));
sumAll(0) or sumAll(-1) and have the function return undefined instead, which I actually think is a good idea. Even better would be to have a base case that catches all possible states where no recursion should happen, like (!(n > 1)). But all this distracts from the original question.Perhaps you will enjoy a repeatable technique that can guide you through designing your recursive function. Let's solve sumAll using inductive reasoning -
If n is zero, return the empty sum, zero
(inductive) n is negative or positive. If n is negative, return the negative result of the subproblem sumAll(-n)
(inductive) n is positive. Return n plus the result of the subproblem sumAll(n - 1)
function sumAll(n) {
if (n == 0) // 1
return 0
else if (n < 0) // 2
return -sumAll(-n)
else
return n + sumAll(n - 1) // 3
}
console.log(sumAll(-10), sumAll(0), sumAll(10))
// -55 0 55Here is sumAll written using a switch instead. It behaves identically but maybe you will find the syntax nicer to read -
function sumAll(n) {
switch (true) {
case n == 0: return 0 // 1
case n < 0: return -1 * sumAll(-n) // 2
default: return n + sumAll(n - 1) // 3
}
}
console.log(sumAll(-10), sumAll(0), sumAll(10))
// -55 0 55Here is sumAll again as a pure, functional expression -
const sumAll = (n = 0) =>
n == 0 // 1
? 0
: n < 0 // 2
? -1 * sumAll(-n)
: n + sumAll(n - 1) // 3
console.log(sumAll(-10), sumAll(0), sumAll(10))
// -55 0 55
n--does? How does that differ from--n, and why is it relevant?n - 1is much clearer--zero cognitive overhead and anyone reading the code will understand exactly what's happening.