資訊專欄INFORMATION COLUMN
Recursion, simply put, is calling a function on itself. It can used to break down complex problems into smaller manageable similar units that can be handled by the same function.
Recursion vs IterationAn iterative function is one that loops to repeat some part of the code, and a recursive function is one that calls itself again to repeat the code.
E.g To calculate the sum of an array of numbers
function iterativeSum(arr) {
let sum = 0;
for (let i of arr) {
sum += i;
}
return sum;
}
function recursiveSum(arr) {
if (arr.length === 0) {
return 0;
}
return arr[0] + recursiveSum(arr.slice(1));
}
/**
*
* iterativeSum([1,2,3]) => 1 + 2 + 3 => 6
*
* recursiveSum([1,2,3])
* => 1 + recursiveSum([2,3])
* => 2 + recursiveSum([3])
* => 3 + recursiveSum([])
* => 0
* => 0 + 3 + 2 + 1 => 6
*/
console.log(iterativeSum([1,2,3])); //6
console.log(recursiveSum([1,2,3])); //6
How to use recursion
base condition is a must
Using recursion without a base condition leads to infinite recursion. As recursion is calling the function on itself, base condition indicates when to terminate the process.
function infiniteRecursion() {
// keeps calling itself without termination
return infiniteRecursion();
}
break down the problem into smaller units that can be handled by the function itself.
E.g.
the sum of an array = the value of first element + the sum of the rest of array.
That"s how we do it recursively in recursiveSum example above.
Practices make perfect Q1 Question:By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. Write a function that, given a number, tries to find a sequence of such additions and multiplications that produce that number.
Thoughts:To find a solution for a number(let"s call it A), we tries adding 5 or multiplying 3 to the current number(let"s call it B) and use recursion to
check if there is a solution for the result(i.e. B + 5 or B * 3). The base condition is when the current number is greater than(boom!) or equal to(solution found!) A.
function findSolution(num) {
function find(start, history) {
if(start > num) {
return null; // boom!
} else if (start === num) {
return history; //solution found
}
return find(start + 5, `(${history} + 5)`) || find(start * 3, `(${history} * 3)`);
}
return find(1, "1");
}
console.log(findSolution(13)); //(((1 * 3) + 5) + 5)
console.log(findSolution(20)); //null
Q2
Question: Inorder(Left, Right, Top) traversal of binary tree
Solution
class Node {
constructor(value, left=null, right=null) {
this.value = value;
this.left = left;
this.right = right;
}
}
function inorder(node, fn) {
if(node == null) {
return;
}
inorder(node.left, fn);
fn(node);
inorder(node.right, fn);
}
function test() {
/**
* A
* /
* B C
* /
* E F H
*/
let E = new Node("E"),
F = new Node("F"),
H = new Node("H"),
B = new Node("B", E, F),
C = new Node("C", null, H),
A = new Node("A", B, C);
inorder(A, node => console.log(node.value)); // E B F A C H
}
test();
Reference
Eloquent JavaScript
NoticeIf you want to follow the latest news/articles for the series of reading notes, Please 「Watch」to Subscribe.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/93678.html
這兩天搜了下JS遞歸的相關(guān)文章， 覺(jué)得這篇文章很不錯(cuò)， 就順手翻譯了下，也算給自己做個(gè)筆記，題目是我自己加的。原文很長(zhǎng)，寫得也很詳盡，這里并非逐字翻譯， 而是作者所講的主要概念加上我自己的一些理解，本文中解決方案的實(shí)際意義并不是特別大，但算法的邏輯挺有意思，不過(guò)也略抽象，理解需要花點(diǎn)時(shí)間（囧，估計(jì)我太閑了） 文中的用例?全部來(lái)自原文： 原文鏈接：（原題為：理解JS函數(shù)式編程中的遞歸）Underst...
摘要：尾遞歸優(yōu)化一般遞歸與尾遞歸一般遞歸執(zhí)行可以看到一般遞歸每一級(jí)遞歸都產(chǎn)生了新的局部變量必須創(chuàng)建新的調(diào)用棧隨著遞歸深度的增加創(chuàng)建的棧越來(lái)越多造成爆棧尾遞歸尾遞歸基于函數(shù)的尾調(diào)用每一級(jí)調(diào)用直接返回遞歸函數(shù)更新調(diào)用棧沒(méi)有新局部變量的產(chǎn)生類似迭代的 Python尾遞歸優(yōu)化 一般遞歸與尾遞歸 一般遞歸: def normal_recursion(n): if n == 1: ...
摘要：只有當(dāng)位數(shù)時(shí)，才打印數(shù)字。首先分析邊界，應(yīng)該，然后用存最高位。用函數(shù)對(duì)進(jìn)行遞歸運(yùn)算，同時(shí)更新結(jié)果數(shù)組。更新的過(guò)程歸納一下，首先，計(jì)算最高位存入，然后，用到倍的和之前里已經(jīng)存入的所有的數(shù)個(gè)循環(huán)相加，再存入，更新，計(jì)算更高位直到等于 Problem Print numbers from 1 to the largest number with N digits by recursion. ...
摘要：對(duì)于大數(shù)據(jù)量，則可以用二分查找進(jìn)行優(yōu)化。有一個(gè)模塊，用于維護(hù)有序列表。和用于指定列表的區(qū)間，默認(rèn)是使用整個(gè)列表。模塊提供的函數(shù)可以分兩類只用于查找，不進(jìn)行實(shí)際的插入而則用于實(shí)際插入。 Python 的列表（list）內(nèi)部實(shí)現(xiàn)是一個(gè)數(shù)組，也就是一個(gè)線性表。在列表中查找元素可以使用 list.index() 方法，其時(shí)間復(fù)雜度為O(n)。對(duì)于大數(shù)據(jù)量，則可以用二分查找進(jìn)行優(yōu)化。二分查找要求...
摘要：代碼其中方法的棧幀如下，一共個(gè)類型的局部變量一共占用個(gè)字感謝您的耐心閱讀，如果您發(fā)現(xiàn)文章中有一些沒(méi)表述清楚的，或者是不對(duì)的地方，請(qǐng)給我留言，您的鼓勵(lì)是作者寫作最大的動(dòng)力。 代碼 package com.mousycoder.mycode.happy_jvm; /** * @version 1.0 * @author: mousycoder * @date: 2019...
閱讀 3174·2021-11-19 09:40
閱讀 3664·2021-11-16 11:52
閱讀 2993·2021-11-11 16:55
閱讀 3191·2019-08-30 15:55
閱讀 1195·2019-08-30 13:08
閱讀 1667·2019-08-29 17:03
閱讀 3027·2019-08-29 16:19
閱讀 2589·2019-08-29 13:43
