Fonction récursive (Triangle de Pascal)

[VDH-Bruno]

Bonjour,

 

Voilà je bute toujours sur le même problème pour résumer :

 

Faire des fonctions récursive simple du type (fonc (-1 nbr)) ou (fonc (cdr lst)), c’est Ok

Faire des fonctions récursive multiple du type (append (fonc (car lst)) (fonc (cdr lst))), c’est Ok

 

Par contre si c’est pour des fonctions récursives imbriqué (type fonction combi3 de (gile)), c’est laborieux bien souvent je contourne le problème avec l’introduction d’une variable (Cf chalenge 33) ou l’utilisation de mapcar si c'est possible.

 

Je n'arrive pas à formuler clairement un raisonnement impliquant l’imbrication de fonction récursif (problème d’algoritmie et de méthode sans doute).

 

Pour illustrer mon problème je me propose de vous montrer mon code pour renvoyer le développement de la ligne du triangle de pascal suivant un indice n.

 

Triangle de Pascal (rappel)

n=0      (1)
n=1      (1 1)
n=2      (1 2 1)
n=3      (1 3 3 1)
n=4      (1 4 6 4 1)
ect..

 

Tentative d’écriture de l’agorithme (certainement maldroite, je débute également en la matière..)

 

L’exécution prend fin pour n=0 et renvoi la liste 1 (condition d’arret)

Passage de n à n+1 (sub 1)
  Ajouter élément 1 en début et fin de liste

  Si la liste à un second terme (n>0)

  Calcule les coefficients intérieur (sub 2)
       Prendre le premier terme de la liste n puis lui ajouter le second etc
       jusqu'à la ce qu’il n’y est plus de second terme. (condition d’arret)

 

 

Mon code factorisé pour plus de lisibilité

(defun TPascal (n / sub1 sub2)

 (defun sub2 (lst)
   (mapcar '(lambda (x y) (+ x y)) lst (cdr lst))
 )

 (defun sub1 (n)
   (cond
     ((= 1 n) '(1 1))                                 ; n = 1
     (T (append '(1) (sub2 (sub1 (1- n))) '(1))) ; n+1
   )
 )

 (if (zerop n)
   '(1)                                       ; n = 0
   (sub1 n)
 )

)

 

(TPascal 3) ; retourne (1 3 3 1) Ok

 

Le code fonctionne bien, il est même bien écrit (je pense) mais encore une fois j’ai contourné mes difficultés dans l’écriture de sub2 (que je voulais coder récursivement).

 

Ce qui m’a obligé à adapter mon algorithme en posant la condition d’arrêt dans sub1 à n=1, pour avoir une valeur de retour acceptable pour sub2.

 

Mes questions :

Comment formuler sub2 de façon récursive.. (de façon fonctionnel) ?

Y a-t-il un défaut dans mon raisonnement, si oui lequel (je serai heureux de le comprendre).

 

En espérant ne pas être trop confus, merci.

 

(Ps : Par la suite je pense m’intéresser à la symétrie axiale du triangle pour éventuellement optimiser sa construction, et également mémoriser tous les appels de 0 à n)

[VDH-Bruno]

Bonsoir,

 

Je développe un peu, pour que vous puissiez comprendre un peu mieux, ce à quoi je m’exerce :

 

L’intérêt éventuelle d’une telle fonction (triangle de pascal) outre le développement des identités remarquables, c’est de renvoyer le nombre de combinaison simple en utilisant la méthode graphique des coefficients binomiaux (et vice versa).

 

Application

Calcule du nombre de combinaison (nCp) simple de p élément choisis parmi n. (rappel : p et n sont les coefficients binomiaux).

 

Pour une liste ‘(A B C D E F G H) on veut connaître le nombre de combinaison simple de 4 éléments distincts.

 

Par la formule mathématique : nCp = n! / (p! (n-p)!)

(note on peut certainement faire mieux en triturant le code de façon à fusionner les fonctions fact & nCp, pour ne pas calculer 3 fois la factorielle, mais seulement les opérations complémentaires).

 

Code :

 (defun fact (n)
 (if (zerop n)
   1
   (* n (fact (1- n)))
 ) 
)

(defun nCp (n p)
 (if (< n p)
   nil
   (/ (fact n) (* (fact (- n p)) (fact p)))
 )
)

 

(nCp (length '(A B C D E F G H)) 4); retourne 70

(nCp (length '(A B C D E F G H)) 20); retourne nil

 

 

Par la méthode graphique des coefficients binomiaux.

(Notez que dans ce cas il n’est même pas judicieux d’écrire une fonction nth suffi)

 

Code

 (defun nCp (n p)
 (nth p (TPascal n))
)

 

(nCp (length '(A B C D E F G H)) 4); retourne 70

(nCp (length '(A B C D E F G H)) 20); retourne nil

 

 

Explication de mon intérêt à maîtriser les appels de fonctions récursives imbriqués

Actuellement je travaille pour mes besoins à combler mes lacunes en mathématique (essentiellement dans le domaine du dénombrement, pour le moment..) et par la même j’essaye de m’initier à l’algorithmie (autre point faible)

 

Pour crever l’abcès une bonne fois pour toutes, j’ai entrepris depuis quelques jours d’écrire une petite bibliothèque de routines (que je publierais surement) portant sur les problèmes de permutations, d’arrangement et de combinaisons de listes (version simples et à répétitions).

 

Cerise sur le gâteaux, j’ai entrepris de tout programmer de façon fonctionnel.. histoire de consolider mes connaissances et d’acquérir de l’aisance.

 

D’où l’intérêt pour moi de maîtriser ce type de structure.. , que je retrouve systématiquement (suffit de voir les fonctions combi de (gile) pour s’en convaincre).

 

(Ps : Depuis mon immersion dans le dénombre et la combinatoire, je ne pense plus avoir de problème pour ranger mes chaussettes dans un tiroir, ni pour répartir des grenouilles dans des étangs.. :casstet: merci aux matheux et à leurs exemples.. :exclam: )

[(gile)]

Salut,

 

Comment formuler sub2 de façon récursive.. (de façon fonctionnel) ?

 

(defun triPascal (n / f1 f2)

 (defun f1 (l n)
   (if	(= 0 n)
     (cons 1 l)
     (f1 (f2 (cons 1 l)) (1- n))
   )
 )

 (defun f2 (l)
   (if	(cdr l)
     (cons (+ (car l) (cadr l)) (f2 (cdr l)))
     '(1)
   )
 )

 (f1 nil n)
)

 

Mais la programmation fonctionnelle ce n'est que la récursivité, les fonctions dites "d'ordre supérieur" (qui requièrent une fonction comme argument) comme mapcar, apply etc. ainsi que les fonctions anonyme (lambda) en sont aussi des concepts majeur.

 

Par ailleurs, la fonction f1 ne sert en fait que de compteur, elle pourrait être remplacée par une itération avec repeat :

 

(defun triPascal (n / foo l)

 (defun foo (l)
   (cond
     ((null l) nil)
     ((null (cdr l)) '(1))
     ((cons (+ (car l) (cadr l)) (foo (cdr l))))
     )
 )

 (repeat (1+ n) (setq l (cons 1 (foo l))))
)

[(gile)]

mémoriser tous les appels de 0 à n

 

Pas difficile en adaptant le code ci-dessus:

 

(defun triPascal (n / f1 f2)

 (defun f1 (l n)
   (if	(< 0 n)
     ((lambda (x)
 (cons (cons 1 x) (f1 x (1- n)))
      )
(f2 (cons 1 l))
     )
   )
 )

 (defun f2 (l)
   (if	(cdr l)
     (cons (+ (car l) (cadr l)) (f2 (cdr l)))
     '(1)
   )
 )

 (cons '(1) (f1 nil n))
)

[(gile)]

Pour ce dernier cas F# est intéressant car il permet de créer des séquences paresseuses infinies qui ne seront effectivement calculée que quand elles servent (ici quand elle est transformée en liste)

 

let triPascal n =

   let rec foo l = 
       match l with
       | []      -> []
       | h :: [] -> [1]
       | h :: t  -> h + t.Head :: foo t
       
   Seq.unfold (fun l -> Some(l, 1 :: foo l)) [1] 
   |> Seq.take (n + 1) 
   |> Seq.toList

 

> triPascal 4 ;;

val it : int list list =

[[1]; [1; 1]; [1; 2; 1]; [1; 3; 3; 1]; [1; 4; 6; 4; 1]]

[VDH-Bruno]

Super, :D :D :D

 

Merci (gile), une fois de plus tu as parfaitement compris ou je voulais en venir avec mon code en parlant de programmation fonctionnelle que je m’efforce de maîtriser.

 

Avant de lire tes réponses, j’avais continué à chercher pour sub2, je m’en suis aperçu que ce je voulais écrire n’étais qu’une imbrication de boucles codé récursivement. J’étais arrivé a ça (quasiment pareil que toi, mais en moins):

 (defun sub2 (lst)
  (if (cdr lst)
    (cons (+ (car lst) (cadr lst)) (sub2 (cdr lst)))
  )
)

_$ (append '(1) (sub2 '(1 8 28 56 70 56 28 8 1)) '(1))

(1 9 36 84 126 126 84 36 9 1)

 

Je vois que tu as également précédé ma question de l’étape suivante, mémoriser tous les appels de 0 à n.

Pas difficile en adaptant le code ci-dessus:

Je ne peux hélas pas en dire autant, je ne suis pas arrivé à franchir l’obstacle sans faire un bidouillage en introduisant des variables dans mon code (donc plus en fonctionnelle). J’avais bien essayé une fonction à 2 arguments comme ta fonction f1 sans grand succès, merci pour ton code je vais étudier tout cela de prés.

 

En prime un code en F#, que je vais archiver car j’ai posté la question Qu’elle version me conseilleriez-vous ? sur un autre forum, vu l’absence des réponses, je me suis demandé si il ne vaudrait pas mieux pour moi que je m’essaie à Calm ou OCalm (je ne sais pas ce qui est le mieux) pour ce que je souhaite faire. Il y a visiblement de la doc et des tut en français, mais dans ce cas ce sera un peu plus tard car les math, l’algoritmie et le Lisp m’occupent suffisamment, et je ne me vois pas apprendre une nouvelle syntaxe pour le moment :casstet: .

[(gile)]

Salut,

 

La programmation fonctionnelle a en effet quelque chose de fascinant, mais a aussi un côté "nombriliste". Un langage "purement fonctionnel" ne pourrait qu'être utilisé à faire des calculs dans son interpréteur.

 

Comme toi j'ai découvert la programmation avec AutoCAD (j'en avais un tout petit peu fait en fac, mais c'était il y a plus de 30 ans) et je pense qu'il est important de lier l'apprentissage à des problèmes concrets pour ne pas finir par n'implémenter que des problèmes mathématiques.

 

Quand j'ai voulu essayer d'apprendre un autre langage qu'AutoLISP, j'ai choisi un langage supporté par .NET pour ne pas me déconnecter d'AutoCAD. Avec C# j'ai découvert la Programmation Orientée Objet et les immenses possibilité d'une plateforme qui fournit un nombre impressionnant de bibliothèques.

 

Depuis peu, je regarde du côté de F# parce que je pense que, comme toi, j'aime bien le côté programmation fonctionnelle et qu'en plus ce que j'ai appris de environnement .NET y est toujours accessible.

 

En bonus, un autre bout de code F# qui ne retourne que la rangée n d'un triangle de Pascal.

 

let rowPascal n = 
   let rec foo l = 
       match l with
       | []      -> []
       | h :: [] -> [1]
       | h :: t  -> h + t.Head :: foo t
   List.fold (fun l i -> 1 :: foo l) [] [0 .. n]

 

> rowPascal 0 ;;

val it : int list = [1]

> rowPascal 1 ;;

val it : int list = [1; 1]

> rowPascal 2 ;;

val it : int list = [1; 2; 1]

> rowPascal 6 ;;

val it : int list = [1; 6; 15; 20; 15; 6; 1]

[(gile)]

Salut,

 

On peut utiliser un autre algorithme pour calculer la rangée suivant, ce qui va permettre un code plus concis.

 

Si, pour une rangée (liste), on crée deux nouvelles listes, la première en lui ajoutant un 0 au début et la seconde en lui ajoutant un 0 à la fin, la somme de ces deux listes est la rangée suivante, exemple :

(mapcar '+ '(0 1 1) '(1 1 0)) retourne (1 2 1)

 

(defun nthPascal (n / f)
 
 (defun f (l) (mapcar '+ (cons 0 l) (append l '(0))))
 
 (if (< 0 n)
   (f (nthPascal (1- n)))
   '(1)
 )
)

 

J'ai lancé un challenge sur TheSwamp, même si tu ne lis pas l'anglais tu y trouveras des codes brillants

[VDH-Bruno]

Oui ! Jolie coup ton algorithme.. :D

 

J'ai lancé un challenge sur TheSwamp, même si tu ne lis pas l'anglais tu y trouveras des codes brillants

Je vais suivre cela avec interet,

 

 

Sinon pour faire suite à ta remarque

La programmation fonctionnelle a en effet quelque chose de fascinant

 

En ce qui me concerne c’est quelque chose de très visuelle (et pas abstraite comme j’ai pu le lire), en gros pour imager, ça me fait penser aux poupées russe.

 

D’ailleurs le lisp avec ses parenthèses imbriqués enveloppant une fonction, qui enveloppe une fonction (ou liste) etc.. C’est tout à fait le jeu des poupées russe et je comprends mieux cette notion de langage définit récursivement.

 

Et ce concept de « cellule cons » pour représenter une liste de symbole, qui peuvent être une fonction ou une donnée. Facilement représentable en « arbre binaire » c’est également une bonne représentation visuelle de la chose.

 

Autre avantage du Lisp, avec les fonctions cdr, car, cons, et quelques autres, additionner à quelques opérateurs mathématiques cela suffit pour venir à bout de problèmes relativement ardus (sans avoir besoin de mémoriser une quantité astronomique de fonctions) .

 

Tout cela me parle (donc m’intéresse), faut dire que j’ai une structure mental très visuel et mes années passer en tant que projeteur n’ont pas arrangé les choses.., pour solutionner un problème il faut que je puisse le visualiser, quant j’y arrive il m’arrive de frôler le génie (hélas dans le cas contraire je peux également passer pour le dernier des crétins..)

 

Pour l’anecdote je peux assez facilement visualiser l’ensemble d’un projet commercial sans pour autant parvenir à mémoriser le numéro de l’affaire en cour, de même pour l’histoire de France et tout un tas d'autre chose..

 

En ce qui concerne la programmation qualifié d’impérative (si j’ai bien compris cette notion), bizarrement j’avoue avoir plus de difficulté, mais le problème vient certainement de moi car quant je tente ce type d’approche, j’ai la fâcheuse tendance à coder avant même d’avoir posé clairement le problème que je cherche à solutionner.. Et donc j’ai tendance à bidouiller à chaques nouvelles difficultés, pour finalement tous réécrire une fois le code achevé (lorsque j’y arrive et que j’en ai encore le courage..).

 

En ce qui concerne Calm (dont F# en est une adaptation), j’y songe (rien ne presse) cherchant à m’initier à l’algorithmie, j’ai découvert ce site http:// http://www.france-ioi.org/, et visiblement les solutions proposé sont souvent implémenté dans ce dialecte très proche du Lisp (même si l’absence de parenthèses me perturbe quelque peu..)

 

De plus connaissant la politique de mon entreprise je ne serai pas étonné de repasser sur une version LT dans un futur proche, le fait de travailler sur une version pleine relevant plus d’un concours de circonstance qu’autre chose..

 

Comme toi j’ai également eu une initiation à la programmation à l’IUT, il y a plus d’une quinzaine d’année. Il ne m’en ait strictement rien resté (je n’étais pas spécialement brillant), du pascal ou un dialecte basic je crois ? Un dinosaure trainant parfois sur ce forum pourrai le confirmer.. (si je ne fait pas une erreur sur la personne).

 

A+

 

 

<font class=edite>[Edité le 14/1/2011 par VDH-Bruno]</font>

[VDH-Bruno]

Bonsoir,

 

J’ai enfin réussi à sortir la tête du trou sur un plan professionnel, ce qui m’a permis de retravailler les codes de (gile) et ceux proposés sur the swamp.

 

Et je viens enfin de comprendre la ligne suivante, (que j’avais à tord survolé et copié par mimétisme)

 ( (lambda (x) (cons x (f1 x (1- n))) ) (f2 l) ) 

 

 

 

Pour résumer une subtilité (que j’ignorai) sur l’emploi de lambda seul, et qui n’apparaît pas clairement dans les exemples de l’aide (exemples illustrés avec mapcar et apply).

 

1- Pour exécuter lambda seul, il faut l’envelopper de parenthèses

 (lambda () (alert "Bonjour !!!")) ; retourne #<USUBR @186838c0 -lambda->
[b] ([/b] (lambda () (alert "Bonjour !!!"))  [b] ) [/b]; fonctionne

 

A bien y regarder c'est normal suffit de comparer l'expression avec la syntaxe utilisé pour évaluer une fonction définie avec defun:

 (defun bonjour ()
 (alert "Bonjour !!!")
)

 

 $ (bonjour)
nil
_$

 

 

2- Pour passer un paramètre sans apply ou mapcar (c’est tout bête une fois qu’on le sais)

 ( (lambda (x) (* x x)) 3 ); retourne 9

 

 

3- L’exemple suivant fournie dans l’aide

 (apply '(lambda (x y z)
         (* x (- y z)) 
       ) 
       '(5 20 14) 
)                         ; renvoie  30

 

Peut donc également s’écrire de la façon suivante

 ((lambda (x y z)
         (* x (- y z)) 
       ) 
       5 20 14 
)                         ; renvoie  30

 

A la lueur de cette récente découverte (qui très certainement n’avait pas échappé à la plupart d’entre vous), je vais pouvoir traquer les vilaines variables des quelques codes que n’avais pas réussie à programmer de façon fonctionnelle.

 

Cordialement Bruno,

[(gile)]

Salut,

 

On peut pousser un peu plus loin en implémentant en AutoLISP les fonctions d'ordre supérieur F# (ou OCaml) scan, fold et unfold.

 

gc:fold

;|
gc:fold
Retourne l'état final d'un accumulateur dont l'état initial est modifié
par l'application d'une fonction à chacun des éléments d'une liste

(fun ... (fun (fun init (nth 0 lst)) (nth 1 lst)) ... (nth n lst))

Arguments
fun : une fonction (lambda ou defun) qui prend l'accumulateur et un élément
     de la liste comme arguments et retourne l'état modifié de l'accumulateur
acc : l'état initial de l'accumulateur
lst ; la liste
|;

(defun gc:fold (fun acc lst)
 (if lst
   (gc:fold fun (fun acc (car lst)) (cdr lst))
   acc
 )
)

;; ou, plus simplement :

(defun gc:fold (fun acc lst)
 (foreach n lst (setq acc (fun acc n)))
)

 

gc:scan

;|
gc:scan
Retourne la liste de toutes les états intermédiaires plus l'état final
d'un accumulateur dont l'état initial est modifié par l'application
d'une fonction à chacun des éléments d'une liste.
(list
 init
 (fun init (nth 0 lst))
 (fun (fun init (nth 0 lst)) (nth 1 lst))
 ...
 (fun ... (fun (fun init (nth 0 lst)) (nth 1 lst)) ... (nth n lst))
)

Arguments
fun : une fonction (lambda ou defun) qui prend l'accumulateur et un élément
     de la liste comme arguments et retourne l'état modifié de l'accumulateur
acc : l'état initial de l'accumulateur
lst ; la liste
|;

(defun gc:scan (fun acc lst)
 (cons acc (mapcar '(lambda (x) (setq acc (fun acc x))) lst))
)

 

gc:unfold

;|
gc:unfold
Génère une liste à partir d'une fonction de calcul qui prend un état
et le modifie pour produire chaque élément suivant de la séquence.

(list
 (car (fun init))
 (car (fun (cdr (fun init))))
 (car (fun (cdr (fun (cdr (fun init))))))
 ...
)

Arguments
fun : une fonction (lambda ou defun) qui prend un un état comme argument
     et retourne une liste du type (résultat état_suivant).
state : l'état initial
|;

(defun gc:unfold (fun state)
 ((lambda (r)
    (if (cdr r)
      (cons (car r) (gc:unfold fun (cadr r)))
    )
  )
   (fun state)
 )
)

 

Ces fonctions peuvent être utilisées pour le triangle de Pascal.

Dans les cas de gc:fold et gc:scan la liste ne sert que de compteur, avec gc:unfold, c'est la longueur de la liste (accumulateur) qui sert de condition d'arrêt.

 

(gc:fold (lambda (a l) (mapcar '+ (cons 0 a) (append a '(0)))) '(1) '(1 2 3 4 5))

retourne : (1 5 10 10 5 1)

 

(gc:scan (lambda (a l) (mapcar '+ (cons 0 a) (append a '(0)))) '(1) '(1 1 1 1 1))

retourne : ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1))

 

(gc:unfold (lambda (a)
      (if (<= (length a) 6)
	(list a (mapcar '+ (cons 0 a) (append a '(0))))
      )
    )
   '(1)
)

retourne : ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1))

[VDH-Bruno]

Bonsoir,

 

(gile) merci encore pour ce complément et de tous ce que tu donne en général sur ce forum.

Je vais décortiquer tout cela avec grand intérêt. ;)

[VDH-Bruno]

Bonsoir,

 

A la relecture, je me suis aperçu que je n'avais pas pris le soin de publier mes codes:

 

Version du triangle de pascal de mon premier message modifié pour mémoriser tous les appels de 0 à n, sur le principe d'un accumulateur (notion entrevu sur la récursion terminal) stockant tous les retours d'appel de la fonction f1.

 

 (defun triPascal (n / f1 f2)

 (defun f1 (l n)
   (if     (< 0 n)
     ((lambda (x)
            (cons x (f1 x (1- n)))
      )
           (f2 l)
     )
   )
 )

 (defun f2 (lst)
   (append '(1)
               (mapcar '(lambda (x y) (+ x y)) lst (cdr lst))
               '(1)
   )
 )

 (cons '(1) (f1 nil n))

)

 

 

Ou de façon plus concise (en supprimant la factorisation de f2):

 

 (defun triPascal (n / f1)

 (defun f1 (l n)
   (if     (< 0 n)
     ((lambda (x)
            (cons x (f1 x (1- n)))
      )
           (append  '(1)
                       (mapcar '(lambda (x y) (+ x y)) l (cdr l))
                       '(1)
           )
     )
   )
 )

 (cons '(1) (f1 nil n))

)

 

 

Console Visual LISP

 _$ (trace triPascal f1)
F1
_$ (triPascal 4)
((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))
_$

 

Fenêtre de Suivi

 Saisie (TRIPASCAL 4)
 Saisie (F1 nil 4)
   Saisie (F1 (1 1) 3)
     Saisie (F1 (1 2 1) 2)
       Saisie (F1 (1 3 3 1) 1)
         Saisie (F1 (1 4 6 4 1) 0)
         Résultat:  nil
       Résultat:  ((1 4 6 4 1))
     Résultat:  ((1 3 3 1) (1 4 6 4 1))
   Résultat:  ((1 2 1) (1 3 3 1) (1 4 6 4 1))
 Résultat:  ((1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))
Résultat:  ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

 

C'est vrai que la programmation qualifiée de fonctionnel à un côté ludique et fascinant.. En tout cas cela aura été une discussion trés enrichissante, merci

A+

 

(Ps: Si j'ai bien suivie la prochaine étape sont les fonctions dites d'ordre supérieur).

 

 

<font class=edite>[Edité le 17/2/2011 par VDH-Bruno]</font>

[(gile)]

Ce qu'on appelle fonctions d'ordre supérieur ce sont les fonctions qui requièrent un fonction comme argument.AutoLISP en fournit quelques unes : apply, mapcar, vl-sort, vl-member-if(-not), vl-remove-if(-not).

 

Mais il est possible d'en définir d'autres...

[VDH-Bruno]

En revisitant le sujet, je me suis aperçu qu’il y avait moyen de simplifier et de faire encore plus concis…

 

Version fonctionnelle :

(defun triPascal (n / f1)
 (defun f1 (l n)
   (if (< 0 n)
     (cons l (f1 (append '(1) (mapcar '+ l (cdr l)) '(1)) (1- n)))
   )
 )
 (f1 '(1) (1+ n))
)

 

 

Version itérative :

(defun triPascal (n / l)
 (cons '(1)
       (reverse (repeat n
                  (setq n (1- n)
                        l (cons (append '(1) (mapcar '+ (car l) (cdar l)) '(1)) l)
                  )
                )
       )
 )
)