Results 1 to 20 of 21
 05262010, 11:26 AM #1Member
 Join Date
 May 2010
 Posts
 4
 Rep Power
 0
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; }
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.
 05262010, 01:32 PM #2Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
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;
Java Code:return sum(n / 10) + n % 10;
Java Code:sum(100) > sum(100/10) + 100 % 10 > sum(10) + 10 & 10 > sum(1)
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
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(n1)*n; }
Last edited by m00nchile; 05262010 at 01:35 PM.
Ever seen a dog chase its tail? Now that's an infinite loop.
 05262010, 01:51 PM #3Member
 Join Date
 May 2010
 Posts
 4
 Rep Power
 0
this is what i got on paper:
f(4)>f(41)*4>f(31)*3>f(21)*2>f(11)*1>f(0)return 1
goes back to 11 and replace it with 1, go back to 21 and replace with 1 go back to 31 and replace with 2(1*1*2) goes back and replace 41 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.
 05262010, 01:58 PM #4Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
You pretty much got it, exept the first call is f(51)*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.
 05262010, 02:24 PM #5Member
 Join Date
 May 2010
 Posts
 4
 Rep Power
 0
why is it f(51)*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(n1) + fibo(n2); }
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.
 05262010, 02:36 PM #6Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
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^y1, and that into x*x*x^y2, 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.
 05262010, 02:56 PM #7Senior Member
 Join Date
 Apr 2010
 Location
 Belgrade, Serbia
 Posts
 278
 Rep Power
 6
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)); } }
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;
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;
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
 05262010, 03:11 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
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*(n1)!; so I do this:
Java Code:int me(int n) { if (n == 0) return 1; // this is what I know return n*him(n1); // let him do the hard part }
Java Code:int me(int n) { if (n == 0) return 1; // this is what I know return n*me(n1); // let him do the hard part }
kind regards,
JosLast edited by JosAH; 05262010 at 03:18 PM.
 05262010, 03:31 PM #9Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
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.
 05262010, 03:37 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
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 Clike language eliminate tail recursion or implement memoization ...
kind regards,
Jos
 05262010, 03:56 PM #11Moderator
 Join Date
 Apr 2009
 Posts
 12,431
 Rep Power
 21
Cartoons would be a must as well...
 05262010, 03:57 PM #12
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.
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.
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; 05262010 at 04: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
 05262010, 04:03 PM #13Member
 Join Date
 May 2010
 Posts
 4
 Rep Power
 0
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.
 05262010, 04:11 PM #14
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
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(n1)+him(n2); // my friend solves both of these }
Java Code:int me(int n) { if (n <= 1) return n; // this is all I know return me(n1)+me(n2); // my friend solves both of these }
kind regards,
Jos
 05262010, 04:21 PM #15Moderator
 Join Date
 Apr 2009
 Posts
 12,431
 Rep Power
 21
 05262010, 04:29 PM #16
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
 05262010, 04:36 PM #17Moderator
 Join Date
 Apr 2009
 Posts
 12,431
 Rep Power
 21
 05262010, 04:45 PM #18Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 6
The problem with the OP's original example is simply a bad name choice:
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; }
 05262010, 05:03 PM #19
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
 05262010, 05:19 PM #20Senior Member
 Join Date
 Apr 2010
 Location
 Belgrade, Serbia
 Posts
 278
 Rep Power
 6
Similar Threads

A difficult question  efficient coding?
By tyang in forum Advanced JavaReplies: 3Last Post: 02052010, 03:48 PM 
A difficult question
By tyang in forum New To JavaReplies: 2Last Post: 01312010, 10:45 PM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
Difficult compilation
By pochis40 in forum Java AppletsReplies: 10Last Post: 12212009, 01:35 PM 
Java's web world is really difficult..
By jurka in forum JavaServer Pages (JSP) and JSTLReplies: 1Last Post: 09022008, 05:33 PM
Bookmarks