Рекурсия является одним из самых полезных, но очень мало понятных методов программирования. Существуют особые виды проблем, которые могут быть решены очень просто и изящно с помощью рекурсивной функции (например, поиск файла в иерархической файловой системе).
Эта статья не предназначена для объяснения того, как работает рекурсия ... но в статье представлены 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 комментариев
Добавить комментарий