find（）の再帰バージョン

Question

私がしようとしているのは、配列とテスト関数を受け取り、テストに合格する配列の最初の要素を返すfindの再帰バージョンを作ることです。例を見てみましょう：

function isEven(num) { return(num%2 == 0); } 
var arr = [1, 3, 5, 4, 2]; 

function findRecursive(arr, func) { 
    var p = arr.shift(); 
    if (func(p) == true) 
     return p; 
    else 
     findRecursive(arr, func); 
} 

findRecursive(arr, isEven); 

何らかの理由で私は未定義になっています。しかし、もし私が5行目のポップにシフトすると、正しく2が返ってきます。何が問題なのですか？

Answer 1

再帰呼び出しの値を返す必要があります。それ以外の場合は、undefined、関数の標準return valueをJavascriptに返します。

} else { 
    return findRecursive(arr, func); 
    // ^^^ 
} 

チェックする要素がもうない場合は、配列の長さのチェックを挿入することができます。その後、意図的にundefinedを返すことができます。

function isEven(num) { return num % 2 === 0; } 
 

 
function findRight(array, fn) { 
 
    if (!array.length) { 
 
     return; 
 
    } 
 

 
    var p = array.pop(); 
 
    return fn(p) ? p : findRight(array, fn); 
 
} 
 

 
console.log(findRight([1, 3, 5, 4, 2], isEven)); // 2 
 
console.log(findRight([1, 3, 5], isEven));  // undefined

Answer 2

再帰は、関数型プログラミングの文脈で生まれたループ機構です。その文脈から抜け出すことは、再帰がどのように使われることになっているかについての粗い理解を可能にするだけです。

再帰は、永続的な（不変の）データ型や純粋な関数のような他の関数プログラミング慣行と併用すると、表現

const find = (f, [x,...xs]) => 
 
    x === undefined 
 
    ? x 
 
    : f (x) 
 
     ? x 
 
     : find (f, xs) 
 

 
const isEven = x => 
 
    (x & 1) === 0 
 
     
 
console.log (find (isEven, [1, 3, 5, 4, 2])) // 4 
 
console.log (find (isEven, [1, 3, 5, 7, 9])) // undefined

Be careful with recursion in JavaScript, tho - 大型アレイ上のスタックを吹い避けるために、スタック・安全なループ・メカニズムを使用し

あなたはfindRecursive` `から復帰するのを忘れ

const recur = (...values) => 
 
    ({ type: recur, values }) 
 
    
 
const loop = f => 
 
    { 
 
    let acc = f() 
 
    while (acc && acc.type === recur) 
 
     acc = f (...acc.values) 
 
    return acc 
 
    } 
 
    
 
const find = (f, xs) => 
 
    loop ((i = 0) => 
 
    i === xs.length 
 
     ? undefined 
 
     : f (xs [i]) 
 
     ? xs [i] 
 
     : recur (i + 1)) 
 

 
const isEven = x => 
 
    (x & 1) === 0 
 

 
// [ 1, 2, 3, 4, ... 20000 ] 
 
const numbers = 
 
    Array.from (Array (2e4), (x,n) => n + 1) 
 
    
 
console.log (find (isEven, numbers))  // 2 
 

 
// this would have blown the stack using the first version of `find` 
 
// but it works just fine here, thanks to loop/recur 
 
console.log (find (x => x < 0, numbers)) // undefined