Компьютердик борбор

Келгиле, функцияларга кайрылып, аларды кененирээк изилдеп көрөлү.

Биздин биринчи темабыз рекурсия болот .

Эгерде сиз программалоодо жаңы эмес болсоңуз, анда сиз рекурсия менен мурунтан эле тааныш болушуңуз мүмкүн жана бул бөлүмдү өткөрүп жиберсеңиз болот.

Рекурсия – бул тапшырма табигый түрдө бир нече окшош, бирок жөнөкөй тапшырмаларга бөлүнүшү мүмкүн болгон кырдаалдарда пайдалуу программалоо ыкмасы. Же тапшырманы жөнөкөй аракеттерге жана бир эле тапшырманын жөнөкөй версиясына чейин жөнөкөйлөштүрсө болот. Же болбосо, биз жакын арада көрө тургандай, белгилүү бир маалымат структуралары менен иштөө.

Функциянын денесинде тапшырманы аткаруу учурунда башка функциялар кошумча тапшырмаларды аткарууга чакырылышы мүмкүн. Субчакыруунун өзгөчө учуру бул функция өзүн чакырганда . Бул рекурсия деп аталат .

Ой жүгүртүүнүн эки жолу

Биринчи мисал катары, табигый күчкө pow(x, n)көтөрүүчү функцияны жазалы . Башкача айтканда, ал өзүнөн эсе көбөйөт .xnxn

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Аны ишке ашыруунун эки жолун карап көрөлү.

Итеративдик жол: цикл for:

	@A@function pow(x, n) {
  let result = 1;

  // умножаем result на x n раз в цикле
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

alert( pow(2, 3) ); // 8@A@
	

Рекурсивдүү жол: тапшырманы жөнөкөйлөтүү жана функциянын өзүн чакыруу:

 
 

	@A@function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8@A@
	

Рекурсивдүү версия түп-тамырынан бери айырмаланат.

Функция pow(x, n)чакырылганда, аткаруу эки бутакка бөлүнөт:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

Эгерде n == 1, анда бул жөнөкөй. Бул бутак рекурсиянын негизи деп аталат , анткени ал дароо эле айкын натыйжага алып келет: pow(x, 1)барабар x.
pow(x, n)Биз төмөнкү формада көрсөтө алабыз : x * pow(x, n - 1). Кайсы математикада төмөнкүчө жазылат: . Бул бутак рекурсиялык кадам болуп саналат : биз маселени жөнөкөй аракетке (көбөйтүү ) жана жөнөкөй аналогдук маселеге ( азыраак менен ) азайтабыз. Кийинки кадамдар тапшырманы ал жеткенге чейин барган сайын жөнөкөйлөтөт .xⁿ = x * x^n-1xpownn1

Функция өзүнөн мурун pow рекурсивдүү чакыратn == 1 деп айтылат .

Мисалы, эсептөөнүн рекурсивдүү версиясы pow(2, 4)кадамдардан турат:

pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2

Демек, рекурсия функцияны баалоо анын жөнөкөй чакырыгына чейин кыскартылганда колдонулат, ал эми андан да жөнөкөйгө чейин кыскартылышы мүмкүн жана мааниси айкын болгонго чейин.

Проблеманын рекурсивдүү чечими, адатта, кайталануучуга караганда кыскараак болот.

?Анын ордуна шарттуу колдонуу менен , функциянын кодун кыскараак, бирок окууга оңой кылып, ifкайра жаза алабыз :pow(x, n)

@A@function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}@A@

Уяланган чалуулардын жалпы саны (анын ичинде биринчиси) рекурсиянын тереңдиги деп аталат . Биздин учурда, ал барабар болот n.

Рекурсиянын максималдуу тереңдиги JavaScript кыймылдаткычы менен чектелген. Сиз сөзсүз түрдө 10 000 чалууларга ишене аласыз, кээ бир котормочулар көбүрөөк мүмкүнчүлүк берет, бирок алардын көбү үчүн 100 000 чалуу мүмкүн эмес. Чалуу стекинин ашып кетишинин алдын алуу үчүн автоматтык оптималдаштыруулар бар («куйрук рекурсиялык оптималдаштыруу»), бирок алар азырынча универсалдуу колдоого алынбайт жана жөнөкөй учурларда гана иштейт.

Бул рекурсияны колдонууну чектейт, бирок ал дагы эле кеңири колдонулат: көп сандагы маселелерди чечүү үчүн рекурсивдүү чечүү жолу жөнөкөй кодго алып келет, аны сактоо оңой.

Аткаруу контексти, стек

Эми биз рекурсивдүү чалуулар кантип иштээрин көрөбүз. Бул үчүн, функциялардын "капутун астына" карап көрөлү.

Иштеп жаткан функциянын аткарылуу процесси жөнүндө маалымат анын аткаруу контекстинде сакталат .

Аткаруу контексти – бул функция чакырыгы тууралуу маалыматты камтыган атайын ички берилиштер структурасы. Ал котормочу жайгашкан коддун белгилүү бир ордун, функциянын локалдык өзгөрмөлөрүн, маанини this(биз аны бул мисалда колдонбойбуз) жана башка кызмат маалыматын камтыйт.

Бир функция чакырыгында аны менен байланышкан так бир аткаруу контексти бар.

Функция уяча чалуу жасаганда, төмөнкүлөр болот:

Учурдагы функциянын аткарылышы токтотулган.
Аны менен байланышкан аткаруу контексти атайын берилиштер структурасында сакталат - аткаруу контексттик стек .
Ички чалуулар аткарылат, алардын ар бири үчүн өзүнчө аткаруу контексти түзүлөт.
Алар аяктагандан кийин, эски контекст стектен чыгарылат жана тышкы функциянын аткарылышы токтогон жеринен улантылат.

Функцияны чакыруунун мисалын колдонуп, контексттерди кененирээк карап көрөлү pow(2, 3).

pow(2, 3)

Чакыруунун башталышында pow(2, 3)аткаруу контексти өзгөрмөлөрдү сактайт: x = 2, n = 3, аткаруу функциянын биринчи сабында.

Сиз аны төмөнкүдөй диаграммалай аласыз:

Контекст: { x: 2, n: 3, 1-сап } pow(2, 3)

Бул функциянын аткарылышынын башталышы гана. Шарт n == 1туура эмес, андыктан аткаруу экинчи бутагына өтөт if:

@A@function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );@A@

Өзгөрмөлөрдүн маанилери бирдей, бирок функциянын аткарылышы башка сапка секирип кетти, чыныгы контекст:

Контекст: { x: 2, n: 3, сап 5 } pow(2, 3)

Туундуну баалоо үчүн аны жаңы аргументтер менен x * pow(x, n - 1)иштетүү керек .powpow(2, 2)

pow(2, 2)

Уюшкан чалууну аткаруу үчүн, JavaScript аткаруу контекст стекиндеги учурдагы аткаруу контекстти эстейт .

Бул жерде биз ошол эле функцияны чакырып жатабыз pow, бирок бул эч кандай мааниге ээ эмес. Бардык функциялар үчүн процесс бирдей:

Учурдагы контекст стектин башында "эстелет".
Уюшкан чалуу үчүн жаңы контекст түзүлөт.
Уюшкан чалуунун аткарылышы аяктаганда, мурунку чалуунун контексти калыбына келтирилет жана тиешелүү функциянын аткарылышы уланат.

Уюшкан чалуунун башындагы контексттин көрүнүшү pow(2, 2):

Контекст: { x: 2, n: 2, 1-сап } pow(2, 2)
Контекст: { x: 2, n: 3, сап 5 } pow(2, 3)

Жаңы аткаруу контексти стектин жогору жагында (кара шрифт менен), ал эми мурунку эсте калган контексттер анын астында.

Кошумча чалуу аяктаганда, артка секирүү оңой болот, анткени контекст өзгөрмөлөрдү да, коддун токтогон жерин да сактайт. Фигуралардагы "сызык" деген сөз ээн-эркин, чындыгында буйруктар тизмегиндеги так орун эсинде калган.

pow(2, 1)

Процесс кайталанат: линияда жаңы чалуу жасалат 5, азыр аргументтер менен x=2, n=1.

Жаңы аткаруу контексти түзүлөт, мурунку контекст стекке кошулат:

Контекст: { x: 2, n: 1, 1-сап } pow(2, 1)
Контекст: { x: 2, n: 2, 5-сап } pow(2, 2)
Контекст: { x: 2, n: 3, сап 5 } pow(2, 3)

Азыр стекте эки эски контекст жана бир агым бар pow(2, 1).

Чыгыңыз

Аткаруу учурунда pow(2, 1), мурунку иштетүүлөрдөн айырмаланып, шарт n == 1чын, ошондуктан шарттын биринчи бутагы аткарылат if:

@A@function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}@A@

Мындан ары уяча чалуулар жок, ошондуктан функция кайтаруу менен аяктайт 2.

Функция аяктаганда, анын аткаруу контекстинин кереги жок, ошондуктан ал эстутумдан алынып салынат, ал эми мурункусу стектен калыбына келтирилет:

Контекст: { x: 2, n: 2, 5-сап } pow(2, 2)
Контекст: { x: 2, n: 3, сап 5 } pow(2, 3)

Чалууларды иштетүү улантылат pow(2, 2). Натыйжага ээ болуп , кайра кайтып келип pow(2, 1)ишин бүтүрө алат .x * pow(x, n - 1)4

Мурунку чалуунун контексти калыбына келтирилди:

Контекст: { x: 2, n: 3, сап 5 } pow(2, 3)

Эң четки чакыруу өз ишин аяктайт, анын натыйжасы: pow(2, 3) = 8.

Бул учурда рекурсиянын тереңдиги 3 болду .

Жогорудагы сүрөттөрдөн көрүнүп тургандай, рекурсиянын тереңдиги стекте бир убакта сакталган контексттердин максималдуу санына барабар.

Келгиле, эстутум талаптарын карап көрөлү. Рекурсия күтүүдөгү тышкы чалуулар үчүн бардык маалыматтарды стекке сактоого алып келет жана бул учурда экспонентацияны nэстутумда nар кандай контексттерди сактоого алып келет.

Экспонентацияны цикл аркылуу ишке ашыруу алда канча үнөмдүү:

@A@function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}@A@

Функциянын итеративдик версиясы бир контекстти колдонот, анда жана powмаанилери ырааттуу түрдө өзгөрөт . Ошол эле учурда, керектелүүчү эстутум көлөмү аз, туруктуу жана көз каранды эмес .iresultn

Ар кандай рекурсияны циклге айландырса болот. Эреже катары, цикл менен вариант кыйла натыйжалуу болот.

Бирок рекурсияны циклге айландыруу тривиалдуу эмес болушу мүмкүн, өзгөчө функция шарттарга жараша ар кандай рекурсивдүү субчакырыктарды колдонгондо, натыйжалары айкалышканда же тармакташуу татаалыраак болгондо. Оптималдаштыруу керексиз жана таптакыр пайдасыз болушу мүмкүн.

Көбүнчө рекурсияны колдонгон код кыскараак, түшүнүү жана сактоо оңой. Оптимизация бардык жерде талап кылынбайт, эреже катары, жакшы код биз үчүн маанилүү, ошондуктан ал колдонулат.

Рекурсивдүү өтүүлөр

Рекурсиянын дагы бир чоң колдонулушу рекурсивдүү өтүү болуп саналат.

Элестеткиле, бизде компания бар. Кадр түзүмү объекти катары көрсөтүлүшү мүмкүн:

@A@let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};@A@

Башкача айтканда, ишкананын бөлүмдөрү бар.

Бөлүм бир катар кызматкерлерден турушу мүмкүн. Мисалы, sales бир бөлүмдө 2 кызматкер бар: Жон жана Элис.
Же бир бөлүм кичи бөлүмдөргө бөлүнөт, мисалы, бөлүм developmentкичи бөлүмдөрдөн турат: sitesжана internals. Ар бир бөлүмдүн өзүнүн кызматкерлери бар.
Бөлүм чоңойгон сайын бөлүмдөргө (же командаларга) бөлүнүшү да мүмкүн.

Мисалы, бир бөлүм sitesкелечекте командаларга siteAжана siteB. Жана аларды андан ары ажыратууга болот. Бул сүрөттө жок, жөн гана аны эске алуу керек.

Эми бардык айлык акынын суммасын алуу үчүн функция керек дейли. Муну кантип кыла алабыз?

Итеративдик ыкма оңой эмес, анткени структурасы кыйла татаал. Биринчи идея 1-уяланган бөлүмдөрдүн үстүнө салынган цикл менен forобъекттин үстүнөн айлануу. companyБирок, андан кийин бизге 2-деңгээлдеги бөлүмдөрдүн кызматкерлерин кайталоо үчүн көбүрөөк уюлдук циклдер керек sites... Анан дагы 3-деңгээлдеги бөлүмдөр аркылуу келечекте пайда болушу мүмкүнбү? Эгер биз бир объектти айланып өтүү үчүн кодго 3-4 уюшкан илмек салсак, анда ал бир топ эле жаман болот.

Келгиле, рекурсияга аракет кылалы.

Көрүнүп тургандай, биздин функция эмгек акынын өлчөмүн эсептөө үчүн бөлүмдү алганда, эки мүмкүн болгон жагдай бар:

Же бул массив менен "жөнөкөй" бөлүм - анда биз айлык акыларды жөнөкөй циклде чогулта алабыз.
Же бул бөлүмчөлөрү бар объектN - анда биз Nбөлүмдөрдүн ар биринин суммасын алуу үчүн рекурсивдүү чалууларды жасап, натыйжаларды бириктире алабыз.

Качан (1) массивди алганыбызда, бул рекурсиянын негизи, анча маанилүү эмес учур.

Объектти алууда (2) учур рекурсиялык кадам болуп саналат. Татаал тапшырма бөлүмчөлөр үчүн кошумча тапшырмаларга бөлүнөт. Алар, өз кезегинде, кайрадан бөлүмчөлөргө бөлүнүшү мүмкүн, бирок эртеби-кечпи бул бөлүнүү аяктайт жана чечим (1) учурга чейин кыскарат.

Алгоритмди коддон окуу дагы оңой:

 
 

@A@let company = { // тот же самый объект, сжатый для краткости
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// Функция для подсчёта суммы зарплат
function sumSalaries(department) {
  if (Array.isArray(department)) { // случай (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // сумма элементов массива
  } else { // случай (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // рекурсивно вызывается для подотделов, суммируя результаты
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 6700@A@

Код кыска жана түшүнүктүү (мен үмүттөнөм?). Бул рекурсиянын күчү. Бул бөлүмдөрдүн каалаган уя деңгээлинде иштейт.

Чалуу үлгүсү:

Принциби жөнөкөй: объект үчүн рекурсивдүү чалуулар колдонулат {...}, ал эми массивдер [...]рекурсия дарагынын "жалбырагы", алар дароо жыйынтык берет.

Эскертүү, код биз жогоруда айтылган функцияларды колдонот:

Массив элементтеринин суммасын алуу үчүн Массив ыкмаларыarr.reduce бөлүмүндөгү ыкма .
for(val of Object.values(obj))Объекттин баалуулуктарын кайталоо үчүн цикл : Object.valuesмаанилердин массивин кайтарат.

Рекурсивдүү структуралар

Рекурсивдүү (рекурсивдүү аныкталган) берилиштер структурасы – бул өзүнүн бөлүктөрүндө кайталануучу структура.

Биз муну жогорудагы компаниянын структурасынын мисалынан көрдүк.

Компаниянын бөлүмү болуп төмөнкүлөр саналат:

Же бир топ адамдар.
Же бөлүмдөрү бар объект .

Веб-иштеп чыгуучулар үчүн жакшыраак белгилүү мисалдар бар: HTML жана XML документтер.

HTML документинде HTML теги төмөнкүлөрдү камтышы мүмкүн:

Тексттин фрагменттери.
HTML комментарийлери.
Башка HTML тэгдери (өз кезегинде алар текст үзүндүлөрүн/комментарийлерди же башка тегдерди, ж.б. камтышы мүмкүн).

Бул дагы бир рекурсивдүү аныктама.

Жакшыраак түшүнүү үчүн, кээ бир учурларда массивге альтернатива катары колдонулушу мүмкүн болгон "байланышкан тизме" деп аталган дагы бир рекурсивдүү структураны карайбыз.

Шилтемеленген тизме

Биз объекттердин иреттелген тизмесин сактагыбыз келет деп элестетиңиз.

Массив табигый тандоо болот:

@A@let arr = [obj1, obj2, obj3];@A@

... Бирок массивдердин кемчиликтери бар. "Элементти алып салуу" жана "элемент киргизүү" операциялары кымбат. arr.unshift(obj)Мисалы, new га орун бошотуш үчүн операция бардык элементтерди кайра индекстеши керек objжана массив чоң болсо, бул убакытты талап кылат. Ошол эле arr.shift().

Жапырт реиндексациялоону талап кылбаган бир гана структуралык өзгөртүүлөр массивдин аягынан баштап жасалган өзгөртүүлөр болуп саналат: arr.push/pop. Ошентип, массив чоң кезектер үчүн бир топ жай болушу мүмкүн, биз анын башынан иштөөгө туура келет.

Же биз чындап эле тез киргизүү/жок кылуу керек болсо, биз шилтемеленген тизме деп аталган башка маалымат структурасын тандай алабыз .

Шилтемеленген тизме элементи объект катары рекурсивдүү түрдө аныкталат:

value,
nextшилтемеленген тизмедеги кийинки элементке тиешелүү касиет , же nullал акыркы элемент болсо.

Мисал:

@A@let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};@A@

Тизменин графикалык көрүнүшү:

Түзүү үчүн альтернативалуу код:

@A@let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };@A@

Бул жерде биз бир нече объект бар экенин дагы жакшы көрө алабыз, алардын ар бири менен valueжана nextанын кошунасын көрсөтүп турат. Өзгөрмө listчынжырдагы биринчи объект болуп саналат, андыктан nextанын көрсөткүчтөрүн ээрчип, биз каалаган элементке жете алабыз.

Тизмени оңой эле бир нече бөлүккө бөлүп, андан кийин кайра бириктирсе болот:

@A@let secondList = list.next.next;
list.next.next = null;

Бириктирүү:

list.next.next = secondList;@A@

Жана, албетте, биз каалаган жерден элементтерди киргизип же алып сала алабыз.

Мисалы, жаңы элементти кошуу үчүн, биз тизменин биринчи элементин жаңыртышыбыз керек:

@A@let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// добавление нового элемента в список
list = { value: "new item", next: list };@A@

Тизменин ортосунан элементти алып салуу үчүн, nextмурунку элементтин маанисин өзгөртүү керек:

list.next = list.next.next;

list.next1нарктан секирип кетти 2. Наркы 1азыр чынжырдан чыгарылды. Эгерде ал башка жерде сакталбаса, ал эстутумдан автоматтык түрдө өчүрүлөт.

Массивдерден айырмаланып, кайра номерлөө жок, элементтер оңой иретке келтирилет.

Албетте, тизмелер ар дайым массивдерден жакшы эмес. Болбосо, бардыгы тизмелерди гана колдонушмак.

Негизги кемчилиги - индекси боюнча элементке оңой жете албайбыз. Жөнөкөй массивде: arr[n]түз шилтеме. Бирок тизмеде биз биринчи элементтен баштап, nextN-элементи алуу үчүн N жолу барышыбыз керек.

...Бирок мындай операциялар бизге дайыма эле керек эмес. Мисалы, бизге кезек керек болушу мүмкүн, ал тургай, деке керек болушу мүмкүн - бул эки учунан элементтерди абдан тез кошууга/алып салууга мүмкүндүк берген иреттелген структура, бирок ортосуна кирүүнүн кереги жок.

Тизмелер жакшыртылышы мүмкүн:

Тизме аркылуу артка оңой жылдыруу үчүн мурунку пунктка кайрылууга prevкошумча касиетти кошо аласыз .next
Сиз ошондой эле тизменин акыркы элементине шилтеме кыла турган өзгөрмө кошо аласыз tail(жана элементтер аягында кошулганда/алып салынганда аны жаңырта аласыз).
...Башка өзгөртүүлөр болушу мүмкүн: эң негизгиси, маалыматтар структурасы аткаруу жана ыңгайлуулугу жагынан биздин милдеттерибизге дал келет.

Бардыгы

Шарттары:

Рекурсия - бул функция өзүн чакырган программалоо термини. Рекурсивдүү функциялар кээ бир маселелерди кооздук менен чечүү үчүн колдонулушу мүмкүн.

Функция өзүн чакырганда, бул рекурсиялык кадам деп аталат . Рекурсиянын негизин функциянын аргументтери түзөт, алар тапшырманы ушунчалык жөнөкөй кылгандыктан, чечим андан ары уяча чалууларды талап кылбайт.
Рекурсивдүү аныкталган берилиштердин структурасы - бул өзүн колдонуу менен аныктала турган маалымат структурасы.

Мисалы, шилтемеленген тизме тизмеге (же нөлгө) шилтемени камтыган объекттен турган маалымат структурасы катары аныкталышы мүмкүн.
```
list = { value, next -> list }
```
Бул бөлүмдөгү HTML элемент дарагы же бөлүм дарагы сыяктуу дарактар да рекурсивдүү: алардын бутактары бар жана ар бир бутак башка бутактарды камтышы мүмкүн.

Мисалда көргөнүбүздөй sumSalary, рекурсивдүү функциялар аларды кайталоо үчүн колдонулушу мүмкүн.

Ар кандай рекурсивдүү функцияны итеративдик функцияга кайра жазууга болот. Жана бул кээде аткарууну оптималдаштыруу үчүн талап кылынат. Бирок көптөгөн көйгөйлөр үчүн рекурсивдүү чечим жетишерлик тез жана жазууга жана сактоого оңой.

Tasks

Берилгенге чейинки сандардын суммасын эсептегиле

sumTo(n)Сандардын суммасын эсептеген функцияны жазыңыз 1 + 2 + ... + n.

Мисалы:

@A@sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050@A@

Үч чечим чыгарыңыз:

Циклды колдонуу.
Рекурсия аркылуу, анткени sumTo(n) = n + sumTo(n-1)үчүн n > 1.
Арифметикалык прогрессиянын формуласын колдонуу .

Функцияңыздын кандайча иштээрин мисал:

@A2function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050@A@

PS Кайсы чечим эң ылдам? Эң жайбы? Неге?

PPS Рекурсия аркылуу санаса болобу sumTo(100000)?

чечим

Факториалды эсептөө

Натурал сандын факториалы - бул санга көбөйтүлгөн "себя минус один", андан кийин "себя минус два", жана башкалар 1. факториал nкатары белгиленетn!

Факториалдын аныктамасын төмөнкүчө жазса болот:

n! = n * (n - 1) * (n - 2) * ...*1

Ар кандай баалуулуктарга мисал n:

@A@1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120@A@

Кыйынчылык рекурсияны колдонуп factorial(n)кайтаруучу функцияны жазууда турат n!.

@A@alert( factorial(5) ); // 120@A@

PS Кеңеш: n!төмөнкүдөй жазылышы мүмкүн, n * (n-1)!мисалы:3! = 3*2! = 3*2*1! = 6

чечим

Fibonacci сандары

Фибоначчи сандарынын ырааттуулугу формула менен аныкталат . Башкача айтканда, кийинки сан мурунку экөөнүн суммасы катары алынат.F_n = F_n-1 + F_n-2

Алгачкы эки сан 1, анан 2(1+1), анан 3(1+2), 5(2+3)жана башкалар: 1, 1, 2, 3, 5, 8, 13, 21....

Фибоначчи сандары алтын катыш жана бизди курчап турган көптөгөн жаратылыш кубулуштары менен тыгыз байланышта .

Фибоначчи санын fib(n)кайтаруучу функцияны жазыңыз .n-е

Жумуштун мисалы:

function fib(n) { /* ваш код */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

PS Жогорудагы мисалдагы бардык функциялар тез иштеши керек. Чалуу fib(77)секунданын бир бөлүгүнөн ашпашы керек.

чечим

Жалгыз шилтемеленген тизмени чыгаруу

Бизде жалгыз байланышкан тизме бар дейли ( Рекурсия жана стек бөлүмүндө сүрөттөлгөндөй ):

@A@let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};@A@

printList(list)Тизменин элементтерин бирден басып чыгаруучу функцияны жазыңыз .

Эки чечимди жасаңыз: цикл жана рекурсия аркылуу.

Кайсынысы жакшы: рекурсия менен же рекурсиясызбы?

чечим