Важная информация
Показано с 1 по 4 из 4

Тема: Рекурсия и немного о стеке

  1. #1 Рекурсия и немного о стеке 
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    Сама по себе рекурсия в программировании - это способность процедуры или функции вызывать саму себя до достижения требуемого результата. Многие и в том числе я часто применяют рекурсию по причине: это удобно , просто и делает код коротким. Поскольку рекурсия целиком зависит от размеров стека, то отсюда вытекает ее главный минус: ограниченные ресурсы (или проще ограниченное кол-во рекурсивных вызовов и размер локальных переменных). Не знаю как обстоит дело в других языках программирования, но в FreeBasic есть возможность менять размер стека простым способом. Для этого надо при компиляции явно указать требуемый размер. Пример, который вызовет переполнение стека:

    Код :
    Dim iArray(2000000) As Integer

    Однако можно скомпилировать с ключом -t <размер стека в килобайтах, по умолчанию 1024>

    пример:

    fbc -s console -t 8192 example.bas
    При такой компиляции переполнения стека не будет, поскольку он увеличен в 8 раз.

    Где бы не было объяснение метода рекурсия, почти везде идет пример фракталов. И здесь я тоже приведу этот пример, но на языке FreeBasic:



    Код :
    Dim Shared As integer x=320,y=240,n,r=40
    Dim Shared As single k1=.3 , k2=3
     
    #Ifndef PI
    #define PI 3.14159265358979323846
    #EndIf
     
    Screen 18
     
    Sub p(x As Integer ,y As Integer ,r As Integer ,r1 As Integer ,n As Integer )
        Dim As integer x1,y1,i
        if n>0 Then
            color 15-n
            circle (x,y),r
            r1 = IIf (Frac(r*k2)>0.5,r*k2+1,r*k2)
            for i = 1 to 4
                x1= IIf (Frac(x+r1*cos(pi/2*i))>0.5,x+r1*cos(pi/2*i)+1,x+r1*cos(pi/2*i))
                y1=IIf (Frac(y+r1*sin(pi/2*i))>0.5,y+r1*sin(pi/2*i)+1,y+r1*sin(pi/2*i))
                p(x1,y1,IIf (Frac(r*k1)>0.5,r*k1+1,r*k1),r1,n-1)
            Next
        EndIf
    End Sub
     
    Input "n =",n
    p(x,y,r,0,n)
    Sleep
    Ответить с цитированием  
     

  2. Пользователь сказал cпасибо:

    >Quiet Snow< (10.01.2013)

  3. #2  
    Супер модератор Аватар для >Quiet Snow<
    Регистрация
    11.04.2011
    Адрес
    Планета земля
    Сообщений
    3,846
    Сказал(а) спасибо
    1,815
    Поблагодарили 945 раз(а) в 807 сообщениях
    Записей в блоге
    1
    Рекурсия - мощный инструмент в программировании. Я так и не научился ей пользоваться
    уверенно, хотя принцип знаю давно.
    Стараюсь проектировать проги без рекурсии там, где это возможно. Тут многое упирается
    в возможности языка, если язык кишит динамическими структурами, то можно и вообще
    без рекурсии. Но я пока слабо ориентируюсь в FB, поэтому не знаю насколько хорошо
    развит данный функционал(имеется в виду безо всяких указателей).
    Обучение прикладному программированию(по skype), качественно, недорого, 18+, вопросы в личку.
    «Если вы ничего не сделаете, я уверяю вас, ничего и не произойдёт» © Жак Фреско
    Ограниченно модерирую.
    Ответить с цитированием  
     

  4. Пользователь сказал cпасибо:

    stabud (07.01.2013)

  5. #3  
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    Цитата Сообщение от >Quiet Snow< Посмотреть сообщение
    Стараюсь проектировать проги без рекурсии там, где это возможно.
    Это да, кому как нравится.

    Вот еще 2 примера с рекурсией, идеи и реализация взяты с примеров, написанных на борландском паскале:

    [Ссылки могут видеть только зарегистрированные пользователи. ]

    Код :
    Dim As Integer n,w=800,h=600
     
    ScreenRes w,h
     
    Sub BOX(x As Integer,y As Integer,n As Integer,size As Short)
    	dim s As Short
    	if n-1>0 Then
    		s = size \ 2
    		BOX(x-size, y+size,n-1,s)
    		BOX(x-size, y-size,n-1,s)
    		BOX(x+size, y+size,n-1,s)
    		BOX(x+size, y-size,n-1,s)
    	EndIf
    	Line(x-size, y-size)-(x+size, y+size),,BF
    	Line(x-size+1, y-size+1) - (x+size-1, y+size-1),Rnd*13+1,BF
    End Sub
     
     
    start: Input "n =",n
    if n>5 And n<1 then GoTo start
    color 15
    BOX(w \ 2, h \ 2 , n , h \ 4)
    Sleep

    [Ссылки могут видеть только зарегистрированные пользователи. ]

    Код :
    Dim Shared As Integer x=200,y=100,p=6,n=3
    Dim Shared As Single t=.25,l=50
     
    #Ifndef PI
    #define PI 3.14159265358979323846
    #EndIf
     
    ScreenRes x*2,y*2
     
    Sub snow(x As Integer ,y As Integer ,k As Integer,l As Single)
    	Dim As Integer x1,y1
    	If k=0 Then Exit Sub
    	For i As Integer = 1 To p
    		x1=Int(x+l*Cos(2*pi*(i-1)/p))
    		y1=Int(y+l*Sin(2*pi*(i-1)/p))
    		Line(x,y)-(x1,y1)
    		snow(x1,y1,k-1,l*t)
    	Next
    End Sub
     
    snow(x,y,n,l)
    Sleep
    Ответить с цитированием  
     

  6. Пользователь сказал cпасибо:

    >Quiet Snow< (10.01.2013)

  7. #4  
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    И еще один пример с треугольниками.

    [Ссылки могут видеть только зарегистрированные пользователи. ]

    Код :
    Dim As Integer x1=320,y1,x2=639,y2=479,x3,y3=479,n
    ScreenRes 640, 480
     
    Sub TRI(x1 As Integer,y1 As Integer,x2 As Integer,_
    			y2 As Integer,x3 As Integer,y3 As Integer, N As Integer)
     
    	Dim As Integer x12,y12,x23,y23,x31,y31
    	If N=0 Then Exit Sub
    	x12=(x1+x2) \ 2 : y12=(y1+y2) \ 2
    	x23=(x2+x3) \ 2 : y23=(y2+y3) \ 2
    	x31=(x3+x1) \ 2 : y31=(y3+y1) \ 2
    	Color 15-n
    	PSet (x31,y31)
    	Line -(x12,y12)
    	Line -(x23,y23)
    	Line -(x31,y31)
     
    	TRI(x1,y1,x12,y12,x31,y31, N-1)
    	TRI(x2,y2,x12,y12,x23,y23, N-1)
    	TRI(x3,y3,x31,y31,x23,y23, N-1)
     
    End Sub
     
    Input "n =",n
    PSet (x1,y1)
    Line - (x2,y2)
    Line - (x3,y3)
    Line - (x1,y1)
    TRI(x1,y1,x2,y2,x3,y3, n)
    Sleep
    Ответить с цитированием  
     

  8. Пользователь сказал cпасибо:

    >Quiet Snow< (10.01.2013)

Информация о теме
Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права
  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •