javascript: fungsi anonim rekursif?

Katakanlah saya memiliki fungsi rekursif dasar:

function recur(data) {
    data = data+1;
    var nothing = function() {
        recur(data);
    }
    nothing();
}

Bagaimana saya bisa melakukan ini jika saya memiliki fungsi anonim seperti ...

(function(data){
    data = data+1;
    var nothing = function() {
        //Something here that calls the function?
    }
    nothing();
})();

Saya ingin cara memanggil fungsi yang memanggil fungsi ini ... Saya telah melihat skrip di suatu tempat (saya tidak ingat di mana) yang dapat memberi tahu Anda nama fungsi yang dipanggil, tetapi saya tidak dapat mengingat satu pun informasi itu sekarang.

Anda bisa memberi nama fungsi, bahkan saat Anda membuat fungsi sebagai nilai dan bukan pernyataan "deklarasi fungsi". Dengan kata lain:

(function foo() { foo(); })();

adalah fungsi rekursif stack-blowing. Sekarang, yang mengatakan, Anda mungkin tidak mungkin tidak ingin melakukan ini secara umum karena ada beberapa masalah aneh dengan berbagai implementasi Javascript. ( catatan - itu adalah komentar yang cukup lama; beberapa / banyak / semua masalah yang dijelaskan dalam posting blog Kangax mungkin diperbaiki di browser yang lebih modern.)

Ketika Anda memberi nama seperti itu, nama itu tidak terlihat di luar fungsi (yah, itu tidak seharusnya; itu salah satu keanehan). Ini seperti "letrec" di Lisp.

Adapun arguments.callee, hal itu tidak diizinkan dalam mode "ketat" dan umumnya dianggap sebagai hal yang buruk, karena akan mempersulit pengoptimalan. Ini juga jauh lebih lambat dari yang diperkirakan.

edit - Jika Anda ingin mendapatkan efek dari fungsi "anonim" yang dapat memanggil dirinya sendiri, Anda dapat melakukan sesuatu seperti ini (dengan asumsi Anda meneruskan fungsi tersebut sebagai panggilan balik atau sesuatu seperti itu):

asyncThingWithCallback(params, (function() {
  function recursive() {
    if (timeToStop())
      return whatever();
    recursive(moreWork);
  }
  return recursive;
})());

Apa yang dilakukannya adalah menentukan fungsi dengan pernyataan deklarasi fungsi yang bagus, aman, tidak rusak di IE , membuat fungsi lokal yang namanya tidak akan mencemari namespace global. Fungsi wrapper (benar-benar anonim) hanya mengembalikan fungsi lokal tersebut.

Orang-orang membicarakan tentang kombinator Y dalam komentar, tetapi tidak ada yang menulisnya sebagai jawaban.

Kombinator Y dapat didefinisikan dalam javascript sebagai berikut: (terima kasih kepada steamer25 untuk tautannya)

var Y = function (gen) {
  return (function(f) {
    return f(f);
  }(function(f) {
    return gen(function() {
      return f(f).apply(null, arguments);
    });
  }));
}

Dan ketika Anda ingin meneruskan fungsi anonim Anda:

(Y(function(recur) {
  return function(data) {
    data = data+1;
    var nothing = function() {
      recur(data);
    }
    nothing();
  }
})());

Hal terpenting yang perlu diperhatikan tentang solusi ini adalah Anda tidak boleh menggunakannya.

U kombinator

Dengan meneruskan fungsi ke dirinya sendiri sebagai argumen, sebuah fungsi bisa berulang menggunakan parameternya alih-alih namanya! Jadi fungsi yang diberikan Uharus memiliki setidaknya satu parameter yang akan mengikat fungsi (itu sendiri).

Dalam contoh di bawah ini, kami tidak memiliki kondisi keluar, jadi kami hanya akan mengulang tanpa batas hingga tumpukan overflow terjadi

const U = f => f (f) // call function f with itself as an argument

U (f => (console.log ('stack overflow imminent!'), U (f)))

Kami dapat menghentikan rekursi tak terbatas menggunakan berbagai teknik. Di sini, saya akan menulis fungsi anonim kami untuk mengembalikan fungsi anonim lain yang menunggu masukan; dalam hal ini, beberapa nomor. Ketika angka diberikan, jika lebih besar dari 0, kami akan terus berulang, jika tidak mengembalikan 0.

const log = x => (console.log (x), x)

const U = f => f (f)

// when our function is applied to itself, we get the inner function back
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
// returns: (x => x > 0 ? U (f) (log (x - 1)) : 0)
// where f is a reference to our outer function

// watch when we apply an argument to this function, eg 5
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0) (5)
// 4 3 2 1 0

Apa yang tidak langsung terlihat di sini adalah bahwa fungsi kita, saat pertama kali diterapkan ke dirinya sendiri menggunakan Ukombinator, ia mengembalikan fungsi yang menunggu masukan pertama. Jika kami memberi nama untuk ini, dapat secara efektif membangun fungsi rekursif menggunakan lambda (fungsi anonim)

const log = x => (console.log (x), x)

const U = f => f (f)

const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)

countDown (5)
// 4 3 2 1 0

countDown (3)
// 2 1 0

Hanya ini bukan rekursi langsung - fungsi yang memanggil dirinya sendiri menggunakan namanya sendiri. Definisi kami tentang countDowntidak merujuk dirinya sendiri di dalam tubuhnya dan rekursi tetap dimungkinkan

// direct recursion references itself by name
const loop = (params) => {
  if (condition)
    return someValue
  else
    // loop references itself to recur...
    return loop (adjustedParams)
}

// U combinator does not need a named reference
// no reference to `countDown` inside countDown's definition
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)

Cara menghapus referensi mandiri dari fungsi yang ada menggunakan kombinator U.

Di sini saya akan menunjukkan kepada Anda cara mengambil fungsi rekursif yang menggunakan referensi ke dirinya sendiri dan mengubahnya menjadi fungsi yang menggunakan kombinator U sebagai pengganti referensi mandiri.

const factorial = x =>
  x === 0 ? 1 : x * factorial (x - 1)
  
console.log (factorial (5)) // 120

Sekarang menggunakan kombinator U untuk mengganti referensi bagian dalam factorial

const U = f => f (f)

const factorial = U (f => x =>
  x === 0 ? 1 : x * U (f) (x - 1))

console.log (factorial (5)) // 120

Pola penggantian dasarnya adalah ini. Buat catatan mental, kami akan menggunakan strategi serupa di bagian selanjutnya

// self reference recursion
const foo =         x => ...   foo (nextX) ...

// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)

Kombinator Y

terkait: kombinator U dan Y dijelaskan menggunakan analogi cermin

Pada bagian sebelumnya kita telah melihat bagaimana mengubah rekursi referensi diri menjadi fungsi rekursif yang tidak bergantung pada fungsi bernama menggunakan kombinator U. Ada sedikit gangguan karena harus ingat untuk selalu meneruskan fungsi ke dirinya sendiri sebagai argumen pertama. Nah, kombinator-Y dibangun di atas kombinator-U dan menghilangkan bagian yang membosankan itu. Ini adalah hal yang baik karena menghilangkan / mengurangi kompleksitas adalah alasan utama kami membuat fungsi

Pertama, mari turunkan kombinator-Y kita sendiri

// standard definition
const Y = f => f (Y (f))

// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (x => Y (f) (x))

// remove reference to self using U combinator
const Y = U (h => f => f (x => U (h) (f) (x)))

Sekarang kita akan melihat bagaimana penggunaannya dibandingkan dengan U-combinator. Perhatikan, untuk berulang, alih-alih U (f)kita bisa langsung meneleponf ()

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

Y (f => (console.log ('stack overflow imminent!'),  f ()))

Sekarang saya akan mendemonstrasikan penggunaan countDownprogram Y- Anda akan melihat programnya hampir identik tetapi kombinator Y menjaga semuanya sedikit lebih bersih

const log = x => (console.log (x), x)

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const countDown = Y (f => x => x > 0 ? f (log (x - 1)) : 0)

countDown (5)
// 4 3 2 1 0

countDown (3)
// 2 1 0

Dan sekarang kita akan lihat factorialjuga

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const factorial = Y (f => x =>
  x === 0 ? 1 :  x * f (x - 1))

console.log (factorial (5)) // 120

Seperti yang Anda lihat, fmenjadi mekanisme rekursi itu sendiri. Untuk berulang, kami menyebutnya seperti fungsi biasa. Kita bisa memanggilnya berkali-kali dengan argumen berbeda dan hasilnya akan tetap benar. Dan karena ini adalah parameter fungsi biasa, kita dapat menamainya sesuka kita, seperti di recurbawah ini -

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (recur => n =>
  n < 2 ? n : recur (n - 1) +  (n - 2))

console.log (fibonacci (10)) // 55

Kombinator U dan Y dengan lebih dari 1 parameter

Pada contoh di atas, kita melihat bagaimana kita dapat mengulang dan meneruskan argumen untuk melacak "status" dari komputasi kita. Tetapi bagaimana jika kita perlu melacak status tambahan?

Kita bisa menggunakan data gabungan seperti Array atau sesuatu ...

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (f => ([a, b, x]) =>
  x === 0 ? a : f ([b, a + b, x - 1]))

// starting with 0 and 1, generate the 7th number in the sequence
console.log (fibonacci ([0, 1, 7])) 
// 0 1 1 2 3 5 8 13

Tapi ini buruk karena mengekspos keadaan internal (penghitung adan b). Alangkah baiknya jika kita bisa menelepon fibonacci (7)untuk mendapatkan jawaban yang kita inginkan.

Menggunakan apa yang kita ketahui tentang fungsi curried (urutan fungsi unary (1-paramter)), kita dapat mencapai tujuan kita dengan mudah tanpa harus mengubah definisi kita Yatau mengandalkan data gabungan atau fitur bahasa tingkat lanjut.

Perhatikan definisi di fibonaccibawah ini. Kami segera melamar 0dan 1yang terikat adan bmasing - masing. Sekarang fibonacci hanya menunggu argumen terakhir yang akan diberikan x. Ketika kita berulang, kita harus memanggil f (a) (b) (x)(bukan f (a,b,x)) karena fungsi kita dalam bentuk kari.

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const fibonacci = Y (f => a => b => x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)

console.log (fibonacci (7)) 
// 0 1 1 2 3 5 8 13

Pola semacam ini dapat berguna untuk mendefinisikan semua jenis fungsi. Di bawah ini kita akan melihat dua fungsi yang lebih didefinisikan dengan menggunakan Ycombinator ( rangedan reduce) dan turunan dari reduce, map.

const U = f => f (f)

const Y = U (h => f => f (x => U (h) (f) (x)))

const range = Y (f => acc => min => max =>
  min > max ? acc : f ([...acc, min]) (min + 1) (max)) ([])

const reduce = Y (f => g => y => ([x,...xs]) =>
  x === undefined ? y : f (g) (g (y) (x)) (xs))
  
const map = f =>
  reduce (ys => x => [...ys, f (x)]) ([])
  
const add = x => y => x + y

const sq = x => x * x

console.log (range (-2) (2))
// [ -2, -1, 0, 1, 2 ]

console.log (reduce (add) (0) ([1,2,3,4]))
// 10

console.log (map (sq) ([1,2,3,4]))
// [ 1, 4, 9, 16 ]

INI SEMUA ANONIM OMG

Karena kami bekerja dengan fungsi murni di sini, kami dapat mengganti fungsi bernama apa pun untuk definisinya. Perhatikan apa yang terjadi saat kita menggunakan fibonacci dan mengganti fungsi bernama dengan ekspresinya

/* const U = f => f (f)
 *
 * const Y = U (h => f => f (x => U (h) (f) (x)))
 *
 * const fibonacci = Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
 *
 */

/*
 * given fibonacci (7)
 *
 * replace fibonacci with its definition
 * Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
 *
 * replace Y with its definition
 * U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
//
 * replace U with its definition
 * (f => f (f)) U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
 */

let result =
  (f => f (f)) (h => f => f (x => h (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
  
console.log (result) // 13

Dan begitulah - fibonacci (7)dihitung secara rekursif hanya dengan menggunakan fungsi anonim

Mungkin paling sederhana menggunakan "objek anonim" sebagai gantinya:

({
  do: function() {
    console.log("don't run this ...");
    this.do();
  }
}).do();

Ruang global Anda benar-benar tidak tercemar. Ini sangat mudah. Dan Anda dapat dengan mudah memanfaatkan status non-global objek.

Anda juga dapat menggunakan metode objek ES6 untuk membuat sintaks lebih ringkas.

({
  do() {
    console.log("don't run this ...");
    this.do();
  }
}).do();

Saya tidak akan melakukan ini sebagai fungsi sebaris. Itu mendorong batas-batas selera yang baik dan tidak benar-benar memberi Anda apa pun.

Jika memang harus, ada arguments.calleeseperti dalam jawaban Fabrizio. Namun hal ini umumnya dianggap tidak disarankan dan tidak diizinkan dalam 'mode ketat' ECMAScript Fifth Edition. Meskipun ECMA 3 dan mode non-ketat tidak akan hilang, bekerja dalam mode ketat menjanjikan lebih banyak kemungkinan pengoptimalan bahasa.

Seseorang juga dapat menggunakan fungsi sebaris bernama:

(function foo(data){
    data++;
    var nothing = function() {
        foo(data);
    }
    nothing();
})();

Namun, ekspresi fungsi sebaris bernama juga sebaiknya dihindari, karena JScript IE melakukan beberapa hal buruk padanya. Dalam contoh di atas foosalah mencemari lingkup induk di IE, dan induk fooadalah contoh terpisah untuk footerlihat di dalamfoo .

Apa tujuan meletakkan ini dalam fungsi anonim sebaris? Jika Anda hanya ingin menghindari mencemari lingkup induk, tentu saja Anda dapat menyembunyikan contoh pertama Anda di dalam fungsi anonim (namespace) panggilan mandiri lainnya. Apakah Anda benar-benar perlu membuat salinan baru nothingsetiap kali sekitar rekursi? Anda mungkin lebih baik menggunakan namespace yang berisi dua fungsi sederhana yang saling rekursif.

(function(data){
    var recursive = arguments.callee;
    data = data+1;
    var nothing = function() {
        recursive(data)
    }
    nothing();
})();

Anda bisa melakukan sesuatu seperti:

(foo = function() { foo(); })()

atau dalam kasus Anda:

(recur = function(data){
    data = data+1;
    var nothing = function() {
        if (data > 100) return; // put recursion limit
        recur(data);
    }
    nothing();
})(/* put data init value here */ 0);

Saat Anda mendeklarasikan fungsi anonim seperti ini:

(function () {
    // Pass
}());

Ini dianggap sebagai ekspresi fungsi dan memiliki nama opsional (yang dapat Anda gunakan untuk memanggilnya dari dalam dirinya sendiri. Tetapi karena ini adalah ekspresi fungsi (dan bukan pernyataan), ia tetap anonim (tetapi memiliki nama yang dapat Anda panggil). Jadi fungsi ini dapat memanggil dirinya sendiri:

(function foo () {
    foo();
}());
foo //-> undefined

Mengapa tidak meneruskan fungsi ke functio itu sendiri?

    var functionCaller = function(thisCaller, data) {
        data = data + 1;
        var nothing = function() {
            thisCaller(thisCaller, data);
        };
        nothing();
    };
    functionCaller(functionCaller, data);

Dalam situasi tertentu Anda harus mengandalkan fungsi anonim. Diberikan adalah mapfungsi rekursif :

const map = f => acc => ([head, ...tail]) => head === undefined 
 ? acc
 : map (f) ([...acc, f(head)]) (tail);

const sqr = x => x * x;
const xs = [1,2,3,4,5];

console.log(map(sqr) ([0]) (xs)); // [0] modifies the structure of the array

Harap dicatat bahwa maptidak boleh mengubah struktur array. Jadi akumulator acctidak perlu diekspos. Kita bisa membungkus mapfungsi lain misalnya:

const map = f => xs => {
  let next = acc => ([head, ...tail]) => head === undefined
   ? acc
   : map ([...acc, f(head)]) (tail);

  return next([])(xs);
}

Tapi solusi ini cukup bertele-tele. Mari gunakan Ukombinator yang diremehkan :

const U = f => f(f);

const map = f => U(h => acc => ([head, ...tail]) => head === undefined 
 ? acc
 : h(h)([...acc, f(head)])(tail))([]);

const sqr = x => x * x;
const xs = [1,2,3,4,5];

console.log(map(sqr) (xs));

Ringkas, bukan? Usangat sederhana tetapi memiliki kelemahan bahwa panggilan rekursif menjadi agak dikaburkan: sum(...)menjadi h(h)(...)- itu saja.

Saya tidak yakin apakah jawabannya masih diperlukan tetapi ini juga dapat dilakukan dengan menggunakan delegasi yang dibuat menggunakan function.bind:

    var x = ((function () {
        return this.bind(this, arguments[0])();
    }).bind(function (n) {
        if (n != 1) {
            return n * this.bind(this, (n - 1))();
        }
        else {
            return 1;
        }
    }))(5);

    console.log(x);

Ini tidak melibatkan fungsi atau argumen bernama.callee.

Seperti bobince menulis, cukup beri nama fungsi Anda.

Tapi, saya rasa Anda juga ingin meneruskan nilai awal dan akhirnya menghentikan fungsi Anda!

var initialValue = ...

(function recurse(data){
    data++;
    var nothing = function() {
        recurse(data);
    }
    if ( ... stop condition ... )
        { ... display result, etc. ... }
    else
        nothing();
}(initialValue));

Contoh jsFiddle yang berfungsi (menggunakan data + = data untuk bersenang-senang)

saya membutuhkan (atau lebih tepatnya, menginginkan) fungsi anonim satu baris untuk berjalan di atas objek yang membangun string, dan menanganinya seperti ini:

var cmTitle = 'Root' + (function cmCatRecurse(cmCat){return (cmCat == root) ? '' : cmCatRecurse(cmCat.parent) + ' : ' + cmCat.getDisplayName();})(cmCurrentCat);

yang menghasilkan string seperti 'Root: foo: bar: baz: ...'

Dengan ES2015 kita bisa bermain-main sedikit dengan sintaks dan penyalahgunaan parameter default dan thunks. Yang terakhir hanyalah fungsi tanpa argumen:

const applyT = thunk => thunk();

const fib = n => applyT(
  (f = (x, y, n) => n === 0 ? x : f(y, x + y, n - 1)) => f(0, 1, n)
);

console.log(fib(10)); // 55

// Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Harap dicatat bahwa fini adalah parameter dengan fungsi anonim (x, y, n) => n === 0 ? x : f(y, x + y, n - 1)sebagai nilai defaultnya. Kapan fdipanggil oleh applyTpemanggilan ini harus dilakukan tanpa argumen, sehingga nilai default yang digunakan. Nilai default-nya adalah sebuah fungsi dan karenanya fmerupakan fungsi bernama, yang dapat memanggil dirinya sendiri secara rekursif.

Jawaban lain yang tidak melibatkan fungsi bernama atau argumen.callee

var sum = (function(foo,n){
  return n + foo(foo,n-1);
})(function(foo,n){
     if(n>1){
         return n + foo(foo,n-1)
     }else{
         return n;
     }
},5); //function takes two argument one is function and another is 5

console.log(sum) //output : 15

Ini adalah pengerjaan ulang jawaban jforjs dengan nama berbeda dan entri yang sedikit dimodifikasi.

// function takes two argument: first is recursive function and second is input
var sum = (function(capturedRecurser,n){
  return capturedRecurser(capturedRecurser, n);
})(function(thisFunction,n){
     if(n>1){
         return n + thisFunction(thisFunction,n-1)
     }else{
         return n;
     }
},5); 

console.log(sum) //output : 15

Tidak perlu membuka gulungan rekursi pertama. Fungsi yang menerima dirinya sendiri sebagai referensi mengingatkan kembali pada cairan primordial OOP.

Ini adalah versi jawaban @ zem dengan fungsi panah.

Anda dapat menggunakan UatauY kombinator. Kombinator Y menjadi yang paling sederhana untuk digunakan.

U combinator, dengan ini Anda harus terus meneruskan fungsinya: const U = f => f(f) U(selfFn => arg => selfFn(selfFn)('to infinity and beyond'))

Y combinator, dengan ini Anda tidak harus terus meneruskan fungsi: const Y = gen => U(f => gen((...args) => f(f)(...args))) Y(selfFn => arg => selfFn('to infinity and beyond'))

Namun solusi Y-combinator lainnya, menggunakan tautan kode rosetta (saya pikir seseorang sebelumnya menyebutkan tautan di suatu tempat di stackOverflow.

Panah adalah untuk fungsi anonim yang lebih mudah dibaca oleh saya:

var Y = f => (x => x(x))(y => f(x => y(y)(x)));

Ini mungkin tidak berfungsi di semua tempat, tetapi Anda dapat menggunakan arguments.calleeuntuk merujuk ke fungsi saat ini.

Jadi, faktorial dapat dilakukan sebagai berikut:

var fac = function(x) { 
    if (x == 1) return x;
    else return x * arguments.callee(x-1);
}