I have been reading multiple articles and as soon as I go to do something recursively I just don't get it, I understand the base case, but I don't get the recursive step. so I have this code which is a solution I found.
function range (start, end) {
if (end < start) return [];
if(start == end) {
return [start];
}
else {
const numbers = range(start , end - 1);
numbers.push(end)
return numbers;
}
}
so, I understand the start == end, here is what I do not get.
why is numbers an array? I don't see anywhere that range is an array, I also don't understand if I use start 1 and push start, the numbers are backward. I have spent 3 weeks so far trying to get a better grasp on recursion and just can not do it, if someone could please help explain to me and maybe offer some resources I have not found? I watched Al Sweigarts recursion video, and thought I understood it until I went to do something, I found it its the recursive step that is just destroying me, I am trying everything I can to understand and get an idea of how this works but I am just super frustrated with myself at this point. thank you for any help.
CodePudding user response：
See comments inline:
function range (start, end) {
console.log("range function is running with arguments of: ", start, end);
// If end < start, exit function and return an empty array
if (end < start) return [];
// If not, check if start and end are equal (with conversion)
if(start == end) {
// If so, return an array that only contains the start parameter value and exit
return [start];
} else {
// If the above tests are false, call the function again
// but with end being one less than before and assign either
// array from above as the value of numbers.
const numbers = range(start , end - 1);
numbers.push(end); // Add end to the end of the array
return numbers; // Return this array instead of the other 2
}
}
console.log("Final array is: ",range(10,20)); // Display the final returned arrayCodePudding user response：
The only possible thing range is returning here is [] which is an array and [start] which is also an array. So when youre calling range recursively from the else block then you'll always end up with an array since there arent any other paths the code can go.
CodePudding user response：
You cannot understand a recursive algorithm ( not your own ) by reading its lines only.. so, you need to apply a simple example to get the right result and understand where it's goes to, this is my example :
First call
start = 1
end = 0
=>start > start
Algorithm result : return []; ===> an empty array
First call
start = 1
end = 1
=> start = end
Algorithm result : return [start]; ===> array of ONE element (start value)
First call
start = 1
end = 5
=> start < end
in this case the algorithm will call itself const numbers = range(start , end - 1); by changing the end value and storing it in array called numbers
Second call :
numbers = []
range(1,5-1)
(don't forget, "end" (4) is still greater than "start" so it will go to the recall iteration )
Third call :
numbers []
range(1,4-1)
=>"end" is still greater (3)
Fourth call :
numbers []
range(1,3-1)
=>"end" is still greater (2)
Fifth call : numbers [] range(1,2-1)
=>now, "end"(1) is equals to "start" (1),the next iteration will act differently
Sixth call : start = end ==> this call will return start value (1) and push it to the constant number
so, now, the algorithm will continue the execution of not executed lines after the previous calls (I mean numbers push() ):
Result of sixth call = 1
it will push it to numbers, and return numbers (array of one element [1])
Result of fifth call = 2
push to numbers ==> numbers is [1,2]
etc. Until it reaches the first call.
Final Result : [1,2,3,4,5]
I hope that it can help.
CodePudding user response：
domain and codomain
A function's inputs are known as its domain and the function's return type is known as its codomain. These types can effectively guide us when writing our implementation -
range : (number, number) -> number array
fill in the blanks
This helpful template can get you started on almost any recursive function. It may seem challenging at first, but things become easier as we fill in the pieces. According to the types for range, we already know 2 and 3 must return some array -
// range : (number, number) -> number array
function range(start, end) {
if (...) // 1
return ... // 2 (must return array)
else
return ... // 3 (must return array)
}
1. base case
Each recursive function needs a base case, which does not result in a recursive call, allowing the function to eventually exit. Under what conditions does the range function exit?
// range : (number, number) -> number array
function range(start, end) {
if (end < start) // 1 ✅ when end subceeds start, exit
return ... // 2
else
return ... // 3
}
2. base value
When the exit condition is met, we need to return the base value. Typically it is the empty value of our function's return type, or codomain. Since we must return an array, what is the empty value for arrays?
// range : (number, number) -> number array
function range(start, end) {
if (end < start) // 1 ✅
return [] // 2 ✅ an empty array is []
else
return ...
}
3. inductive case(s)
We must specify what happens when the exit condition is not met in the else branch, known as the inductive cases. If end < start is not true, by induction we know that end >= start. In this case we solve the problem for the current start and end, and append it to the result of the smaller sub-problem. In other words, if I have range(P,Q) the answer is -
append Q to the result of range(P, Q - 1)
Remember the type for range gives us a hint. When range is called with new arguments, the first and second arguments are both number. The return value will be an array of numbers, or number array.
In JavaScript we write that as -
// range : (number, number) -> number array
function range(start, end) {
if (end < start) // 1 ✅
return [] // 2 ✅
else
return [...range(start, end - 1), end] // 3 ✅ minus and append
}
substitution model
Recursion is a functional heritage and so using it with functional style yields the best results. This means writing functions with referential transparency, meaning there are no observable side-effects and the function will always return the same value when the same inputs are used. Using the substitution model we can substitute any function call for its return value -
range(3,6)
[...range(3, 6 - 1), 6]
[...range(3, 5), 6]
[...[...range(3, 5 - 1), 5], 6]
[...[...range(3, 4), 5], 6]
[...[...[...range(3, 4 - 1), 4], 5], 6]
[...[...[...range(3, 3), 4], 5], 6]
[...[...[...[...range(3, 3 - 1), 3], 4], 5], 6]
[...[...[...[...range(3, 2), 3], 4], 5], 6]
[...[...[...[...[], 3], 4], 5], 6] // base case
[...[...[...[3], 4], 5], 6]
[...[...[3, 4], 5], 6]
[...[3, 4, 5], 6]
[3, 4, 5, 6]
using plus instead of minus
It should be helpful for us to see that we can solve range using and prepend instead of - and append -
// range : (number, number) -> number array
function range(start, end) {
if (start > end) // ✅ when start exceeds end, exit
return []
else
return [start, ...range(start 1, end)] // ✅ plus and prepend
}
range(3,6)
[3, ...range(3 1, 6)]
[3, ...range(4, 6)]
[3, ...[4, ...range(4 1, 6)]]
[3, ...[4, ...range(5, 6)]]
[3, ...[4, ...[5, ...range(5 1, 6)]]]
[3, ...[4, ...[5, ...range(6, 6)]]]
[3, ...[4, ...[5, ...[6, ...range(6 1, 6)]]]]
[3, ...[4, ...[5, ...[6, ...range(7, 6)]]]]
[3, ...[4, ...[5, ...[6, ...[]]]]] // base case
[3, ...[4, ...[5, ...[6]]]]
[3, ...[4, ...[5, 6]]]
[3, ...[4, 5, 6]]
[3, 4, 5, 6]
demo
function rangeplus(start, end) {
if (start > end)
return []
else
return [start, ...rangeplus(start 1, end)]
}
function rangeminus(start, end) {
if (end < start)
return []
else
return [...rangeminus(start, end - 1), end]
}
console.log(rangeplus(3,6))
// [3, 4, 5, 6]
console.log(rangeminus(3,6))
// [3, 4, 5, 6]