Индукция. рекурсия
Концепцията зарекурсияе сложна, но необходима концепция за програмист.
Тук не мога да избягам от класическия факторен пример. Факториелът на положително цяло число N е произведението на всички цели числа от 1 до N. Например факториелът на пет е 1*2*3*4*5, тоест 120. Факториелът на едно се счита за равен на 1.
Всичко е ясно. Има обаче друг, абсолютно ужасен начин за дефиниране на това какво е факториел. Този метод на дефиниране се наричаиндуктивен. Ето го:
"Факториелът на едно е 1. Факториелът на всяко положително цяло числоN, по-голямо от едно, е равен наNпъти факториела наN-1."
Ако вече всичко ви е ясно, значи сте професор по математика. Нека обясня за обикновените хора. Да вземем някакво конкретно N, например 100. Тогава ужасната дефиниция ще звучи по-просто: Факториелът на числото 100 е равен на числото 100, умножено по факториела на числото 99.
Какво от това? И как можем да разберем оттук на какво е равен конкретен факториел, да речем факториел от три? Ние също ще спорим по напълно чудовищен начин:
Гледам дефиницията: Факториелът на три е 3 по факториел на две. Не знам какъв е факториелът на две. Така че слизам малко по-надолу.
Гледам дефиницията: Факториелът на две е 2 по факториела на едно. Не знам колко е. Слизам още едно стъпало надолу.
Гледам дефиницията: Факториелът на единица е равен на 1. Ето най-после - за първи път научих конкретно число. Така че можете да се върнете обратно.
Качвам се едно стъпало нагоре. Факториелът на две е 2 по 1, което е 2. Добре.
Качвам се още едно стъпало. Факториелът на три е 3 по 2, което е 6. Проблемът е решен!
Като разсъждаваме по този начин, можем да изчислим факториелапроизволен брой. Този начин на разсъждение се наричарекурсивен.
Какво общо има всичко това с компютрите? Факт е, че рекурсивният метод на разсъждение се прилага в много езици за програмиране, включително Visual Basic. Това означава, че тези езици също трябва да разбират индуктивния начин за писане на програми.
Нека накратко обозначим факториела на числото N като Факториал(N) и отново да повторим нашия индуктивен начин на обяснение:
АкоN>1, тогаваФакториал(N)се изчислява чрез умножаванеNпоФакториал(N-1)."
В съответствие с това обяснение ще напишем функцията Factorial във Visual Basic, за да изчислим факториела: