\documentclass[leqno]{schuleab}
\usepackage[utf8]{inputenc}
\usepackage{schulinf}

% Dieses Dokument ist in der Zusammenarbeit von Informatikreferendaren und
% ehemaligen Informatikreferendaren der Studienseminare (heute ZfsL) Arnsberg,
% Hamm und Solingen entstanden.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% http://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% http://ddi.uni-wuppertal.de/material/materialsammlung/
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter  http://www.ctan.org/pkg/schule
% zur Verfügung.

\usepackage[pdfauthor={Referendare der Informatikfachseminare Arnsberg, Hamm und Solingen}]{hyperref}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\svnid{$Id: ab_01_rekursion.tex 626 2014-05-22 21:36:50Z pieper $}

\dokName{Rekursion}
\jahrgang{Q1}

\begin{document}
\section*{Rekursion}

Rekursion ist eine besondere Art, um Funktionen zu definieren, Programme zu schreiben und Probleme zu lösen. Schreiben Sie auf, was Sie unter dem Begriff Rekursion verstehen und wie sich diese beschreiben lässt. 

\subsection*{Rekursive Definitionen}
Gegeben sind die folgende drei mathematischen Definitionen für positive ganze Zahlen. Bearbeiten Sie dazu die unten folgenden Aufgaben.

\begin{equation}
	f(x) = \left\{
		\begin{array}{ll}
			x + f(x-1) & \textrm{für } x \ge 2\\
			1 & \textrm{für } x = 1\\
			0 & \textrm{für } x = 0\\
		\end{array} \right.
\end{equation}
\begin{equation}
	g(x,y) = \left\{
		\begin{array}{ll}
			x + g(x, y-1) & \textrm{für } y \ge 1\\
			0 & \textrm{für } y = 0\\
		\end{array} \right.
\end{equation}
\begin{equation}
	h(x,y) = \left\{
		\begin{array}{ll}
			x * h(x, y-1) & \textrm{für } y \ge 2\\
			x & \textrm{für } y \le 1\\
		\end{array} \right.
\end{equation}

\begin{smallenumerate}
	\item Schreiben Sie die einzelnen Rechenschritte auf, die bei einer konkreten Rechnung durchgeführt werden. Wählen Sie dazu verschiedene Zahlen im Bereich zwischen 0 und 10.
	\item Geben Sie an, welche Rechenoperation sich hinter der rekursiven Definition verbirgt.
\end{smallenumerate}

\subsection*{Rekursive Problemlösung}

Die beiden folgenden Probleme zeichnen sich dadurch aus, dass es für sie sehr einfache Lösungsansätze gibt, die mit Rekursion arbeiten. Erarbeiten Sie erst die beiden Lösungsansätze und halten diese schriftlich fest, bevor Sie sich den beiden speziellen Aufgaben zu den Problemen widmen.

\subsubsection*{Stufenproblem}
\begin{wrapfigure}[7]{r}{4.5cm}
	\begin{center}
		\vspace{-1cm}
		\input{treppenproblem.cir}
	\end{center}
\end{wrapfigure}
Bei einer normalen Treppe kann man mit einem Schritt eine Stufe oder auch zwei Stufen hochgehen. Bei einer Treppe aus drei Stufen ergeben sich so drei Möglichkeiten, wie man diese Treppe hochgehen kann: Drei Mal eine Stufe, erst eine und dann zwei Stufen und erst zwei Stufen und dann eine. Wie viele Möglichkeiten gibt es bei einer Treppe mit 4, 5 bzw. n Stufen?

Schreiben Sie Ihren Lösungsansatz für die Anzahl der Möglichkeiten in einer Mathematischen Definition auf.

\subsubsection*{Türme von Hanoi}
Ein Turm besteht aus mehreren Scheiben unterschiedlicher Größe. Diese Scheiben sind der Größe nach geordnet auf einen Stab gesteckt, so dass die Größte unten liegt. Die Aufgabe besteht darin, den Turm auf einen anderen Stab um zu lagern, in dem immer nur eine Scheibe gleichzeitig bewegt wird. Dabei steht nur ein weiterer Stab zur Hilfe zur Verfügung. Weiterhin muss beachtet werden, dass immer nur eine kleinere Scheibe auf einer größeren Scheibe liegt und nicht umgekehrt.

\begin{center}
	\input{tuerme_von_hanoi.cir}
\end{center}

Überführen Sie Ihren Lösungsansatz in ein Ablaufdiagramm.

\subsection*{Reflexion}
In der ersten Aufgabe sollten Sie ihr Verständnis des Begriffs Rekursion aufschreiben. Tun Sie dieses erneut und vergleichen Sie dieses mit dem Verständnis zu Beginn des Arbeitsblatts.

\newpage

\section*{Hilfen}

\minisec{Definition 1:}
\[ f(4) = 4 + f(3) = 4 + 3 + f(2) = \ldots \]

\vfill

\minisec{Definition 2:}
\[ g (3,6) = 3 + g(3,5) = 3 + 3 + g(3,4) = \ldots \]

\vfill

\minisec{Stufenproblem}
Geht man zu Beginn nur eine der n Stufen hoch, so hat man nur noch n-1 Stufen incl. deren Möglichkeiten vor sich. Geht man stattdessen zwei Stufen hoch, so hat man nur noch n-2 Stufen incl. deren Möglichkeiten vor sich.

\vfill

\minisec{Türme von Hanoi}
Versuche zuerst einen Turm aus einer Scheibe umzulegen, fahre dann fort mit zwei und drei Scheiben. Schaue dir dabei an, ob du bei drei Scheiben auch Schrittfolgen nutzt, die du bei zwei Scheiben genutzt hast.



\end{document}
