Line length Open
The solution to this problem, and the first trick that you can use to speed up recursive functions, is to use memoization. We already published [a great blog post on memoization](/js/s/memoization/) a little while back, so be sure to check it out to learn more about the subject. Here's our `fibonacciNumber` function, using memoization:- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
To understand recursion better, let's add a `console.log()` call before each `return` and figure out what exactly is happening:- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
excerpt: Recursive code tends to be inefficient or in need of optimization. Learn a couple of tricks we use to speed up our recursive functions.- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
As you can see, for each value of `n`, `fibonacciNumber` will be called twice, once with `n - 1` and once with `n - 2` and this will continue until it's called with either `1` or `0`. While this is straightforward to write and understand, it is inefficient as it will have to calculate the same value more than once.- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
However, you have to bear in mind what the actual use cases of your recursive code are and be very careful how you optimize them. Memoization can be a more powerful tool if a recursive function is called multiple times with different arguments, as its cache persists between calls, while iteration can be faster for recursive computations that are used less frequently. Always pay attention to your code and optimize for the cases you know or anticipate to be more common.- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
First header should be a top level header Open
## Recursive functions- Read upRead up
- Exclude checks
MD002 - First header should be a top level header
Tags: headers
Aliases: first-header-h1
Parameters: level (number; default 1)
This rule is triggered when the first header in the document isn't a h1 header:
## This isn't a H1 header
### Another headerThe first header in the document should be a h1 header:
# Start with a H1 header
## Then use a H2 for subsectionsLine length Open
The second and final trick stems from the very definition of recursive programming turned on its head. If we can solve a smaller instance of the problem and use it for the solution of a larger instance of the problem, it should be possible to work iteratively from the smaller problem to the larger one, instead of recursively. Here's this idea in practice for our `fibonacciNumber` function:- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
As you can see in the example above, the value for each `n` is only computed once. While the Fibonacci sequence doesn't require any costly calculations, this could make a huge difference for a more computationally expensive problem. It will also be a lot more noticeable for higher values of `n` where the number of calculations will increase significantly.- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
The iterative solution above makes the same calculations as the memoized one, however it performs better due to two key reasons. First of all, there is no cache, which would take up space in memory, making the latter implementation require fewer resources. Similarly, as there are no recursive calls or checks for cache hits, the code performs better and requires fewer resources to execute.- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.
Line length Open
Recursion is a programming technique where the final solution is computed by breaking down the problem into smaller instances of the same problem and computing the solution for each one. The most common implementation is a function that calls itself, reducing the problem every time until it reaches an instance of the problem whose solution is either trivial to compute or already known. Let's look at a very well-known example, calculating the `n`th term of the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number), implemented using recursion in JavaScript:- Read upRead up
- Exclude checks
MD013 - Line length
Tags: line_length
Aliases: line-length Parameters: linelength, codeblocks, tables (number; default 80, boolean; default true)
This rule is triggered when there are lines that are longer than the configured line length (default: 80 characters). To fix this, split the line up into multiple lines.
This rule has an exception where there is no whitespace beyond the configured line length. This allows you to still include items such as long URLs without being forced to break them in the middle.
You also have the option to exclude this rule for code blocks and tables. To
do this, set the code_blocks and/or tables parameters to false.
Code blocks are included in this rule by default since it is often a requirement for document readability, and tentatively compatible with code rules. Still, some languages do not lend themselves to short lines.