Рекурсия для начинающих в JavaScript с 8 примерами

  • 28 ноября, 13:29
  • 1497
  • 0

Рекурсия является одним из самых полезных, но очень мало понятных методов программирования. Существуют особые виды проблем, которые могут быть решены очень просто и изящно с помощью рекурсивной функции (например, поиск файла в иерархической файловой системе).

Рекурсия для начинающих в JavaScript с 8 примерами

Эта статья не предназначена для объяснения того, как работает рекурсия ... но в статье представлены 8 классических задач, реализованных как с использованием рекурсивного решения, так и итеративного решения.

Как вы, вероятно, видите ... для некоторых задач рекурсия происходит более естественно, а для других она не должна использоваться вообще.

1. Рассчитать сумму натуральных чисел до n

Рекурсивное решение

var sum = addTo(10);
println(sum);

function addTo(n)
{
    if (n == 0)
        return 0;

    return n + addTo(n - 1);
}

Итеративное решение

var sum = addTo(10);
println(sum);

function addTo(n)
{
    var sum = 0;

    for(var i = 1; i <= n; i++)
    {
        sum += i;
    }

    return sum;
}

2. Рассчитать факториал из n. Напоминание! = 1 * 2 * ... * n

Рекурсивное решение

var prod = factorial(10);
println(prod);

function factorial(n)
{
    if (n <= 1)
        return 1;

    return n * factorial(n - 1);
}

Итеративное решение

var prod = factorial(10);
println(prod);

function factorial(n)
{
    var prod = 1;

    for(var i = 1; i <= n; i++)
    {
        prod *= i;
    }

    return prod;
}

3. Рассчитать значение n в m мощности

Рекурсивное решение

println(powerNo(3, 2));

function powerNo(n, m)
{
    if (m == 0)
        return 1;

    if (m == 1)
        return n;

    return n * powerNo(n, m - 1);
}

Итеративное решение

println(powerNo(3, 2));

function powerNo(n, m)
{
    var prod = 1;

    for(var i = 1; i <= m; i++)
    {
        prod *= n;
    }

    return prod;
}

4. Найти n-е число Фибоначчи

Рекурсивное решение

function findFibonacci(n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return findFibonacci(n - 1) + findFibonacci(n - 2);
}

var n = findFibonacci(10);
println(n);
Итеративное решение

function findFibonacci(n)
{
    var fib0 = 0;
    var fib1 = 1;

    if (n == 0)
        return fib0;

    if (n == 1)
        return fib1;

    var fib;

    for(var i = 2; i <= n; i++)
    {
        fib = fib0 + fib1;

        fib0 = fib1;
        fib1 = fib;
    }

    return fib;
}

println(findFibonacci(10));

5. Рассчитать сумму элементов массива чисел

Рекурсивное решение

var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var n = sum(ar);
println(n);


function sum(ar)
{
    return _sum(ar, ar.length - 1);
}

function _sum(ar, index)
{
    if (index == 0)
        return ar[0];

    return ar[index] + _sum(ar, index - 1);
}

Итеративное решение

var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var n = sum(ar);
println(n);

function sum(ar)
{
    var sum = 0;

    for(var el of ar)
    {
        sum += el;
    }

    return sum;
}

6. Сортировать массив чисел, используя алгоритм пузырьковой сортировки

Рекурсивное решение

var ar = [23, 1000, 1, -1, 8, 3];
println(ar);
bubbleSort(ar);
println(ar);

function bubbleSort(ar)
{
    var shouldSort = false;

    for(var i = 0; i < ar.length - 1; i++)
    {
        var a = ar[i];
        if ( a > ar[i+1] )
        {
            ar[i] = ar[i+1];
            ar[i+1] = a;
            shouldSort = true;
        }
    }

    if (shouldSort)
    {
        bubbleSort(ar);
    }
}

Итеративное решение

var ar = [23, 1000, 1, -1, 8, 3];
println(ar);
bubbleSort(ar);
println(ar);

function bubbleSort(ar)
{
    var shouldSort = true;

    while(shouldSort)
    {
        shouldSort = false;

        for(var i = 0; i < ar.length - 1; i++)
        {
            var a = ar[i];
            if ( a > ar[i+1] )
            {
                ar[i] = ar[i+1];
                ar[i+1] = a;
                shouldSort = true;
            }
        }
    }
}

7. Найти число в отсортированном массиве (бинарный поиск)

Рекурсивное решение

//        0   1   2   3   4   5   6   7   8   9
var ar = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

var position = findNumber(90, ar);
println(position);

// Find number n in sorted array ar
// Returns array index if found or -1 if not found
function findNumber(n, ar)
{
    return _findNumber(n, ar, 0, ar.length - 1);
}

// Find number n in sorted array ar in between indexes i1 and i2
// using recursive approach
function _findNumber(n, ar, i1, i2)
{
    if (i2 < i1)
        return -1;

    println("Checking interval: [" + i1 + ", " + i2 + "]");

    var mid = i1 + Math.floor((i2 - i1) / 2);

    if (n === ar[mid])
        return mid;

    if (n < ar[mid])
        return _findNumber(n, ar, i1, mid - 1);

    return _findNumber(n, ar, mid + 1, i2);
}

Итеративное решение

//        0   1   2   3   4   5   6   7   8   9
var ar = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

var position = findNumber(90, ar);
println(position);

// Find number n in sorted array ar using iterative approach
// Returns array index if found or -1 if not found
function findNumber(n, ar)
{
    var i1 = 0;
    var i2 = ar.length - 1;

    while(i1 <= i2)
    {
        println("Checking interval: [" + i1 + ", " + i2 + "]");

        var mid = i1 + Math.floor((i2 - i1) / 2);

        if (n === ar[mid])
            return mid;

        if (n < ar[mid])
        {
            i2 = mid - 1;
        }
        else
        {
            i1 = mid + 1;
        }
    }

    return -1;
}

8. Найти максимальное число в массиве, содержащем числа или другие массивы чисел

Рекурсивное решение

var ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];

var max = findMax(ar);
println("Max  = ", max);

// Use recursion to find the maximum numeric value in an array of arrays
function findMax(ar)
{
    var max = -Infinity;

    // Cycle through all the elements of the array
    for(var i = 0; i < ar.length; i++)
    {
        var el = ar[i];

        // If an element is of type array then invoke the same function
        // to find out the maximum element of that subarray
        if ( Array.isArray(el) )
        {
            el = findMax( el );
        }

        if ( el > max )
        {
            max = el;
        }
    }

    return max;
}

Итеративное решение

// Find the maximum number in a jagged array of numbers or array of numbers
// Do not use recursion

var ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];

var max = findMax(ar);
println("Max  = ", max);

// Use a stack to find the maximum numeric value in an array of arrays
function findMax(arElements)
{
    var max = -Infinity;

    // This is the stack on which will put the first array and then 
    // all the other sub-arrays that we find as we traverse an array     
    var arrays = [];

    arrays.push(arElements);

    // Loop as long as are arrays added to the stack for processing
    while(arrays.length > 0)
    {
        // Extract an array from the stack
        ar = arrays.pop();

        // ... and loop through its elements
        for(var i = 0; i < ar.length; i++)
        {
            var el = ar[i];

            // If an element is of type array, we'll add it to stack
            // to be processed later
            if ( Array.isArray(el) )
            {
                arrays.push(el);
                continue;
            }

            if ( el > max )
            {
                max = el;
            }
        }
    }

    return max;
}


0 комментариев
Сортировка:
Добавить комментарий