Thursday, November 3, 2011

recursion

  • Question:-How to make a binary search tree program without using recursion?
    Usually in binary search tree programs, the root is passed to a function insert(). Insert() calls itself many times using recursion, only then can it add the nodes. Is there any way this program can be made without using recursion in insert() ?

    Answer:-I'm not aware of an efficient method for doing that without using recursion. You could have a boolean function that determines if the data is in the left or right half of the list and then change your midpoint index accordingly and just use a loop, but that's going to require a lot more work instead of just using recursion.
  • Question:-Is there a recursion formula i can use to solve this integration by parts problem?
    I have this problem:
    integrate: x^7cos(x^4)dx
    I was wondering if there was a recursion formula I could use to simplify the process of solving this problem. Thanks!

    Answer:-∫x^7cos(x^4)dx
    (x^3)(x^4)cos(x^4)dx
    x^4 = t
    4x^3 dx = dt
    ∫x^7cos(x^4)dx
    substitue to get
    = (1/8)∫tcostdt
    use by parts with u = t and v' = cost
    ∫uv' = uv - ∫u' v
    = (1/8) [tsint - ∫sint]
    = (1/8) [tsint + cost] + c
    = (1/4) (x^4)(sinx^4) + (1/4)(cosx^4) + c
  • Question:-What is recursion in Java and how does do we use it?
    I am learning Java on my own but i dont get what recursion is. I got some code that loops itself. Like a method looping itself till condition is false. Can someone please explain to me recursion really good.

    Answer:-Recursion is when a method calls itself. It is sometimes used because some problems are easier to solve using a recursive solution than an iterative solution. There is no problem that absolutely requires the use of recursion. Its just that for some problems it is easier.

    Recursion is less efficient and uses more memory than iterative solutions. This is because each time the method calls itself, a new stack frame is created with that method, and all of its state. In severe cases, this can result in overflowing the stack, or running out of memory. Because of this, recursion does have to be used with care.

    The classic example of a recursive function is using recursion to generate a fibonacci sequence:

    long fib(int n) {
    if (n == 0 || n == 1) {
    return n;
    } else {
    return fib(n - 1) + fib(n - 2);
    }
    }
  • Question:-What is the difference between recursion and iteration?
    What is the difference between recursion and iteration? In relation to maths and computers.

    Answer:-there is a very nice detailed discussion written here:


    http://en.wikipedia.org/wiki/Iteration#Computing

    thus depending on the technicality of the denotation applied, there may be a difference in the two. but overall, they both mean to imply that there is a repetition in the process

    you may also visit this:
    http://en.wikipedia.org/wiki/Recursion
  • Question:-What are some pros and cons of using recursion?
    What would you tell a beginner in C# what some pros and cons are in recursion and when to use it and when not?
    The only thing I can think off as far as cons is that it takes a lot of memory and for me it seems more confusing than a loop structure would be. But I am sure there are better pros and cons.

    Answer:-Sometimes it's simpler to understand and is a shorter solution to use recursion, but it uses up more memory (because each time the function is called again it adds to the stack)... so I'd recommend just using loops wherever you can.
  • Question:-How do I make a Java class that turns a string into pig latin using recursion and not loops?
    for my AP comp. science class i need to make a program that takes a string with multiple words, and turns each word into pig latin. the hard part is that i can only use recursion, not loops, can anyone help out?

    Answer:-Tell your teacher that's a bit contrived... there's no reason to use recursion for such a problem (unless perhaps you're programming in lisp).

    But since you MUST, look at defining the problem in terms of itself, for example:
    PigLatin("This is a sentence") =
    "isThay"+PigLatin("is a sentence")

    once you do that you find a recursive implementation just kinda falls into place.
  • Question:-How do I make a recursion equation for this situation?
    The book says "Suppose that you make an initial deposit of $100 into an account that pays 4% annual interest, compounded monthly." So how do I write a recursion equation for that? I'm confused by the compounded monthly thing because I know of it were compounded annually it would be Un = 1.04U(n-1). Thanks!

    Answer:-Capital=100(1+0.04/12)^t with t expressed in month
    so capital at month (n) = capital at month(n-1)*(1+0.04/12)
  • Question:-How do understand recursion and write recursive methods?
    I'm finding it extremely difficult to understand recursion. How do I write a recursive program for say division without a guess and check approach. For doing a pre-order traversal on a BST, how do I write a recursive method?

    Answer:-Writing a recursive method is a bit like making a plan to line up dominoes and knock them over. You have to anticipate how each individual recursive call (domino) is going to add its part to accomplishing the whole task.

    That means that the "meat" of a recursive method is not in the recursive part, but in the "end cases" the parts of the code that execute when you are not going to re-call the method, the last domino in the chain, the one that you push to start the fun.

    So, let's look at your first example, a recursive program for (integer) division. The division algorithm you are trying to implement is "for positive d and n, let n(0) be n. Keep subtracting d from n(i) step by step, until in some step q, n(q) is less than d. Your answer is q."

    The key is to look at the END case first. What if at the start n is already less than d? Then you did "zero steps", so your division result is 0.

    In pseudocode:
    ----------------------
    int divide(int n, int d) {
    if (n < d) {
    return 0;
    }
    ....
    }
    ----------------------
    Now what if n is not less than d (greater than or equal to d)? Then we want to try another step in the division process with a smaller n. That is, run the divide function again with "the same d" and n = "the old n" - d. But once THAT divide finishes it only tells us how many subtraction steps were required for (n-d)/d. We know that n/d requires one more step. So we have to add that step tally to the result:
    ----------------------
    int divide(int n, int d) {
    if (n < d) {
    return 0;
    } else {
    return divide( n-d, d ) + 1;
    }
    }
    ----------------------
    What is that second return actually saying? It says: " I don't know how to compute the result myself, but I do know that it is ONE MORE than the result for 'divide( n-d, d )'. So I will 'pass the buck' to that method call and then just add one to whatever it gives me back."

    And the process continues. We keep adding "divide" dominoes to the chain until we reach a divide operation where n has "shrunk" to be smaller than d... our end case, our zero result. Now we knock over the first domino (the last one we added to the chain), returning "0". And the dominoes begin to fall. Every time one domino knocks over another domino we add "1" to the method result until finally the first method call is the last domino to fall, and it returns the division result.

    Let's try some examples:

    12/18:
    ----------------------
    divide(12,18)
    ---> returns 0, since 12 is less than 18
    result is 0.
    ----------------------

    20/5:
    ----------------------
    divide(20, 5)
    ---> returns divide(20-5, 5) + 1
    ------> returns divide(15-5, 5) +1
    ---------> returns divide(10-5, 5) +1
    ------------> returns divide(5-5, 5) +1
    ---------------> returns 0, since 5-5 is 0, which is less than 5
    and now the dominoes fall...
    ------------> returns 0 + 1
    ---------> returns 1 + 1
    ------> returns 2 + 1
    ---> returns 3 + 1
    result is 4.
    ----------------------

    8/3:
    ----------------------
    divide(8, 3)
    ---> returns divide(8-3, 3) + 1
    ------> returns divide(5-3, 3) +1
    ---------> returns 0, since 5-3 is 2, which is less than 3
    and now the dominoes fall...
    ------> returns 0 + 1
    ---> returns 1 + 1
    result is 2.
    ----------------------

    The thinking is the same for a pre-order traversal on a BST. FIRST think about what happens at the end case, when you reach a node with no children. Now how do you get to the end case? What happens along the way?

    If it helps, model some cases:
    • a BST with one node,
    • a BST with two nodes with the 2nd as left child,
    • two nodes with 2nd as right child,
    • three nodes: parent and two children,
    • three nodes: parent, left-child, right-grandchild,
    • three nodes: parent, right-child, right-grandchild,
    • etc.

    Try to see how the dominoes fall in order to build the steps in your traversal.
  • Question:-How do I create a function to calculate the factorial of a given integer WITHOUT using recursion?
    How do I create a function to calculate the factorial of a given integer WITHOUT using recursion?

    So, instead of the using FindFact function calling itself, it will be calling the new function multiple times.

    (C++ not in visual basic)

    Answer:-This is a Javascript code and easy to translate to other languages. You'll get an overflow when the number is too large. How large is large can be verified by running the program.

    ---computes n! for any n-------
    var fact,i,n
    fact=1
    for (i=1; i<=n; i++){
    fact=fact * i
    }
  • Question:-What are examples of times when recursion would be good to use as ooposed to loops (Java)?
    I am in a programming class, and I am quite ahead of it and I was wondering, if recusion is supposed to slow down you computer and stuff. Why use it? When would it be best to use recursion over an iterator

    Answer:-You don't always know when you need to stop.

No comments:

Post a Comment