We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Recursion
  4. Functions and Fractals: Sierpinski triangles
  5. Discussions

Functions and Fractals: Sierpinski triangles

  • __alexey__
     + 0 comments

    This problem is about recursion and functional programming.

    Let's discover recursion pattern. The first figure:
    r = 1 (recursion level)
    h = 4 (hight of the figure) 

    ___1___
__111__
_1___1_
111_111

    The second figure:
    r = 2
    h = 8 

    _______1_______
______111______
_____1___1_____
____111_111____
___1_______1___
__111_____111__
_1___1___1___1_
111_111_111_111

    Each triangle with h=4 on the last picture has been submitted by the identical 3 other triangles with half hight (h'=h/2) and less level of recursion (r'=r-1) from the first picture.

    Thus, recursion function looks like 

    def figure(r: Int, h: Int): Array[String] ={
	if (r == 0 | h == 1) triangle(h) else create(figure(r-1, h/2), h/2)
}

    where 

    def triangle(h: Int): Array[String] = {
<returns Array with simple triangle like this 
___1___
__111__
_11111_
1111111
>
}

    and 

    def create(arr: Array[String], h: Int): Array[String] = {
		<arr is an input triangle. Function returns a figure, which was created from 3 triangles with hight=h and several other objects		
		>		
}

    The transpose(arr), rectangle(h), line(h) functions will help to solve this problem with no val or var :)