Page 1 of 2 12 LastLast
Results 1 to 20 of 21
  1. #1
    talper is offline Member
    Join Date
    May 2010
    Posts
    4
    Rep Power
    0

    Default findind it very difficult to understand recursion.

    hey,
    i have some computer knowladge from the past, but i had big problems to keep learning and sitting on the computer for long times, and i stopped at the first problem to understand or when something hard came by.
    i thought its not my area of interests, but i found this problem in other areas, i decided to try and learn it again(im 22) and take an open university course which will only start in 5 months(java) but really wanted to learn it by myself so the course also will be easier but also would may like to work in this field in the future. (you have to take the java course for comp siensce no matter what you know).

    the thing is, that since highschool, when i tried understanding recursion i was blasted with confusing thoughts.
    i just cant get to grasp this idea for some reason, and when i think and look about a code(well mostly with return which is most of the recursion codes, just output and then another call with if is easy to grasp).
    i had problems with it a few years ago, and then i stopped with programming, but got the same feelings yesterday which again got me a little unmotivated.
    i know its one of those things that hard until you grasp it.

    so how do you develop recursion thought? i read something about math induction(no idea what it is) to grasp it.
    even small code like this:

    Java Code:
    public int sum(int n)‏
    {‏
    	if( n <= 9)‏
    		return n;‏
    	return sum(n / 10) + n % 10;‏
    }‏
    so dont talk about bigger ones with trees/list etcs....
    i just cant grasp the idea and when i look at it i just dont know what to do with the input.
    is recursion something you need to do on paper step by step? or when you grasp it it becomes second nature?
    how can i understand this concept for good? i know its a function calling itself, and know its got to have a stopping one, but nothing else. well i know alot but nothing is getting in about this subject.

    i would really really appreciate your help in the subject.
    how long btw it took you to learn and understand recursion? what should i do to understand it best?

    big thank you,
    tal.

  2. #2
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Yes, recursion can be quite confusing, especially at the begining, as it does require a bit of knowledge about the way your program executes, what a command stack is etc. In a nutshell, your code executes this way:
    Lets say you call sum(100), first, it checks for the exit condition, it's this piece:
    Java Code:
    if( n <= 9)‏
    		return n;‏
    This tells the method when to stop. If the exit condition is not met, it moves onto the recursive call:
    Java Code:
    return sum(n / 10) + n % 10;‏
    And the method starts again. In our case it would go like this:
    Java Code:
    sum(100) -> sum(100/10) + 100 % 10 -> sum(10) + 10 & 10 -> sum(1)
    Once the sum(1) call is executed, the exit condition is reached, and the result starts travelling backwards:
    Java Code:
    sum(100) -> sum(100/10) + 100 % 10 -> sum(10) + 10 & 10 -> 1
    sum(100) -> sum(100/10) + 100 % 10 -> 1 + 10 & 10 = 1
    sum(100) -> 1 + 100 % 10 = 1
    1
    In the end, 1 is returned.
    A simpler example that helps with the understanding of recursion is calculating a factorial:
    Java Code:
    int factorial(int n) {
      if(n == 0) return 1;
      return factorial(n-1)*n;
    }
    Get a pen and paper, and figure out what a call to factorial(5) does the same way I broke down your program.
    Last edited by m00nchile; 05-26-2010 at 02:35 PM.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  3. #3
    talper is offline Member
    Join Date
    May 2010
    Posts
    4
    Rep Power
    0

    Default

    this is what i got on paper:
    f(4)->f(4-1)*4->f(3-1)*3->f(2-1)*2->f(1-1)*1->f(0)-return 1
    goes back to 1-1 and replace it with 1, go back to 2-1 and replace with 1 go back to 3-1 and replace with 2(1*1*2) goes back and replace 4-1 to 1*1*2*3 multiply by 4 and return to f(4) the sum?

    still for some reason it doesnt grasp me that good, what is the most important thing i should take to understanding recursion from your execise? and how long until someone grasp it naturally and doesnt need to do all the stages with a pen/paper?

    i tried readin about induction which i understand recursion is based on, but find it kinda of difficult to understand also.

    i will try to do more exercises on paper.

  4. #4
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    You pretty much got it, exept the first call is f(5-1)*5. Now, if you really want to sink your teeth into recursion, have a look at the language prolog. I just completed a course in prolog at uni, and while it doesn't have many practical applications, it does teach you about recursion, since it doesn't have loops. If you want to stick to java instead, just have a look at a few mathematical problems, since they are usually easy to implement recursively, just as my factorial example.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  5. #5
    talper is offline Member
    Join Date
    May 2010
    Posts
    4
    Rep Power
    0

    Default

    why is it f(5-1)*5 if the func start as f(4)?
    i tried doing the same with the fibunachi sequance with this exercise:

    Java Code:
    public int fibo(int n)‏
    {‏
    	if(n <= 1)‏
    		return n;‏
    	return  fibo(n-1) + fibo(n-2);‏
    }‏
    what i wrote looks like a tree(is it because at first it split into 2 seperate calls branches?)
    i started fibo(5).
    i got to a situation from fibo(2)-that is fibo(1)+fibo(0) and both return 1, yet at first i tried to do 1+1 and return 2 to fibo(2) which was wrong but only needed to return 1.
    whats happening here?
    oh imsorry, i needed to return 0 where n=0...my bad.

    though i start to understand it a little bit by writing, i still think i dont understand more comlex situations.
    most people at first will need to use a pen/paper?

    im feeling i understand better how to calculate the function, but cant seem to understand howto thing recursively since the beginning when coming to write the answer itself.

  6. #6
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Oh yeah, you started at f(4), I wrote to start at 5, no biggie. The thing is just that, write more, and you'll understand more. The main thing in recursion is how to break down problems into smaller units. Like calculating x^y. You can break that down into x*x^y-1, and that into x*x*x^y-2, and so on, until you reach the condition y=0, and return 1. It's a concept called divide and conquer, where you break down the problem to the point it's trivial to solve, and then work your way up again.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  7. #7
    cselic is offline Senior Member
    Join Date
    Apr 2010
    Location
    Belgrade, Serbia
    Posts
    278
    Rep Power
    5

    Default

    Java Code:
    public class Power {
    	
    	public static int power(int base, int exponent) {
    		if(exponent == 0)
    			return 1;
    		else {
    			int subproblem = power(base, exponent - 1);
    			return subproblem * base;
    		}
    	}
    	
    	public static void main(String[] args) {
    		System.out.println(power(3,4));
    	}
    }
    Look at this better example with function power.

    power(3,4) = 3 * 3 * 3 * 3 = 81

    How it works?
    We know that every base number with exponent 0 is 1.
    for example 1^0 = 1, 5^0 = 1 etc.
    So the recursion base will be the simplest case
    Java Code:
    if(exponent == 0)
    			return 1;
    In this example I want to find 3^4.
    Thinking with recursion is: Well I can't find 3^4. Is there something easier. Yes there is. You can maybe find 3^3 and than just multiply it with 3.
    In another words another form of 3^4 is 3^3 * 3.
    So can we find 3^3. No we can't. Is there something easier. Yes there. Maybe we can find 3^2. In another words 3^3 = 3^2 * 3, and that means
    3^4 = (3^2 * 3) * 3.

    Ok can we find 3^2. No we can't. Is there something easier. Yes there is. Maybe we can find 3^1. In another words 3^2 = 3^1 * 3, and that means 3^3 = (3^1 *3) * 3, and that means 3^4 = ((3^1 * 3) * 3) * 3).

    Ok, can we find 3^1. No we can't Is there something easier. Yes there is. Maybe we can find 3^0. In another words 3^1 = (3^0) * 3.
    3^2 = ((3^0) * 3) * 3.
    3^3 = (((3^0) * 3) * 3) * 3.
    3^4 = ((((3^0) * 3) * 3) * 3) * 0.

    now can we find 3^0.
    Look at this base case:
    Java Code:
    if(exponent == 0)
    			return 1;
    we have 3^0, that means exponent is 0. So we have finally 3^0 = 1.

    when we find 3^0 = 1 we are going back:
    3^1 = (3^0) * 3 = 1 * 3 = 3
    3^2 = ((3^0) * 3) * 3 = (1 * 3) * 3 = 9
    3^3 = (((3^0) * 3) * 3) * 3 = ((1 * 3) * 3) * 3 = 27
    3^4 = ((((3^0) * 3) * 3) * 3) * 0 = (((1 * 3) * 3) * 3) * 3 = 81

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,771
    Blog Entries
    7
    Rep Power
    21

    Default

    Recursion is easy once you understand the 'twist'; suppose I'm the bragging guy who claims to solve all your problems. In the mean time I happen to have a clever humble friend who actually is able to solve a lot of problems. Now suppose you give me a number n >= 0 and you want me to return a number n!

    I know a bit about n! but I can't solve that problem. I can do the simple parts but I hand over the tricky parts to my humbe friend. I happen to know that 0! == 1 and that n! == n*(n-1)!; so I do this:

    Java Code:
    int me(int n) {
       if (n == 0) return 1; // this is what I know
       return n*him(n-1); // let him do the hard part
    }
    And here's the twist: I am schizophrenic: I am my humble, clever friend and he is me; so basically I did this:

    Java Code:
    int me(int n) {
       if (n == 0) return 1; // this is what I know
       return n*me(n-1); // let him do the hard part
    }
    Of course in the real world we don't name a method 'me' but 'fac'.

    kind regards,

    Jos
    Last edited by JosAH; 05-26-2010 at 04:18 PM.

  9. #9
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Jos, seriously man, take some time off and write a textbook. I've never seen someone explain recursion with schizophrenia so well. I know I'd spend more time at uni with textbooks like that. :D
    Ever seen a dog chase its tail? Now that's an infinite loop.

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,771
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by m00nchile View Post
    Jos, seriously man, take some time off and write a textbook. I've never seen someone explain recursion with schizophrenia so well. I know I'd spend more time at uni with textbooks like that. :D
    But you did understand the 'twist' didn't you? Recursion is so simple and indeed it resembles schizophrenia if you can't find anybody else to solve the problem for you ;-) It's too bad not many of the main stream C-like language eliminate tail recursion or implement memoization ...

    kind regards,

    Jos

  11. #11
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,224
    Rep Power
    20

    Default

    Cartoons would be a must as well...

  12. #12
    sonny's Avatar
    sonny is offline Senior Member
    Join Date
    Feb 2010
    Location
    North West England
    Posts
    146
    Rep Power
    0

    Default A simple metaphor

    suppose you have a whole load of roof tiles to carry up on to the roof and only 10 tiles at a time may be taken up the ladder.

    They will carried up by an automatic but temperamental carrying machine that you are going to program to do the task.

    Now if you know you have 10,000 tiles you can program the machine to do this
    Java Code:
    1. repeat the next series of tasks 1000 times then stop.
           pick up ten tiles
           transport them up the ladder
           put down ten tiles
           return to the ground.
    But what do you do if you don't know EXACTLY how many tiles there are in the first place? ....you can use recursion.
    so your program might look like this

    Java Code:
    1. if there are [B]0[/B] tiles on the ground STOP. 
             pick up ten tiles
             transport them up the ladder
             put down ten tiles
             return to the ground.
             repeat.
    this is a rather simple metaphor but it sort of illustrates why we need recursive methods and when to use them as oppose to iteration.

    here are some of my own moments learning to use recursion.:)
    more fun... with recursion

    Confused??? Is one of these codes more efficient than the others?

    kind regards
    Sonny

    EDIT: Jos thats crazy,, but excellently crazy ;)
    Last edited by sonny; 05-26-2010 at 05:00 PM.
    :p I still have my "L" plates on...... directions and explanations are far more help than blaring your Horn! :p Watching:CS106a on YouTube \Reading The Art & Science of Java by Eric S Roberts

  13. #13
    talper is offline Member
    Join Date
    May 2010
    Posts
    4
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    But you did understand the 'twist' didn't you? Recursion is so simple and indeed it resembles schizophrenia if you can't find anybody else to solve the problem for you ;-) It's too bad not many of the main stream C-like language eliminate tail recursion or implement memoization ...

    kind regards,

    Jos
    jos, i appreciate yours and everyone else comments.
    its sure is an informative post for all beginners not just me.
    can you please elaborate a little bit on the schizopran idea?
    you took a simple code that already was written here yet you added the "schizophran" quate and got a positive response from the one after you so it must be a good explanation.

    yet, i cant seem to understand it (:.
    does it "sum" the idea of recursion? should i take somehing from this idea that i found hard taking from writing the function calling on paper?

    i really appreciate yours and everyone else help (:.
    tal.

  14. #14
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,771
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by talper View Post
    jos, i appreciate yours and everyone else comments.
    its sure is an informative post for all beginners not just me.
    can you please elaborate a little bit on the schizopran idea?
    you took a simple code that already was written here yet you added the "schizophran" quate and got a positive response from the one after you so it must be a good explanation.

    yet, i cant seem to understand it (:.
    does it "sum" the idea of recursion? should i take somehing from this idea that i found hard taking from writing the function calling on paper?

    i really appreciate yours and everyone else help (:.
    tal.
    Here's another example: there's me again (the bragging, Mr Know It All guy) and my humble friend; I claim that I can solve the Fibonacci problem: you given me a number n >= 0 and I give you the n'th Fibonacci number. The first two Fibonacci numbers are 0 and 1; everybody knows that.

    Here's how I solve the problem (with the help from my humble friend)

    Java Code:
    int me(int n) {
       if (n <= 1) return n; // this is all I know
       return him(n-1)+him(n-2); // my friend solves both of these
    }
    I don't have a friend; I'm schizophrenic; I made up that friend, so what actually happened was this:

    Java Code:
    int me(int n) {
       if (n <= 1) return n; // this is all I know
       return me(n-1)+me(n-2); // my friend solves both of these
    }
    Of course 'me' should be read as 'fib'. Voila, another hard recursive example translated to silly schizophrenia and finally translated to sensible recursion.

    kind regards,

    Jos

  15. #15
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,224
    Rep Power
    20

    Default

    Quote Originally Posted by JosAH View Post
    I don't have a friend;
    Oh...you poor thing!
    We'll be your friends...:)

  16. #16
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,771
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Tolls View Post
    Oh...you poor thing!
    We'll be your friends...:)
    No! Go away from me! I mean, I have lots of friends and they keep on disturbing me all the time. ;-)

    kind regards,

    Jos

  17. #17
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,224
    Rep Power
    20

    Default

    Quote Originally Posted by JosAH View Post
    No! Go away from me! I mean, I have lots of friends and they keep on disturbing me all the time. ;-)

    kind regards,

    Jos
    You're only fooling yourself you know.
    The voices in your head don't count.
    ;)

  18. #18
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    952
    Rep Power
    5

    Default

    The problem with the OP's original example is simply a bad name choice:
    Quote Originally Posted by talper View Post
    Java Code:
    public int sum(int n)‏
    {‏
    	if( n <= 9)‏
    		return n;‏
    	return sum(n / 10) + n % 10;‏
    }‏
    How can you have a sum of one integer? What we want is the sum of the int's digits, so let's name the method properly. After that it's pretty easy to follow what's going on.
    Java Code:
            public int sumOfDigits(int n) {
                    // if we have only one digit, then we're done -- just return it
                    if (n <= 9 ) return n;
    
                    // we have at least two digits, so we'll split the job up. we'll
                    // take the last digit, which we can get with n % 10, and add
                    // it to the sum of the remaining digits, which we can get with
                    // sumOfDigits(n / 10) 
                    return sumOfDigits(n / 10) + n % 10;
            }
    -Gary-

  19. #19
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,771
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Tolls View Post
    You're only fooling yourself you know.
    The voices in your head don't count.
    ;)
    Indeed, <yes we do!> they don't count <but we do!> and you're ok <he's not, he's got fangs, don't trust him!> and I'll take my pills again tonight <No! Throw them away!> and take a nap <Good! Then we'll come around again>

    kind regards <ppphrrrt!>

    Jos <and us!>

    ps ;-)

  20. #20
    cselic is offline Senior Member
    Join Date
    Apr 2010
    Location
    Belgrade, Serbia
    Posts
    278
    Rep Power
    5

    Default

    Is that means that Java is real you, and html, xml, etc. script stuffs with tags < > are your other personality? ;)
    I'm just kidding.

    Isn't it better to explain recursion with program: how to choose (or find) a girl for a date, instead of mentioning the psychology stuffs :cool:

Page 1 of 2 12 LastLast

Similar Threads

  1. A difficult question - efficient coding?
    By tyang in forum Advanced Java
    Replies: 3
    Last Post: 02-05-2010, 03:48 PM
  2. A difficult question
    By tyang in forum New To Java
    Replies: 2
    Last Post: 01-31-2010, 10:45 PM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  4. Difficult compilation
    By pochis40 in forum Java Applets
    Replies: 10
    Last Post: 12-21-2009, 01:35 PM
  5. Java's web world is really difficult..
    By jurka in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 09-02-2008, 06:33 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •