Understanding Recursion

HtmlCssJs 發布于2019-08-22 15:42 / 3489人閱讀

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 Iteration

An 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.

Solution:

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

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

Notice

If you want to follow the latest news/articles for the series of reading notes, Please 「Watch」to Subscribe.

GPU云服務器云服務器 Understanding recursion non-recursion understanding hbase and bigtable

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/93678.html

[翻譯] JS的遞歸與TCO尾調用優化

這兩天搜了下JS遞歸的相關文章，覺得這篇文章很不錯，就順手翻譯了下，也算給自己做個筆記，題目是我自己加的。原文很長，寫得也很詳盡，這里并非逐字翻譯，而是作者所講的主要概念加上我自己的一些理解，本文中解決方案的實際意義并不是特別大，但算法的邏輯挺有意思，不過也略抽象，理解需要花點時間（囧，估計我太閑了）文中的用例?全部來自原文：原文鏈接：（原題為：理解JS函數式編程中的遞歸）Underst...

pekonchan 2019-08-21 10:49 評論0 收藏0
Python開啟尾遞歸優化!

摘要：尾遞歸優化一般遞歸與尾遞歸一般遞歸執行可以看到一般遞歸每一級遞歸都產生了新的局部變量必須創建新的調用棧隨著遞歸深度的增加創建的棧越來越多造成爆棧尾遞歸尾遞歸基于函數的尾調用每一級調用直接返回遞歸函數更新調用棧沒有新局部變量的產生類似迭代的 Python尾遞歸優化一般遞歸與尾遞歸一般遞歸: def normal_recursion(n): if n == 1: ...

junnplus 2019-07-31 10:54 評論0 收藏0
[LintCode] Print Numbers by Recursion

摘要：只有當位數時，才打印數字。首先分析邊界，應該，然后用存最高位。用函數對進行遞歸運算，同時更新結果數組。更新的過程歸納一下，首先，計算最高位存入，然后，用到倍的和之前里已經存入的所有的數個循環相加，再存入，更新，計算更高位直到等于 Problem Print numbers from 1 to the largest number with N digits by recursion. ...

kumfo 2019-08-14 15:17 評論0 收藏0
Python 二分查找與 bisect 模塊

摘要：對于大數據量，則可以用二分查找進行優化。有一個模塊，用于維護有序列表。和用于指定列表的區間，默認是使用整個列表。模塊提供的函數可以分兩類只用于查找，不進行實際的插入而則用于實際插入。 Python 的列表（list）內部實現是一個數組，也就是一個線性表。在列表中查找元素可以使用 list.index() 方法，其時間復雜度為O(n)。對于大數據量，則可以用二分查找進行優化。二分查找要求...

URLOS 2019-07-31 10:00 評論0 收藏0
【深入淺出-JVM】（6）：棧幀

摘要：代碼其中方法的棧幀如下，一共個類型的局部變量一共占用個字感謝您的耐心閱讀，如果您發現文章中有一些沒表述清楚的，或者是不對的地方，請給我留言，您的鼓勵是作者寫作最大的動力。代碼 package com.mousycoder.mycode.happy_jvm; /** * @version 1.0 * @author: mousycoder * @date: 2019...

wums 2019-08-16 18:35 評論0 收藏0