Mixing
How does the catalan() function works here?
I stumbled across this function to calculate the catalan number:
def catalan(n):
if n == 0:
return 1
else:
sum = 0
for i in range (n):
sum +=(catalan(i))*(catalan(n-1-i))
return sum
My question is how sum gets values when for example n=2:
sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))
How did catalan(2-1-0) or for any other than 0 argument get it's value, if we defined only value for n=1?
python recursion catalan
asked Jan 2 at 12:12
James ToasterJames Toaster
175
add a comment |
I stumbled across this function to calculate the catalan number:
def catalan(n):
if n == 0:
return 1
else:
sum = 0
for i in range (n):
sum +=(catalan(i))*(catalan(n-1-i))
return sum
My question is how sum gets values when for example n=2:
sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))
How did catalan(2-1-0) or for any other than 0 argument get it's value, if we defined only value for n=1?
python recursion catalan
asked Jan 2 at 12:12
James ToasterJames Toaster
175
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Concrete Mathematics
– user633183
Jan 2 at 17:23
add a comment |
I stumbled across this function to calculate the catalan number:
def catalan(n):
if n == 0:
return 1
else:
sum = 0
for i in range (n):
sum +=(catalan(i))*(catalan(n-1-i))
return sum
My question is how sum gets values when for example n=2:
sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))
How did catalan(2-1-0) or for any other than 0 argument get it's value, if we defined only value for n=1?
python recursion catalan
asked Jan 2 at 12:12
James ToasterJames Toaster
175
I stumbled across this function to calculate the catalan number:
def catalan(n):
if n == 0:
return 1
else:
sum = 0
for i in range (n):
sum +=(catalan(i))*(catalan(n-1-i))
return sum
My question is how sum gets values when for example n=2:
sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))
How did catalan(2-1-0) or for any other than 0 argument get it's value, if we defined only value for n=1?
python recursion catalan
python recursion catalan
asked Jan 2 at 12:12
James ToasterJames Toaster
175
asked Jan 2 at 12:12
James ToasterJames Toaster
175
edited Jan 2 at 14:04
James Toaster
asked Jan 2 at 12:12
James ToasterJames Toaster
175
asked Jan 2 at 12:12
James ToasterJames Toaster
175
asked Jan 2 at 12:12
James ToasterJames Toaster
175
175
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Concrete Mathematics
– user633183
Jan 2 at 17:23
add a comment |
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Concrete Mathematics
– user633183
Jan 2 at 17:23
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Concrete Mathematics
– user633183
Jan 2 at 17:23
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Concrete Mathematics
– user633183
Jan 2 at 17:23
add a comment |
1 Answer
1
active
oldest
votes
Pen and paper evaluation
catalan (0)
# 1
catalan (1)
# = 0 + catalan (0) * catalan (1-1-0)
# = 0 + 1 * catalan (0)
# = 0 + 1 * 1
# = 0 + 1
catalan (2)
# = 0
# + catalan (0) * catalan (2-1-0)
# + catalan (1) * catalan (2-1-1)
# = 0
# + 1 * catalan (1)
# + 1 * catalan (0)
# = 0
# + 1 * 1
# + 1 * 1
# = 1
# + 1
# = 2
catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# = 0
# + 1 * catalan (2)
# + 1 * catalan (1)
# + 2 * catalan (0)
# = 0
# + 1 * 2
# + 1 * 1
# + 2 * 1
# = 0
# + 2
# + 1
# + 2
# = 5
Wasted cycles
Let's look at a naive fibonacci process –
def fib (n):
if n < 2:
return n
else:
return fib (n-1) + fib (n-2)
This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice below that the entire computation of fib(3), almost half the work, is duplicated. In fact, it is not hard to show that the number of times the procedure will compute fib(1) or fib(0) (the number of leaves in the above tree, in general) is precisely fib(n + 1). To get an idea of how bad this is, one can show that the value of fib(n) grows exponentially with n — SICP - Tree Recursion
A similar problem is happening with you catalan program, but to an even worse degree. Calling catalan(3) will yield six (6) additional catalan calls
# catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# ...
# = 5
There are multiple techniques available to avoid this problem. Follow the citation above for more help on the topic.
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
add a comment |
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',
autoActivateHeartbeat: false,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54006167%2fhow-does-the-catalan-function-works-here%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
Pen and paper evaluation
catalan (0)
# 1
catalan (1)
# = 0 + catalan (0) * catalan (1-1-0)
# = 0 + 1 * catalan (0)
# = 0 + 1 * 1
# = 0 + 1
catalan (2)
# = 0
# + catalan (0) * catalan (2-1-0)
# + catalan (1) * catalan (2-1-1)
# = 0
# + 1 * catalan (1)
# + 1 * catalan (0)
# = 0
# + 1 * 1
# + 1 * 1
# = 1
# + 1
# = 2
catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# = 0
# + 1 * catalan (2)
# + 1 * catalan (1)
# + 2 * catalan (0)
# = 0
# + 1 * 2
# + 1 * 1
# + 2 * 1
# = 0
# + 2
# + 1
# + 2
# = 5
Wasted cycles
Let's look at a naive fibonacci process –
def fib (n):
if n < 2:
return n
else:
return fib (n-1) + fib (n-2)
This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice below that the entire computation of fib(3), almost half the work, is duplicated. In fact, it is not hard to show that the number of times the procedure will compute fib(1) or fib(0) (the number of leaves in the above tree, in general) is precisely fib(n + 1). To get an idea of how bad this is, one can show that the value of fib(n) grows exponentially with n — SICP - Tree Recursion
A similar problem is happening with you catalan program, but to an even worse degree. Calling catalan(3) will yield six (6) additional catalan calls
# catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# ...
# = 5
There are multiple techniques available to avoid this problem. Follow the citation above for more help on the topic.
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
add a comment |
Pen and paper evaluation
catalan (0)
# 1
catalan (1)
# = 0 + catalan (0) * catalan (1-1-0)
# = 0 + 1 * catalan (0)
# = 0 + 1 * 1
# = 0 + 1
catalan (2)
# = 0
# + catalan (0) * catalan (2-1-0)
# + catalan (1) * catalan (2-1-1)
# = 0
# + 1 * catalan (1)
# + 1 * catalan (0)
# = 0
# + 1 * 1
# + 1 * 1
# = 1
# + 1
# = 2
catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# = 0
# + 1 * catalan (2)
# + 1 * catalan (1)
# + 2 * catalan (0)
# = 0
# + 1 * 2
# + 1 * 1
# + 2 * 1
# = 0
# + 2
# + 1
# + 2
# = 5
Wasted cycles
Let's look at a naive fibonacci process –
def fib (n):
if n < 2:
return n
else:
return fib (n-1) + fib (n-2)
This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice below that the entire computation of fib(3), almost half the work, is duplicated. In fact, it is not hard to show that the number of times the procedure will compute fib(1) or fib(0) (the number of leaves in the above tree, in general) is precisely fib(n + 1). To get an idea of how bad this is, one can show that the value of fib(n) grows exponentially with n — SICP - Tree Recursion
A similar problem is happening with you catalan program, but to an even worse degree. Calling catalan(3) will yield six (6) additional catalan calls
# catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# ...
# = 5
There are multiple techniques available to avoid this problem. Follow the citation above for more help on the topic.
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
add a comment |
Pen and paper evaluation
catalan (0)
# 1
catalan (1)
# = 0 + catalan (0) * catalan (1-1-0)
# = 0 + 1 * catalan (0)
# = 0 + 1 * 1
# = 0 + 1
catalan (2)
# = 0
# + catalan (0) * catalan (2-1-0)
# + catalan (1) * catalan (2-1-1)
# = 0
# + 1 * catalan (1)
# + 1 * catalan (0)
# = 0
# + 1 * 1
# + 1 * 1
# = 1
# + 1
# = 2
catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# = 0
# + 1 * catalan (2)
# + 1 * catalan (1)
# + 2 * catalan (0)
# = 0
# + 1 * 2
# + 1 * 1
# + 2 * 1
# = 0
# + 2
# + 1
# + 2
# = 5
Wasted cycles
Let's look at a naive fibonacci process –
def fib (n):
if n < 2:
return n
else:
return fib (n-1) + fib (n-2)
This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice below that the entire computation of fib(3), almost half the work, is duplicated. In fact, it is not hard to show that the number of times the procedure will compute fib(1) or fib(0) (the number of leaves in the above tree, in general) is precisely fib(n + 1). To get an idea of how bad this is, one can show that the value of fib(n) grows exponentially with n — SICP - Tree Recursion
A similar problem is happening with you catalan program, but to an even worse degree. Calling catalan(3) will yield six (6) additional catalan calls
# catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# ...
# = 5
There are multiple techniques available to avoid this problem. Follow the citation above for more help on the topic.
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
Pen and paper evaluation
catalan (0)
# 1
catalan (1)
# = 0 + catalan (0) * catalan (1-1-0)
# = 0 + 1 * catalan (0)
# = 0 + 1 * 1
# = 0 + 1
catalan (2)
# = 0
# + catalan (0) * catalan (2-1-0)
# + catalan (1) * catalan (2-1-1)
# = 0
# + 1 * catalan (1)
# + 1 * catalan (0)
# = 0
# + 1 * 1
# + 1 * 1
# = 1
# + 1
# = 2
catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# = 0
# + 1 * catalan (2)
# + 1 * catalan (1)
# + 2 * catalan (0)
# = 0
# + 1 * 2
# + 1 * 1
# + 2 * 1
# = 0
# + 2
# + 1
# + 2
# = 5
Wasted cycles
Let's look at a naive fibonacci process –
def fib (n):
if n < 2:
return n
else:
return fib (n-1) + fib (n-2)
This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice below that the entire computation of fib(3), almost half the work, is duplicated. In fact, it is not hard to show that the number of times the procedure will compute fib(1) or fib(0) (the number of leaves in the above tree, in general) is precisely fib(n + 1). To get an idea of how bad this is, one can show that the value of fib(n) grows exponentially with n — SICP - Tree Recursion
A similar problem is happening with you catalan program, but to an even worse degree. Calling catalan(3) will yield six (6) additional catalan calls
# catalan (3)
# = 0
# + catalan (0) * catalan (3-1-0)
# + catalan (1) * catalan (3-1-1)
# + catalan (2) * catalan (3-1-2)
# ...
# = 5
There are multiple techniques available to avoid this problem. Follow the citation above for more help on the topic.
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
answered Jan 2 at 17:55
user633183user633183
71.6k21143182
71.6k21143182
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54006167%2fhow-does-the-catalan-function-works-here%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Concrete Mathematics
– user633183
Jan 2 at 17:23