====== Rekursion ======

to be written
  * Fakultät rekursiv (schon bei Funktionen)
  * divide et impera / divide and conquer / teile und herrsche

[[https://de.wikipedia.org/wiki/Rekursion#Rekursive_Grafiken|Wikipedia Rekursion]] 
Sierpinski rekursiv ist schon gut, eventuell turtle Grafik, Bilder von Wikipedia?

Hanoi?

<WRAP round todo>
[[https://de.wikipedia.org/wiki/Cantor-Menge|Cantor-Menge]] im Textmodus:
<code python>
def cantor(x):
    if x == 0:
        return "*"
    else:
        s = cantor(x - 1)
        return s + (3**(x-1)) * "-" + s

for i in range(5):
    print(cantor(i))
</code>
</WRAP>

<WRAP round todo>
<code python>
from gpanel import *

def zeichne(x, y, l, xr, yr, rekursionstiefe):
    if rekursionstiefe == 0:
        line(x, y, x + l * xr, y + l * yr)
    else:
        xl = -yr
        yl = xr    
        
        zeichne(x, y, l/3, xr, yr, rekursionstiefe - 1)
        zeichne(x + 2*l/3 * xr, y + 2*l/3 * yr, l/3, xr, yr, rekursionstiefe - 1)
        zeichne(x + l/3 * xr, y + l/3 * yr, l/3, xl, yl, rekursionstiefe - 1)
        zeichne(x + l/3 * (xr + xl), y + l/3 * (yr + yl), l/3, xr, yr, rekursionstiefe - 1)
        zeichne(x + l/3 * (2 * xr + xl), y + l/3 * (2 * yr + yl), l/3, -xl, -yl, rekursionstiefe - 1)
    
makeGPanel(Size(1000, 1000))
window(-10, 1010, -10, 1010)
title("Key 'Esc': escape")

zeichne (0,0, 1000, 1, 0, 6)    
</code>
</WRAP>


<WRAP round todo>
Das folgende Programm findet alle magischen 3x3-Quadrate durch stupides Ausprobieren.

Die am Ende ausgegebene Zahl ist die Fakultät welcher Zahl?

Wenn man die Variable n auf den Wert 4 endet, braucht das Programm sehr lange - grob überschlagen auf meinem Rechner 3 Jahre!

Wer kann das Programm verbessern? 
<code python>
# Erzeuge magisches Quadrat
import time

n = 3

def magisch():
    for x in range(0,n):
        zeilensumme = 0
        spaltensumme = 0
        for y in range(0,n):
            spaltensumme = spaltensumme + a[x][y]
            zeilensumme = zeilensumme + a[y][x]
        if zeilensumme != summe or spaltensumme != summe:
            return False

    erste_diagonalsumme = 0   
    zweite_diagonalsumme = 0   
    for x in range(0,n):
        erste_diagonalsumme = erste_diagonalsumme + a[x][x]
        zweite_diagonalsumme = zweite_diagonalsumme + a[x][n - 1 - x]
    if erste_diagonalsumme != summe or zweite_diagonalsumme != summe:
        return False
    return True

def trage_ein(e):
    global anzahl
    for x in range(0, n):
        for y in range(0, n):
            if a[x][y] == 0:
                a[x][y] = e
                if e > 1:
                    trage_ein(e - 1)
                else:
                    anzahl = anzahl + 1
                    if anzahl % 100000 == 0:
                        print(anzahl)
                        print(time.clock() - startzeit)

                    if magisch():
                        print(a)
                a[x][y] = 0

a = [[0 for y in range(0,n)] for x in range(0,n)]
anzahl = 0
summe = n * (n * n + 1) // 2
startzeit = time.clock()
trage_ein(n * n)
print(anzahl)
print(time.clock() - startzeit)
</code>
</WRAP>

===== Link zur Kursseite =====

[[lehrkraefte:snr:informatik:glf21|Zur Kursseite]]