За последние 24 часа нас посетили 19508 программистов и 1610 роботов. Сейчас ищут 938 программистов ...

Рекурсия

Тема в разделе "PHP для новичков", создана пользователем Sinevik, 24 мар 2017.

  1. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    PHP:
    1. function fib($num)
    2. {
    3.     if ($num < 2) {
    4.         return $num;
    5.     }
    6.     return fib($num - 1) + fib($num - 2);
    7. }
    8. echo fib(4);
    Формула вычисления числа Фибоначчи по его порядковому номеру.
    Если этот скрипт разложить для понимания, то получится вот такая схема
    fib(4)
    fib(3) + fib(2)
    fib(2) + fib(1) + fib(1) + fib(0)
    fib(1) + fib(1) + fib(1) + fib(0)

    Объясните пожалуйста, почему если изменить данный скрипт вот так вот, то возвращает он значение 14.
    Код (Text):
    1. <?php
    2. function fib($num)
    3. {
    4.     if ($num < 2) {
    5.         return $num;
    6.     }
    7.     return $num + fib($num - 1) + fib($num - 2);
    8. }
    9. echo fib(4);
    10.  
    11. ?>
    return $num + fib($num - 1) + fib($num - 2);
     
  2. askanim

    askanim Старожил

    С нами с:
    7 апр 2016
    Сообщения:
    2.201
    Симпатии:
    166
    Адрес:
    GABRIEL
    @Sinevik Потому что возьми отследи дебагером, если самому логику построить сложно
     
  3. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Что это значит?
     
  4. denis01

    denis01 Суперстар
    Команда форума Модератор

    С нами с:
    9 дек 2014
    Сообщения:
    12.227
    Симпатии:
    1.714
    Адрес:
    Молдова, г.Кишинёв
  5. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Ох. Это займёт наверно кучу времени, а мне бы сейчас с рекурсией разобраться. У меня курсы в интернете оплачены. Я потратил 2 дня на то что бы у меня wampserver заработал на винде, качал устанавливал тут всё что мог
     
  6. alexblack

    alexblack Старожил

    С нами с:
    20 янв 2016
    Сообщения:
    640
    Симпатии:
    381
    Ну если вкратце,на каждом уровне глубины рекурсии,где if дает false у тебя в return $num прибавляется к результату fib($num - 1) + fib($num - 2);
    Отсюда и получается 14.Что бы тебе проще было,возьми число 3 например и прогони по твоей функции его либо на листочке,либо в уме.
     
  7. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Нифига не понимаю почему тут 14, получается всё что угодно но только не 14. Короче ладно тогда, фиг с ним
     
  8. askanim

    askanim Старожил

    С нами с:
    7 апр 2016
    Сообщения:
    2.201
    Симпатии:
    166
    Адрес:
    GABRIEL
    @Sinevik Так красавица не паникуй. У нас рекурсию всего то в 5 ом классе средней школы проходят. Слушай внимательно объясню что такое рекурсия - это когда объект является частью самого себя(Это математически). А что же касается программирования то тут это выглядит так:
    PHP:
    1. function a($a) {
    2.         $a = $a +1; // Тут мы плюсуем 1 к нашему значению передаваемому в функции
    3.         // напишем условие входа в рекурсию
    4.        
    5.         if(a < 3) {
    6.             // И вот ключевой момент нашей операции ниндзя
    7.             // Готов?
    8.             // и ?
    9.             // ТАДАДАМ!!!!!!!!!
    10.             a($a); // Вызываем рекурсию при помощи вызова функции a(), а то есть вызова самой себя.
    11.          
    12.         }
    13.         // И наконец-то выход из рекурсии
    14.         return a;
    15.  
    16.     }
    Ну надеюсь красавица ты понял что такое рекурсия.
    И закрепим в двух словах.
    Рекурсия в программировании - Это вызов функции которая вызывает себя же.
     
  9. mahmuzar

    mahmuzar Старожил

    С нами с:
    6 апр 2012
    Сообщения:
    4.631
    Симпатии:
    425
    Адрес:
    РД, г. Махачкала.
    Эм, мне казалось @Sinevik - это парень.
     
  10. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Ну так я это понял. Я же разложил Фибоначчи уже в вопросе
    --- Добавлено ---
    Так и есть) просто некоторые люди любят повыпендриваться перед новичками. Я обычно не обращаю внимания.
     
    Fell-x27 нравится это.
  11. TeslaFeo

    TeslaFeo Старожил

    С нами с:
    9 мар 2016
    Сообщения:
    2.984
    Симпатии:
    759
    это да
    --- Добавлено ---
    только что хотел попытался объяснить это. Для этого нужно с начала объяснить себе.
    Начал объяснять себе и понял, что себе я это буду объяснять очень долго, а потом еще дольше тебе. Короче лучше сам)

    Очень закручено там всё получается.
     
    Sinevik нравится это.
  12. alexblack

    alexblack Старожил

    С нами с:
    20 янв 2016
    Сообщения:
    640
    Симпатии:
    381
    На самом деле c var_dump() можно упростить понимание,посмотрев некоторые промежуточные результаты:
    PHP:
    1. function fib($num)
    2. {
    3.     if ($num < 2) {
    4.         return $num;
    5.     }
    6.     var_dump($val = $num + fib($num - 1) + fib($num - 2));
    7.     return $val;
    8. }
    9. fib(4);
    Код (Text):
    1. int(3)
    2. int(7)
    3. int(3)
    4. int(14)
     
    TeslaFeo и Sinevik нравится это.
  13. askanim

    askanim Старожил

    С нами с:
    7 апр 2016
    Сообщения:
    2.201
    Симпатии:
    166
    Адрес:
    GABRIEL
    @Sinevik
    Слушай принцесса, . Если ты такой умный тогда почему ты не мог сделать вот так:
    PHP:
    1. $i = 0; // Кол-во наших итераций
    2. function fib($num, $i)
    3. {
    4.     $i++;
    5.     $str= '';
    6.     for($b=0;$b<$i;$b++) {
    7.         $str .= '_';
    8.     }
    9.     echo '<br><br> '.$str.$i.' : '.$num;
    10.     if ($num < 2) {
    11.         return $num;
    12.     }
    13.  
    14.     $res =  $num + fib($num - 1, $i) + fib($num - 2, $i);
    15.  
    16.  
    17.  
    18.     return $res;
    19. }
    20. echo '<br><br>'.fib(4);
    Рекурсия - это банальная математика 5 класса, а то что у тебя происходит это рекурсия плюс геометрическая прогрессия ну её проходят в 6 ом классе.
    И посмотреть на экран монитора и разложить всё по полочкам ?
    Тебе нужны не не обращать внимание а слушать и пытаться хоть чему нибудь научиться когда тебе говорят.
     
    #13 askanim, 24 мар 2017
    Последнее редактирование: 24 мар 2017
  14. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Боже, какой ты крутой))))) ну супер супер. Этот парень неимоверно КРУТ, запомните все.
     
    Fell-x27 нравится это.
  15. mkramer

    mkramer Суперстар
    Команда форума Модератор

    С нами с:
    20 июн 2012
    Сообщения:
    8.600
    Симпатии:
    1.764
    Потому что num на каждом уровне рекурсии прибавляется. Вообще, любимый пример всех времён и народов - числа Фибоначчи, это самое неудачное использование рекурсии (потому что одни и те же числа Фибоначчи вычисляются хренову тучу раз). Все объясняют рекурсию на Фибоначчи, поскольку там изначальная формула рекуррентная. Но вычислять его так в какой-нибудь проге, где реально нужны числа Фибоначчи - напрашиваться на неприятности. Об этом хорошо у Н. Вирта написано в "Алгоритмы + структуры данных=программы" (кстати, обязательно читать, хотя там примеры все на Pascal. При своей простоте даёт понимание процесса).
     
    askanim и Sinevik нравится это.
  16. askanim

    askanim Старожил

    С нами с:
    7 апр 2016
    Сообщения:
    2.201
    Симпатии:
    166
    Адрес:
    GABRIEL
    да в отличии от тебя я могу посчитать геометрическую прогрессию. Тебе сразу сказали дебгни . А ты что сделал, ты поплакался в платочек и сдался. Вместо того чтобы напрячь свои извилины хотя бы на чуть чуть, если ты будешь в программировании сдаваться перед каждой такой задачей, ты никогда не станешь программистом, можешь сразу закрыть курс свой и пойти заняться чем нибудь другим.
    --- Добавлено ---
    @mkramer да он до сих пор не понимает что такое рекурсия и прогрессия
     
  17. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Вот это круто та

    Я шокирован как этот Лемур
     
  18. askanim

    askanim Старожил

    С нами с:
    7 апр 2016
    Сообщения:
    2.201
    Симпатии:
    166
    Адрес:
    GABRIEL
    @Sinevik Шансы что ты будешь нормальным прогером ну очень малы, примерно 0,00001% :3 Без шуток. Лучше отложи курс в сторону и попробуй себя в другом направлении.
     
  19. HeavyLady

    HeavyLady Новичок

    С нами с:
    7 дек 2016
    Сообщения:
    11
    Симпатии:
    4
    Что за говнярьство-то началось?
     
    askanim нравится это.
  20. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Одну секундочку, сейчас возьму ручку и блокнот и запишу пару ваших советов.
     
  21. askanim

    askanim Старожил

    С нами с:
    7 апр 2016
    Сообщения:
    2.201
    Симпатии:
    166
    Адрес:
    GABRIEL
    @Sinevik лучше пивка пойди выпей, расслабься.
     
  22. Sinevik

    Sinevik Новичок

    С нами с:
    7 фев 2017
    Сообщения:
    83
    Симпатии:
    4
    Так записано как второй пункт, что 3 идёт?))))))))))
     
  23. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.156
    Симпатии:
    1.771
    Адрес:
    :сердА
    @askanim подуспокойся уже.
    --- Добавлено ---
    @Sinevik дебаггинг это не долго. Ты в чем работаешь? Ставлю, что в блокноте. Если так, то зря. Тебе нужна нормальная IDE, к ней можно подключить дебаггер. Гайдов - полный интернет. Справится даже новичок. Я всем советую IDE phpStorm, она шикарная.

    Далее - при дебаге ты можешь буквально поставить приложение на паузу посреди его работы, заглянуть внутрь и отследить прям прям пошагово, что там, куда, как, откуда, заглянуть в каждую переменную, проверить каждое условие, все как под микроскопом. Это очень помогает в поиске ошибок и в исправлении/понимании логики кода.

    Займись этим делом - глаза боятся, руки делают. Там ничего сложного нет.
    --- Добавлено ---
    +1. Куда логичнее объяснять рекурсию на примерах типа сборки деревьев, где прям вот очевидно, на кой черт она нужна и как работает.
     
    denis01 и mahmuzar нравится это.
  24. mahmuzar

    mahmuzar Старожил

    С нами с:
    6 апр 2012
    Сообщения:
    4.631
    Симпатии:
    425
    Адрес:
    РД, г. Махачкала.
    За-то как звучит!))
     
  25. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.156
    Симпатии:
    1.771
    Адрес:
    :сердА
    Ну даже с практической точки зрения - числа Фибоначчи считать лично мне вот так ни разу и не пришлось. А с древовидными структурами работать - постоянно.
     
    Sinevik нравится это.