How to not recurse twice in LISP











up vote
3
down vote

favorite












I'm trying to write a program that returns the Pell numbers sequence based on a given number.



For example (pellNumb 6) should return a list (0 1 2 5 12 29 70)



This is my code so far.
I am able of calculating the numbers, but I am not able of skipping the double recursion.



(defun base (n)
(if (= n 0)
0
(if (= n 1)
1)))

(defun pellNumb (n)
(if (or (= n 0) (= n 1))
(base n)
(let ((x (pellNumb (- n 2))))
(setq y (+ (* 2 (pellNumb (- n 1))) x))
(print y))))


The output for (pellNumb 4) is 2 2 5 12, and this is because i'm recursing to (pellNumb 2) twice.



Is there a way to skip that, and store these values in a list ?



Thanks!










share|improve this question
























  • Your base function is pointless, since it maps 0 to 0, 1 to 1 and returns nil for everything else. Your caller only calls it in the 0 and 1 case, in which the expression (base n) reduces to n.
    – Kaz
    Nov 8 at 23:51










  • The useless base function could also be cutely written as (case n (0 0) (1 1)), or (case n ((0 1) n)).
    – Kaz
    Nov 8 at 23:51

















up vote
3
down vote

favorite












I'm trying to write a program that returns the Pell numbers sequence based on a given number.



For example (pellNumb 6) should return a list (0 1 2 5 12 29 70)



This is my code so far.
I am able of calculating the numbers, but I am not able of skipping the double recursion.



(defun base (n)
(if (= n 0)
0
(if (= n 1)
1)))

(defun pellNumb (n)
(if (or (= n 0) (= n 1))
(base n)
(let ((x (pellNumb (- n 2))))
(setq y (+ (* 2 (pellNumb (- n 1))) x))
(print y))))


The output for (pellNumb 4) is 2 2 5 12, and this is because i'm recursing to (pellNumb 2) twice.



Is there a way to skip that, and store these values in a list ?



Thanks!










share|improve this question
























  • Your base function is pointless, since it maps 0 to 0, 1 to 1 and returns nil for everything else. Your caller only calls it in the 0 and 1 case, in which the expression (base n) reduces to n.
    – Kaz
    Nov 8 at 23:51










  • The useless base function could also be cutely written as (case n (0 0) (1 1)), or (case n ((0 1) n)).
    – Kaz
    Nov 8 at 23:51















up vote
3
down vote

favorite









up vote
3
down vote

favorite











I'm trying to write a program that returns the Pell numbers sequence based on a given number.



For example (pellNumb 6) should return a list (0 1 2 5 12 29 70)



This is my code so far.
I am able of calculating the numbers, but I am not able of skipping the double recursion.



(defun base (n)
(if (= n 0)
0
(if (= n 1)
1)))

(defun pellNumb (n)
(if (or (= n 0) (= n 1))
(base n)
(let ((x (pellNumb (- n 2))))
(setq y (+ (* 2 (pellNumb (- n 1))) x))
(print y))))


The output for (pellNumb 4) is 2 2 5 12, and this is because i'm recursing to (pellNumb 2) twice.



Is there a way to skip that, and store these values in a list ?



Thanks!










share|improve this question















I'm trying to write a program that returns the Pell numbers sequence based on a given number.



For example (pellNumb 6) should return a list (0 1 2 5 12 29 70)



This is my code so far.
I am able of calculating the numbers, but I am not able of skipping the double recursion.



(defun base (n)
(if (= n 0)
0
(if (= n 1)
1)))

(defun pellNumb (n)
(if (or (= n 0) (= n 1))
(base n)
(let ((x (pellNumb (- n 2))))
(setq y (+ (* 2 (pellNumb (- n 1))) x))
(print y))))


The output for (pellNumb 4) is 2 2 5 12, and this is because i'm recursing to (pellNumb 2) twice.



Is there a way to skip that, and store these values in a list ?



Thanks!







lisp common-lisp






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 10 at 16:25









Sylwester

33.5k22854




33.5k22854










asked Nov 7 at 18:10







user10619884



















  • Your base function is pointless, since it maps 0 to 0, 1 to 1 and returns nil for everything else. Your caller only calls it in the 0 and 1 case, in which the expression (base n) reduces to n.
    – Kaz
    Nov 8 at 23:51










  • The useless base function could also be cutely written as (case n (0 0) (1 1)), or (case n ((0 1) n)).
    – Kaz
    Nov 8 at 23:51




















  • Your base function is pointless, since it maps 0 to 0, 1 to 1 and returns nil for everything else. Your caller only calls it in the 0 and 1 case, in which the expression (base n) reduces to n.
    – Kaz
    Nov 8 at 23:51










  • The useless base function could also be cutely written as (case n (0 0) (1 1)), or (case n ((0 1) n)).
    – Kaz
    Nov 8 at 23:51


















Your base function is pointless, since it maps 0 to 0, 1 to 1 and returns nil for everything else. Your caller only calls it in the 0 and 1 case, in which the expression (base n) reduces to n.
– Kaz
Nov 8 at 23:51




Your base function is pointless, since it maps 0 to 0, 1 to 1 and returns nil for everything else. Your caller only calls it in the 0 and 1 case, in which the expression (base n) reduces to n.
– Kaz
Nov 8 at 23:51












The useless base function could also be cutely written as (case n (0 0) (1 1)), or (case n ((0 1) n)).
– Kaz
Nov 8 at 23:51






The useless base function could also be cutely written as (case n (0 0) (1 1)), or (case n ((0 1) n)).
– Kaz
Nov 8 at 23:51














1 Answer
1






active

oldest

votes

















up vote
7
down vote













Get the nth number



Yes, there is a way - use multiple values:



(defun pell-numbers (n)
"Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
(check-type n (integer 0))
(cond ((= n 0) (values 0 0))
((= n 1) (values 1 0))
(t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
(values (+ (* 2 prev) prev-1)
prev)))))
(pell-numbers 10)
==> 2378 ; 985


This is a standard trick for recursive sequences which depend on several previous values, such as the Fibonacci.



Performance



Note that your double recursion means that (pell-numbers n) has exponential(!) performance (computation requires O(2^n) time), while my single recursion is linear (i.e., O(n)).
Moreover, Fibonacci numbers have a convenient property which allows a logarithmic recursive implementation, i.e., taking O(log(n)) time.



Get all the numbers up to n in a list



If you need all numbers up to the nth, you need a simple loop:



(defun pell-numbers-loop (n)
(loop repeat n
for cur = 1 then (+ (* 2 cur) prev)
and prev = 0 then cur
collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)


If you insist on recursion:



(defun pell-numbers-recursive (n)
(labels ((pnr (n)
(cond ((= n 0) (list 0))
((= n 1) (list 1 0))
(t (let ((prev (pnr (1- n))))
(cons (+ (* 2 (first prev)) (second prev))
prev))))))
(nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)


Note that the recursion is non-tail, so the loop version is probably more efficient.



One can, of course, produce a tail recursive version:



(defun pell-numbers-tail (n)
(labels ((pnt (i prev)
(if (= i 0)
prev ; done
(pnt (1- i)
(cond ((null prev) (list 0)) ; n=0
((null (cdr prev)) (cons 1 prev)) ; n=1
(t
(cons (+ (* 2 (or (first prev) 1))
(or (second prev) 0))
prev)))))))
(nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)





share|improve this answer























  • Hey thanks for the answer. Is there a way to put the values in a list ?
    – user10619884
    Nov 7 at 18:50










  • Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
    – sds
    Nov 7 at 18:55










  • no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
    – Will Ness
    Nov 7 at 18:57










  • The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
    – user10619884
    Nov 7 at 18:57










  • @WillNess: you are right - I just could not believe is was that bad ;-)
    – sds
    Nov 7 at 19:08











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














 

draft saved


draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53195333%2fhow-to-not-recurse-twice-in-lisp%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown
























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
7
down vote













Get the nth number



Yes, there is a way - use multiple values:



(defun pell-numbers (n)
"Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
(check-type n (integer 0))
(cond ((= n 0) (values 0 0))
((= n 1) (values 1 0))
(t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
(values (+ (* 2 prev) prev-1)
prev)))))
(pell-numbers 10)
==> 2378 ; 985


This is a standard trick for recursive sequences which depend on several previous values, such as the Fibonacci.



Performance



Note that your double recursion means that (pell-numbers n) has exponential(!) performance (computation requires O(2^n) time), while my single recursion is linear (i.e., O(n)).
Moreover, Fibonacci numbers have a convenient property which allows a logarithmic recursive implementation, i.e., taking O(log(n)) time.



Get all the numbers up to n in a list



If you need all numbers up to the nth, you need a simple loop:



(defun pell-numbers-loop (n)
(loop repeat n
for cur = 1 then (+ (* 2 cur) prev)
and prev = 0 then cur
collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)


If you insist on recursion:



(defun pell-numbers-recursive (n)
(labels ((pnr (n)
(cond ((= n 0) (list 0))
((= n 1) (list 1 0))
(t (let ((prev (pnr (1- n))))
(cons (+ (* 2 (first prev)) (second prev))
prev))))))
(nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)


Note that the recursion is non-tail, so the loop version is probably more efficient.



One can, of course, produce a tail recursive version:



(defun pell-numbers-tail (n)
(labels ((pnt (i prev)
(if (= i 0)
prev ; done
(pnt (1- i)
(cond ((null prev) (list 0)) ; n=0
((null (cdr prev)) (cons 1 prev)) ; n=1
(t
(cons (+ (* 2 (or (first prev) 1))
(or (second prev) 0))
prev)))))))
(nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)





share|improve this answer























  • Hey thanks for the answer. Is there a way to put the values in a list ?
    – user10619884
    Nov 7 at 18:50










  • Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
    – sds
    Nov 7 at 18:55










  • no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
    – Will Ness
    Nov 7 at 18:57










  • The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
    – user10619884
    Nov 7 at 18:57










  • @WillNess: you are right - I just could not believe is was that bad ;-)
    – sds
    Nov 7 at 19:08















up vote
7
down vote













Get the nth number



Yes, there is a way - use multiple values:



(defun pell-numbers (n)
"Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
(check-type n (integer 0))
(cond ((= n 0) (values 0 0))
((= n 1) (values 1 0))
(t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
(values (+ (* 2 prev) prev-1)
prev)))))
(pell-numbers 10)
==> 2378 ; 985


This is a standard trick for recursive sequences which depend on several previous values, such as the Fibonacci.



Performance



Note that your double recursion means that (pell-numbers n) has exponential(!) performance (computation requires O(2^n) time), while my single recursion is linear (i.e., O(n)).
Moreover, Fibonacci numbers have a convenient property which allows a logarithmic recursive implementation, i.e., taking O(log(n)) time.



Get all the numbers up to n in a list



If you need all numbers up to the nth, you need a simple loop:



(defun pell-numbers-loop (n)
(loop repeat n
for cur = 1 then (+ (* 2 cur) prev)
and prev = 0 then cur
collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)


If you insist on recursion:



(defun pell-numbers-recursive (n)
(labels ((pnr (n)
(cond ((= n 0) (list 0))
((= n 1) (list 1 0))
(t (let ((prev (pnr (1- n))))
(cons (+ (* 2 (first prev)) (second prev))
prev))))))
(nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)


Note that the recursion is non-tail, so the loop version is probably more efficient.



One can, of course, produce a tail recursive version:



(defun pell-numbers-tail (n)
(labels ((pnt (i prev)
(if (= i 0)
prev ; done
(pnt (1- i)
(cond ((null prev) (list 0)) ; n=0
((null (cdr prev)) (cons 1 prev)) ; n=1
(t
(cons (+ (* 2 (or (first prev) 1))
(or (second prev) 0))
prev)))))))
(nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)





share|improve this answer























  • Hey thanks for the answer. Is there a way to put the values in a list ?
    – user10619884
    Nov 7 at 18:50










  • Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
    – sds
    Nov 7 at 18:55










  • no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
    – Will Ness
    Nov 7 at 18:57










  • The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
    – user10619884
    Nov 7 at 18:57










  • @WillNess: you are right - I just could not believe is was that bad ;-)
    – sds
    Nov 7 at 19:08













up vote
7
down vote










up vote
7
down vote









Get the nth number



Yes, there is a way - use multiple values:



(defun pell-numbers (n)
"Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
(check-type n (integer 0))
(cond ((= n 0) (values 0 0))
((= n 1) (values 1 0))
(t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
(values (+ (* 2 prev) prev-1)
prev)))))
(pell-numbers 10)
==> 2378 ; 985


This is a standard trick for recursive sequences which depend on several previous values, such as the Fibonacci.



Performance



Note that your double recursion means that (pell-numbers n) has exponential(!) performance (computation requires O(2^n) time), while my single recursion is linear (i.e., O(n)).
Moreover, Fibonacci numbers have a convenient property which allows a logarithmic recursive implementation, i.e., taking O(log(n)) time.



Get all the numbers up to n in a list



If you need all numbers up to the nth, you need a simple loop:



(defun pell-numbers-loop (n)
(loop repeat n
for cur = 1 then (+ (* 2 cur) prev)
and prev = 0 then cur
collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)


If you insist on recursion:



(defun pell-numbers-recursive (n)
(labels ((pnr (n)
(cond ((= n 0) (list 0))
((= n 1) (list 1 0))
(t (let ((prev (pnr (1- n))))
(cons (+ (* 2 (first prev)) (second prev))
prev))))))
(nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)


Note that the recursion is non-tail, so the loop version is probably more efficient.



One can, of course, produce a tail recursive version:



(defun pell-numbers-tail (n)
(labels ((pnt (i prev)
(if (= i 0)
prev ; done
(pnt (1- i)
(cond ((null prev) (list 0)) ; n=0
((null (cdr prev)) (cons 1 prev)) ; n=1
(t
(cons (+ (* 2 (or (first prev) 1))
(or (second prev) 0))
prev)))))))
(nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)





share|improve this answer














Get the nth number



Yes, there is a way - use multiple values:



(defun pell-numbers (n)
"Return the n-th Pell number, n-1 number is returned as the 2nd value.
See https://oeis.org/A000129, https://en.wikipedia.org/wiki/Pell_number"
(check-type n (integer 0))
(cond ((= n 0) (values 0 0))
((= n 1) (values 1 0))
(t (multiple-value-bind (prev prev-1) (pell-numbers (1- n))
(values (+ (* 2 prev) prev-1)
prev)))))
(pell-numbers 10)
==> 2378 ; 985


This is a standard trick for recursive sequences which depend on several previous values, such as the Fibonacci.



Performance



Note that your double recursion means that (pell-numbers n) has exponential(!) performance (computation requires O(2^n) time), while my single recursion is linear (i.e., O(n)).
Moreover, Fibonacci numbers have a convenient property which allows a logarithmic recursive implementation, i.e., taking O(log(n)) time.



Get all the numbers up to n in a list



If you need all numbers up to the nth, you need a simple loop:



(defun pell-numbers-loop (n)
(loop repeat n
for cur = 1 then (+ (* 2 cur) prev)
and prev = 0 then cur
collect cur))
(pell-numbers-loop 10)
==> (1 2 5 12 29 70 169 408 985 2378)


If you insist on recursion:



(defun pell-numbers-recursive (n)
(labels ((pnr (n)
(cond ((= n 0) (list 0))
((= n 1) (list 1 0))
(t (let ((prev (pnr (1- n))))
(cons (+ (* 2 (first prev)) (second prev))
prev))))))
(nreverse (pnr n))))
(pell-numbers-recursive 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)


Note that the recursion is non-tail, so the loop version is probably more efficient.



One can, of course, produce a tail recursive version:



(defun pell-numbers-tail (n)
(labels ((pnt (i prev)
(if (= i 0)
prev ; done
(pnt (1- i)
(cond ((null prev) (list 0)) ; n=0
((null (cdr prev)) (cons 1 prev)) ; n=1
(t
(cons (+ (* 2 (or (first prev) 1))
(or (second prev) 0))
prev)))))))
(nreverse (pnt (1+ n) ()))))
(pell-numbers-tail 10)
==> (0 1 2 5 12 29 70 169 408 985 2378)






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 9 at 13:09

























answered Nov 7 at 18:39









sds

38.3k1492166




38.3k1492166












  • Hey thanks for the answer. Is there a way to put the values in a list ?
    – user10619884
    Nov 7 at 18:50










  • Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
    – sds
    Nov 7 at 18:55










  • no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
    – Will Ness
    Nov 7 at 18:57










  • The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
    – user10619884
    Nov 7 at 18:57










  • @WillNess: you are right - I just could not believe is was that bad ;-)
    – sds
    Nov 7 at 19:08


















  • Hey thanks for the answer. Is there a way to put the values in a list ?
    – user10619884
    Nov 7 at 18:50










  • Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
    – sds
    Nov 7 at 18:55










  • no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
    – Will Ness
    Nov 7 at 18:57










  • The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
    – user10619884
    Nov 7 at 18:57










  • @WillNess: you are right - I just could not believe is was that bad ;-)
    – sds
    Nov 7 at 19:08
















Hey thanks for the answer. Is there a way to put the values in a list ?
– user10619884
Nov 7 at 18:50




Hey thanks for the answer. Is there a way to put the values in a list ?
– user10619884
Nov 7 at 18:50












Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
– sds
Nov 7 at 18:55




Sure: (multiple-value-list (pell-numbers n)), but why would you want it instead of multiple-value-bind?
– sds
Nov 7 at 18:55












no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
– Will Ness
Nov 7 at 18:57




no they mean all of them, not just the last two. --- also, are you sure it's quadratic and not exponential?
– Will Ness
Nov 7 at 18:57












The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
– user10619884
Nov 7 at 18:57




The assignment asked that the results of the recursion would be stored in a list such that (pellNum 6) should return (0 1 2 5 12 29 70)
– user10619884
Nov 7 at 18:57












@WillNess: you are right - I just could not believe is was that bad ;-)
– sds
Nov 7 at 19:08




@WillNess: you are right - I just could not believe is was that bad ;-)
– sds
Nov 7 at 19:08


















 

draft saved


draft discarded



















































 


draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53195333%2fhow-to-not-recurse-twice-in-lisp%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







這個網誌中的熱門文章

Xamarin.form Move up view when keyboard appear

Post-Redirect-Get with Spring WebFlux and Thymeleaf

Anylogic : not able to use stopDelay()