-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrecurs.tex
128 lines (115 loc) · 3.06 KB
/
recurs.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
% !TEX encoding = IsoLatin9
\section{Fonctions récursives}
\begin{frame}
\begin{columns}
\column{4.8cm}
\tableofcontents[currentsection,hideothersubsections]
\column{7cm}
\centering{
\includegraphics[width=4cm]{fig/deutsch.jpg}
\textit{``To iterate is human, to recurse divine''}\\
\small{
\hfill L. Peter Deutsch (1946-)\\
\hfill auteur de Ghostscript}
}
\end{columns}
\end{frame}
\begin{frame}[fragile]
\frametitle{Fonction récursive}
\begin{block}{}
Un algorithme récursif est un algorithme qui, lors
de son exécution, s'appelle lui-même.
\end{block}
\begin{exampleblock}{Algorithme factorielle}
\begin{algorithmic}[0]
\REQUIRE{n (entier)}\\
\ENSURE{nfact (entier)}\\
\IF {$n=0$}
\RETURN{1}
\ELSE
\RETURN {$n\times$factorielle$(n-1)$}
\ENDIF
\end{algorithmic}
\end{exampleblock}
Le langage C permet la récursivité avec les fonctions :
\begin{codeblock}{}
\vspace{-.3cm}
\lstset{escapeinside={§§}}
\lstset{basicstyle=\scriptsize}
\begin{codeC}
int fact (int n) {
if (n==0) return (1) ;
else return(n * fact (n-1));
}
\end{codeC}
\vspace{-.3cm}
\end{codeblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Contexte d'exécution}
\begin{block}{}
Chaque appel à la fonction crée son propre contexte d'exécution
(peut être gourmand en mémoire).
\end{block}
\begin{columns}
\column{0.5\textwidth}
\begin{codeblock}{}
\vspace{-.3cm}
\lstset{escapeinside={§§}}
\lstset{basicstyle=\scriptsize}
\begin{codeC}
int fact (int n) {
if (n==0) return (1) ;
else return(n * fact (n-1));
}
int main() {
int z ;
z = fact(4);
}
\end{codeC}
\vspace{-.3cm}
\end{codeblock}
\column{0.4\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[
auto,
node distance=1cm,
]
\node (main) {main} ;
\node (f1) [below of = main] {fact} ;
\node (f2) [below of = f1] {fact} ;
\node (f3) [below of = f2] {fact} ;
\node (f4) [below of = f3] {fact} ;
\node (f5) [below of = f4] {fact} ;
\draw[->,thick] (main.220) -- node [midway, left] {4} (f1.140);
\draw[->,thick] (f1.220) -- node [midway, left] {3} (f2.140);
\draw[->,thick] (f2.220) -- node [midway, left] {2} (f3.140);
\draw[->,thick] (f3.220) -- node [midway, left] {1} (f4.140);
\draw[->,thick] (f4.220) -- node [midway, left] {0} (f5.140);
\draw[->,thick] (f5.40) -- node [midway, right] {1} (f4.320);
\draw[->,thick] (f4.40) -- node [midway, right] {1} (f3.320);
\draw[->,thick] (f3.40) -- node [midway, right] {2} (f2.320);
\draw[->,thick] (f2.40) -- node [midway, right] {6} (f1.320);
\draw[->,thick] (f1.40) -- node [midway, right] {24} (main.320);
\end{tikzpicture}
\end{figure}
\end{columns}
\end{frame}
\begin{frame}
\frametitle{Fonctions récursives}
\begin{block}{}
Selon les problème traités, la récursivité permet
d'obtenir un code source succinct.
\end{block}
Par contre, quand elle est mal réalisée :
\begin{itemize}
\item Le code peut tourner sans fin ;
\item La mémoire utilisée peut être énorme (à cause de
la multiplication des contextes d'exécution);
\item Cela peut ralentir l'exécution du programme.
\end{itemize}
\begin{alertblock}{}
A utiliser avec précaution.
\end{alertblock}
\end{frame}