[Проблем] Рекурсия/ReCURS(E)ion


1
Здравейте, колеги. Нов съм в програмирането и на няколко пъти ми се наложи да се сблъскам с рекурсията. На теория я разбирам - имаш това, имаш онова, едното се изпълнява толкова пъти докато не стигне до едно състояние, после се връщаш назад от последното положение на маркера на изпълнение на програмта и тн. и тн. Проблема ми е, че като седна да решавам задачи, които се решават с рекурсия не мога да разбера откъде да тръгна! Също така не успявам изцяло да проследя една рекурсивна програма (дори и с дебъгера), което лично според мен доста спомага за разбирането й. От асистента си в уни знам, че трябва да "докарам" задачата до общ вид и просто да го имплементирам в конзолата. Е да, ама тук идва проблема - смущава ме много това връщане назад от маркера и ме обърква. С 2 думи казано - трябва ми extra tip за решаване на такива задачи, т.е. някой който е наясно и иска да помогне, да ми каже: правиш това, почваш така, проследяваш я (не я проследяваш, защото не ти е необходимо) , стигаш до общ вид на задачата (ами ако не е математическа формула някакъв extra tip за процедиране??) и тн.



Отговори



1
Смятам, че няма как да научиш рекурсия със заучаване на някаква теория. За да я разбереш си потърси конкретни примери. Разгледай няколко решени задачи и след това тествай сам да решиш нещо.
За предпочитане почни с нещо простичко, да хванеш как работи.

от krasi.nikolov (1412 точки)


0
Ами не, аз не искам да зауча някакъв метод ами по-скоро имам нужда от някакъв съвет - кое е добре, кое не и защо. Почнах с n! и ред на Фибоначи. Трудно ми е да си представя нещата - пишеш 1,2,3, а след като излезнат от стека са 3,2,1. Освен това и въпросния маркер от позицията на който се продължава след base case-а.

от rodi1i (237 точки)

0
Честно казано, никога не съм учил програмиране, а съм правил доста неща като практика. Затова и съм в академията, запълвам си разпокъсаните познания. А за рекурсия си трябва практика. :)

от krasi.nikolov (1412 точки)


1

Първо почни с най-елементарни решения/примери с рекурсия:

 

using System;
 
class Program
{
    static void print(int i) // това е рекурсивния метод
    {
        if (i < 0)
        {
            return;
        }
        Console.WriteLine(i);
        i--;
        print(i);
    }
 
 
    static void Main()
    {
        for (int i = 10; i >= 0; i--)
        {
            Console.WriteLine(i);
        }
        print(10); // с рекурсия
    }
}
 
И запомни това че е хубаво да си сигурен че рекурсията ти трябва да има край (да е контролирана).
 
Въпреки че тук: http://bg.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F е написано същото го прочети пак - трябва да се тръгне от някъде...

от stoyanov (2483 точки)


1

Когато  учих рекурсия за първи път се бях натъкнал на следния цитат: "За да разбереш рекурсията, трябва да разбереш рекурсията." smiley

 

"Също така не успявам изцяло да проследя една рекурсивна програма..." - няма и как да стане, освен ако нямаш повечко опит. Конкретно за рекурсията трябва практика, само с теория нищо не става.

А защо нещо трябва да е задължително с рекурсия? Все трябва да има и друго решение може би?


от Mitko_Mitev (1276 точки)


1
Хвани книгата на Преслав Наков и пренапиши всички примерни задачи на C#, те са написани на С в момента (за главата с рекурсии говорим), така хем ще имаш от каде да гледаш хем ще трябва и да пишеш нови неща, след това започни да си играеш и се опитай да решеш задачите които са дадени там. Там ще намериш още много задачи с рекурсии които ще ти дадат добри идеи.
Друго, в интернет има някои добри обяснения особенно на редицата на Фибоначи, кое как се пресмята в стека, дадено е доста нагледно и веднага става ясно какво става отзад. Това също ще ти помогне.
Успех,

от nikola76 (1250 точки)


1
Рекурсивно извикване на функция (метод в С шарп) имаш тогава, когато за да получиш н на брой резултати, всеки последващ път, когато извикваш функцията, на входа й подаваш резултатите от предишното повикване.
Т.е., ако след (к-1) - вото повикване си получил резултат (р)к-1, то при к-тото повикване на входа на функцията подаваш този същия резултат (р)к-1 и така, докато получиш необходимия брой резултати или необходимото число, както е при факториала.

от ellapt (6303 точки)


1

Погледни това линкче, има добро обяснение плюс примерчета: http://up-prakt.hit.bg/recursion_new.html


от nencho83 (538 точки)


1
И аз съвсем скоро гледах видеата на Телерик, посветени на рекурсията. Определено е сложна материя за съвсем начинаещи като мен и мога да кажа, че от задачите, които бяха демонстрирани, направо се пошашнах. Препоръчвам ти да ги изгледаш, все пак, както и да дръпнеш демотата към лекцията. В учебника също има примери. Във видеото на Наков той обяснява някои подробности и специфики относно дебъгването. Набляга се и върху идеята, че рекурсията изобщо трябва да се използва много внимателно и след добра спецификация на необходимия алгоритъм. Понеже си споменал Фибоначи, доколкото разбрах за тази задача в общия случай използването на рекурсия е неподходящо.
Всичко добро!

от Z_Petrov (829 точки)


1

Колега, ето едно страхотно визуализиране на това как работи рекурсията! лично на мен ми я избистри от първото гледане!

http://www.youtube.com/watch?v=lrCX8RBVqtU

тук е малко по-дълбоко:

http://en.wikipedia.org/wiki/Recursion

и разбира се:

http://www.introprogramming.info/intro-csharp-book/read-online/glava10-rekursiq/

прието е:

 

In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:

 (sequence A000045 in OEIS) 0,1,1,2,3,5,8,13...

като нулевият член = 0;

първият на 1 и т.н.

лесно ще проследиш този код и ще направиш аналог с видеото в тубата:

http://pastebin.com/WnkPrx49

или n3 = n2(n1+n0) + n1;

http://en.wikipedia.org/wiki/Fibonacci_number


от Dimov (907 точки)


1
http://www.youtube.com/watch?v=tWEV4AGuVis
На мен това видео ми помогна да разбера как да си определям дъното..в някои случаи....

от zhelyazkovn (2949 точки)