### Author Topic: Recursive function on the fly  (Read 2234 times)

0 Members and 1 Guest are viewing this topic.

#### Grrr1337

• Swamp Rat
• Posts: 735
##### Recursive function on the fly
« on: January 09, 2018, 06:58:59 PM »
Hi guys, just wanted to leave this here - you might find it interesting:
Code - Auto/Visual Lisp: [Select]
1. _\$ (
2.   (setq groupby3
3.     (lambda (L / r)
4.       (repeat 3 (and L (setq r (cons (car L) r))) (setq L (cdr L)) r)
5.       (if L (cons (reverse r) (groupby3 L)) (progn (setq groupby3 nil) (list (reverse r))))
6.     )
7.   )
8.   '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
9. )
10. ((0 1 2) (3 4 5) (6 7 8) (9 10 11) (12 13 14) (15 16))
11. _\$ groupby3
12. nil

(apply ''((a b c)(a b c))
'(
(( f L ) (apply 'strcat (f L)))
(( L ) (if L (cons (chr (car L)) (f (cdr L)))))
(72 101 108 108 111 32 87 111 114 108 100)
)
)

#### roy_043

• Water Moccasin
• Posts: 1814
##### Re: Recursive function on the fly
« Reply #1 on: January 10, 2018, 04:23:43 AM »
Two minor improvements:
Code - Auto/Visual Lisp: [Select]
1. (
2.   (setq groupby3
3.     (lambda (L / r)
4.       (repeat 3 (and L (setq r (cons (car L) r)) (setq L (cdr L))))
5.       (if L (cons (reverse r) (groupby3 L)) (progn (setq groupby3 nil) (list (reverse r))))
6.     )
7.   )
8.   '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
9. )

Maybe this coding style is just too confusing?

Note that because of all the setq's and the use of recursion the code will not be particularly fast.

#### John Kaul (Se7en)

• Needs a day job
• Posts: 9491
##### Re: Recursive function on the fly
« Reply #2 on: January 10, 2018, 07:14:48 AM »
Try a tail-recursive syntax.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### Grrr1337

• Swamp Rat
• Posts: 735
##### Re: Recursive function on the fly
« Reply #3 on: January 10, 2018, 09:22:46 AM »
Maybe this coding style is just too confusing?

Yes - it looks confusing,
But I think if a proper comment description is written about the recursive function (about its inputs/return, aswell note that it localises itself) then it won't be required to understand it, just use it.
Sorry I didn't include any - my point was to share the overall technique, since it looks interesting.

Note that because of all the setq's and the use of recursion the code will not be particularly fast.

Thanks for mentioning, however any recursive routine could be implemented (the one I used was just to demonstrate something practical for that technique).

Try a tail-recursive syntax.

Not sure if this is tail-recursion (but its getting more confusing) :

Code - Auto/Visual Lisp: [Select]
1. _\$ (
2.   (setq
3.     from_right
4.     (lambda ( L )
5.       (if (print (setq L (reverse (cdr (reverse L))))) (from_left L) (setq from_right nil from_left nil))
6.     )
7.     from_left
8.     (lambda ( L )
9.       (if (print (setq L (cdr L))) (from_right L) (setq from_left nil from_right nil))
10.     )
11.   )
12.   '(1 2 3 4 5 6 7 8 9)
13. )
14.
15. (2 3 4 5 6 7 8 9)
16. (2 3 4 5 6 7 8)
17. (3 4 5 6 7 8)
18. (3 4 5 6 7)
19. (4 5 6 7)
20. (4 5 6)
21. (5 6)
22. (5)
23. nil nil
24. _\$ from_right
25. nil
26. _\$ from_left
27. nil
28.

BTW I'm a dummy at understanding recursions - just good enough to write the linear ones.

For that technique, the recursive function must be error-proof, since it won't be able to undefine itself when error occurs.

Should "recursive annonymous function" be a more appropriate name?
« Last Edit: January 10, 2018, 09:26:39 AM by Grrr1337 »
(apply ''((a b c)(a b c))
'(
(( f L ) (apply 'strcat (f L)))
(( L ) (if L (cons (chr (car L)) (f (cdr L)))))
(72 101 108 108 111 32 87 111 114 108 100)
)
)

#### John Kaul (Se7en)

• Needs a day job
• Posts: 9491
##### Re: Recursive function on the fly
« Reply #4 on: January 10, 2018, 09:46:32 AM »
See the examples on the wikipedia page for an example of a tail-recursive function.
[ https://en.wikipedia.org/wiki/Tail_call#Example_programs ]

> Should "recursive annonymous function" be a more appropriate name?
No, because it is named. You are just employing syntactic sugaring techniques. I posted a snip of a conversation I was having with MP which covers this topic, for you once (did you not read it?).
MP, sorry for posting something you wrote out of context but I had the snip in my files and no link. Also, you explain things...gooder.

If you feel as though you're a `dummy at these things', you really should read a good solid book on programing. Structure and Interpretation of Computer Programs is what I started with.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### VovKa

• Swamp Rat
• Posts: 1271
• Ukraine
##### Re: Recursive function on the fly
« Reply #5 on: January 10, 2018, 10:22:02 AM »
Should "recursive annonymous function" be a more appropriate name?
compare
Code: [Select]
`(setq from_right 1 from_left 2)((setq from_right (lambda (L)     (if (print (setq L (reverse (cdr (reverse L)))))       (from_left L)       (setq from_right nil     from_left nil       )     )   )       from_left  (lambda (L)     (if (print (setq L (cdr L)))       (from_right L)       (setq from_left nil     from_right nil       )     )   ) )  '(1 2 3 4 5 6 7 8 9))(print from_right)(print from_left)`with
Code: [Select]
`(setq from_right 1 from_left 2)((lambda (L from_right from_left) (from_left L))  '(1 2 3 4 5 6 7 8 9)  (lambda (L)    (if (print (setq L (reverse (cdr (reverse L)))))      (from_left L)    )  )  (lambda (L)    (if (print (setq L (cdr L)))      (from_right L)    )  ))(print from_right)(print from_left)`

#### MP

• Seagull
• Posts: 17683
• Have thousands of dwgs to process? Contact me.
##### Re: Recursive function on the fly
« Reply #6 on: January 10, 2018, 10:25:46 AM »
Should "syntax masturbation" be a more appropriate name?

fixed
Engineering Technologist • CAD Specialist • Programmer Analyst
Design • Drafting • Document Control • Automation.

#### roy_043

• Water Moccasin
• Posts: 1814
##### Re: Recursive function on the fly
« Reply #7 on: January 10, 2018, 11:26:55 AM »
Maybe this coding style is just too confusing?
Yes - it looks confusing
My point actually is that by condensing the code to fit on a limited number of lines you are confusing yourself, let alone the readers of your code. Just look at your (repeat ...) expression.

#### roy_043

• Water Moccasin
• Posts: 1814
##### Re: Recursive function on the fly
« Reply #8 on: January 10, 2018, 02:21:36 PM »
Does AutoLisp support tail recursion? Using the example from the Wiki link I would say that BricsCAD Lisp does not.

#### Lee Mac

• Seagull
• Posts: 12392
• London, England
##### Re: Recursive function on the fly
« Reply #9 on: January 10, 2018, 03:31:50 PM »
Example using tail recursion:
Code - Auto/Visual Lisp: [Select]
1. (   (lambda ( rec lst ) (rec lst nil))
2.     (lambda ( lst acc )
3.         (if lst
4.             (rec (cdddr lst) (cons (mapcar '(lambda ( a b ) a) lst '(0 1 2)) acc))
5.             (reverse acc)
6.         )
7.     )
8.    '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
9. )
Code - Auto/Visual Lisp: [Select]
1. ((0 1 2) (3 4 5) (6 7 8) (9 10 11) (12 13 14) (15 16))

AFAIK, tail recursion isn't optimised in AutoLISP as it is in other languages.

#### John Kaul (Se7en)

• Needs a day job
• Posts: 9491
##### Re: Recursive function on the fly
« Reply #10 on: January 10, 2018, 03:55:14 PM »
No it's not (from what I remember).

Code: [Select]
`(defun factorial (n) (if (= n 1)    1    (* n (factorial (- n 1)))))Command: (factorial 5)Entering (FACTORIAL 5)  Entering (FACTORIAL 4)    Entering (FACTORIAL 3)      Entering (FACTORIAL 2)        Entering (FACTORIAL 1)        Result:  1      Result:  2    Result:  6  Result:  24Result:  120120(defun factorial (n)  (fact-iter 1 n))(defun fact-iter (product n)  (if (< n 2)      product      (fact-iter (* product n)                 (- n 1))))Command: (factorial 5)Entering (FACTORIAL 5)  Entering (FACT-ITER 1 5)    Entering (FACT-ITER 5 4)      Entering (FACT-ITER 20 3)        Entering (FACT-ITER 60 2)          Entering (FACT-ITER 120 1)          Result:  120        Result:  120      Result:  120    Result:  120  Result:  120Result:  120`
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### Lee Mac

• Seagull
• Posts: 12392
• London, England
##### Re: Recursive function on the fly
« Reply #11 on: January 10, 2018, 04:38:46 PM »

#### John Kaul (Se7en)

• Needs a day job
• Posts: 9491
##### Re: Recursive function on the fly
« Reply #12 on: January 10, 2018, 04:43:52 PM »
No it's not (from what I remember).

Why?
Why isn't it optimized? ...*shrug* I don't have any more knowledge of the inside workings of the interpreter than you do (any more then observations).
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### Lee Mac

• Seagull
• Posts: 12392
• London, England
##### Re: Recursive function on the fly
« Reply #13 on: January 10, 2018, 04:45:03 PM »
No it's not (from what I remember).

Why?
Why isn't it optimized? ...*shrug* I don't have any more knowledge of the inside workings of the interpreter than you do (any more then observations).

Apologies, I misunderstood your response - I thought you were disputing the tail-recursiveness of the function, as opposed to agreeing with the lack of optimisation.

#### John Kaul (Se7en)

• Needs a day job
• Posts: 9491
##### Re: Recursive function on the fly
« Reply #14 on: January 10, 2018, 04:50:25 PM »
Ah. No problem.

I didn't look at your code; I trust your judgement as to its operation. ...I only made the suggestion to use a tail-recursive format for an exercise and a bit of a lesson into recursion 101. And, to eventually drive home the point about iterative functions and proper algorithm design.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org