Understanding Recursion

HtmlCssJs 发布于2019-08-22 15:42 / 3492人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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