Rekursive Prozeduren 2-Loesung

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]


==Fakultät==

Schreiben Sie eine rekursive Prozedur <tt>fak</tt>, die eine Zahl n als Argument erwartet und deren Fakultät n! als Ergebnis liefert.

<code id="4ae713bf976a6">
(define fak
  (lambda (n)
    (if (= n 0)
      1
      (* n (fak (- n 1))))))</code>
<run id="4ae713bf9addf">(fak 5)</run>
<check>(and (= 1 (fak 0)) (= 120 (fak 5)))</check>

==Fibanocci==
Schreiben Sie eine rekursive Prozedur <tt>fib</tt>, die die n-te Fibonacci-Zahl als Ergebnis liefert.

'''Hinweis:''' Die n-te Fibonacci-Zahl ergibt sich aus der Summe ihrer beiden Vorgänger. Die 0-te und 1-te Fibonacci-Zahl ist jeweils 1.
<code id="4ae713bf97e05">
(define fib
  (lambda (n)
    (cond
     ((= n 0) 1)
     ((= n 1) 1)
     (else 
       (+ (fib (- n 1)) (fib (- n 2)))))))</code>
<run id="4ae713bf9b5b6">(fib 5)</run>


===Fibonacci-Liste===
Schreiben Sie eine rekursive Prozedur <tt>fibonacci_list</tt>, die eine Liste mit den ersten n Fibonaccizahlen zurückgibt. Beachten Sie, dass <tt>(fib 0)</tt> die erste Fibonacci-Zahl in der Liste liefert.

'''Hinweis:''' Verwenden Sie zur Lösung dieser Aufgabe Ihre Prozedur <tt>fib</tt> aus der vorherigen Aufgabe! <br/>
Sollte die entstehende Liste absteigend sortiert sein, so kann dies mittels <tt>reverse</tt> behoben werden.
<code id="4ae713bf985d6">
(define fibonacci_list
  (lambda (n)
    (if (< n 0)
      '()
      (cons (fib n) (fibonacci_list (- n 1))))))</code>
<run id="4ae713bf9bd97">(fibonacci_list 5)</run>

==Ascending List==
Schreiben Sie eine Prozedur <tt>ascending</tt>, die eine Liste nimmt und <tt>#t</tt> zurückgibt, falls die Listenelemente aufsteigend geordnet sind, ansonsten <tt>#f</tt>.

'''Hinweis:''' Beachten Sie das Resultat für die leere Liste <tt>’()</tt>.
                                       
'''Aufrufbeispiele:'''
{|
|-
|<tt>
 > (ascending '(1 2 4 7))
 #t
 > (ascending '(1 3 4 5 2 6))
 #f
 > (ascending '())
 #t
</tt>
|}
<code id="4ae713bf9957e">
(define ascending
  (lambda (ls)
    (if (< (length ls) 2)
      #t
      (and (< (car ls) (cadr ls))(ascending (cdr ls))))))
</code>
<run id="4ae713bf9c4f5">(ascending '(1 2 8 34 89 999))</run>
<check>
(and (ascending '()) (ascending '(1 5 7 9)) (not (ascending '(1 3 4 2 8))))
</check>

==Längenbestimmung==
===Listenlänge===
Schreiben Sie eine Prozedur <tt>my-length</tt>, die eine Liste als Argument nimmt und die Anzahl der Elemente in der 1. Ebene ausgibt. Die eingebaute Prozedur <tt>length</tt> darf dabei nicht verwendet werden!

Aufrufbeispiele:
{|
|-
|<tt>
 > (my-length ’(1 2 3 4 5))
 5
 > (my-length ’(1 2 3 4 5 (6 7) (8 (9 10 (11))))
 7
</tt>
|}
<code id="4ae713bf99e70">
(define my-length
  (lambda (ls)
    (cond
      ((null? ls) 0)
      (else 
        (+ 1 (my-length (cdr ls)))))))
</code>
<run id="4ae713bf9cc3a">(my-length '(1 2 (3 (4 5 6)) (7 2) 8))</run>
<check>(and (= (my-length '(1 2 4)) 3) (= (my-length '(1 (1 2) (2 3) 5)) 4) (= (my-length '()) 0))</check>

===Tiefenlänge===
Schreiben Sie eine weitere Prozedur <tt>deep-length</tt>, die ebenfalls eine Liste als Argument nimmt, jedoch die Anzahl ''aller'' Elemente in ''sämtlichen'' Teillisten ausgibt.

'''Hinweis''': Verwenden Sie Ihre Prozedur <tt>mylength</tt> und arbeiten Sie an deren Programmcode, um <tt>deep-length</tt> herzustellen.
                                                   
'''Aufrufbeispiele''':
{|
|<tt>
 > (deep-length ’(1 2 3 4 5))
 5
 > (deep-length ’(1 2 3 4 5 (6 7) (8 (9 10 (11))))
 11
</tt>
|}
<code id="4ae713bf9a617">
(define deep-length
  (lambda (ls)
    (cond
      ((null? ls) 0)
      ((list? (car ls)) (+ (deep-length (car ls))(deep-length (cdr ls))))
      (else 
        (+ 1 (deep-length (cdr ls)))))))
</code>
<run id="4ae713bf9d40e">(deep-length '(1 (2 3) (3 (5 7))))</run>
<check>(and (= (deep-length '()) 0) (= (deep-length '(1 2 3 4 5)) 5) (= (deep-length '(1 2 (3 4 (5 6)) 7 8)) 8))</check>

[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]