so if we call factorial(3),
we get to line 5 and calculate outputValue = 3(factorial(2)),
so if we call factorial(2),
we get to line 5 and calculate outputValue_2 = 2(factorial(1)).
factorial(1) returns 1, so in our second call to factorial(2), outputValue_2 = 2(1) = 2
that returns to our first call to factorial(3) and we get outputValue = 3(2) = 6
so we return 6, which we now know is 3!
Hope this helps and let me know if you have any questions.
Definition: a function is recursive if it calls itself.
That's only direct recursion, you can also have indirect recursion if the function calls another function which then calls the original. This is used lots when evaluating expressions or any operations with order of precedence.
Forget thinking of recursion explicitly, let recursion arise naturally out of the way you construct the definition of what a correct answer to your question is.
If our question is, given a root to a tree, what are the values of its leaves? The answer can be stated as, "The values of the leaves of a tree are either the value of the root itself if it has no subtrees, otherwise the leaves of each of its subtrees."
And a python implementation would look like
classtreeNode:
... # tree nodes have a value and a list of children, which are all treeNodes too.defleaves(root):
if root.children == []:
return root.value
else:
leaves_li = []
for subtree in root.children:
leaves_li += leaves(subtree)
return leaves_li
A more procedural way of finding recursive solutions is to think of what the simplest possible case is (often, it's what happens when the input is empty, or is 1, or 0). That case is called the base case. The we only need to think of a way that we can simplify any other input to get closer to the base case, and find the relation between the simpler version of the problem and the hard version. In the above example, the base case is when they give you a root with no subtree. A more difficult case is when they give you a root that has more subtrees. But the relation is that all subtrees have leaves if you keep traversing their own subtrees, and leaves have no subtrees (they are our base case!). Therefore, all that's necessary is for the function to work its way into the base case and consolidate the returns from the base case into something that makes more sense. In this case we consolidate the leaves by just putting them all into the same list, which we return.
If you're studying something CS related in college, you'll likely take an algorithms class that covers Dynamic Programming. If you don't really get recursion, I'd encourage you to look up "Dynamic Programming Tabulation". It's a technique for solving problems that have intuitive recursive solutions through iteration instead of recursion. For the tree leaves problem it actually isn't very useful, it is much harder to make an iterative solution (although still possible) than the simple recursive solution I provided. It's good to learn because it will teach you the fundamental intuition behind mathematical induction, which is the foundation for recursion in CS.
deleted by creator
deleted by creator
Recursion is simpler than you're making it. Definition: a function is recursive if it calls itself.
As an example, let's write a function in python to calculate z!=z(z-1)(z-2)*...*1
def factorial(z): if (n<=1): return 1 else: outputValue = z*factorial(z-1) return outputValue
so if we call factorial(3), we get to line 5 and calculate outputValue = 3(factorial(2)), so if we call factorial(2), we get to line 5 and calculate outputValue_2 = 2(factorial(1)). factorial(1) returns 1, so in our second call to factorial(2), outputValue_2 = 2(1) = 2 that returns to our first call to factorial(3) and we get outputValue = 3(2) = 6 so we return 6, which we now know is 3!
Hope this helps and let me know if you have any questions.
That's only direct recursion, you can also have indirect recursion if the function calls another function which then calls the original. This is used lots when evaluating expressions or any operations with order of precedence.
Sure
Here's a good link that explains it
This is what worked for me, YMMV.
Forget thinking of recursion explicitly, let recursion arise naturally out of the way you construct the definition of what a correct answer to your question is.
If our question is, given a root to a tree, what are the values of its leaves? The answer can be stated as, "The values of the leaves of a tree are either the value of the root itself if it has no subtrees, otherwise the leaves of each of its subtrees."
And a python implementation would look like
class treeNode: ... # tree nodes have a value and a list of children, which are all treeNodes too. def leaves(root): if root.children == []: return root.value else: leaves_li = [] for subtree in root.children: leaves_li += leaves(subtree) return leaves_liA more procedural way of finding recursive solutions is to think of what the simplest possible case is (often, it's what happens when the input is empty, or is 1, or 0). That case is called the base case. The we only need to think of a way that we can simplify any other input to get closer to the base case, and find the relation between the simpler version of the problem and the hard version. In the above example, the base case is when they give you a root with no subtree. A more difficult case is when they give you a root that has more subtrees. But the relation is that all subtrees have leaves if you keep traversing their own subtrees, and leaves have no subtrees (they are our base case!). Therefore, all that's necessary is for the function to work its way into the base case and consolidate the returns from the base case into something that makes more sense. In this case we consolidate the leaves by just putting them all into the same list, which we return.
If you're studying something CS related in college, you'll likely take an algorithms class that covers Dynamic Programming. If you don't really get recursion, I'd encourage you to look up "Dynamic Programming Tabulation". It's a technique for solving problems that have intuitive recursive solutions through iteration instead of recursion. For the tree leaves problem it actually isn't very useful, it is much harder to make an iterative solution (although still possible) than the simple recursive solution I provided. It's good to learn because it will teach you the fundamental intuition behind mathematical induction, which is the foundation for recursion in CS.
deleted by creator
:Hofstader-shining: