# Thread: findind it very difficult to understand recursion.

1. Member
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;‏
}‏```
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. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
8
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 01:35 PM.

3. Member
Join Date
May 2010
Posts
4
Rep Power
0
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. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
8
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.

5. Member
Join Date
May 2010
Posts
4
Rep Power
0
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. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
8
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.

7. Senior Member
Join Date
Apr 2010
Location
Posts
278
Rep Power
7
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. 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 03:18 PM.

9. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
8
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

10. Originally Posted by m00nchile
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. Moderator
Join Date
Apr 2009
Posts
13,312
Rep Power
23
Cartoons would be a must as well...

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
put down ten tiles
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
put down ten tiles
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.:)
http://www.java-forums.org/new-java/...recursion.html

http://www.java-forums.org/new-java/...an-others.html

kind regards
Sonny

EDIT: Jos thats crazy,, but excellently crazy ;)
Last edited by sonny; 05-26-2010 at 04:00 PM.

13. Member
Join Date
May 2010
Posts
4
Rep Power
0
Originally Posted by JosAH
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. Originally Posted by talper
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. Moderator
Join Date
Apr 2009
Posts
13,312
Rep Power
23
Originally Posted by JosAH
I don't have a friend;
Oh...you poor thing!

16. Originally Posted by Tolls
Oh...you poor thing!
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. Moderator
Join Date
Apr 2009
Posts
13,312
Rep Power
23
Originally Posted by JosAH
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.
;)

18. Senior Member
Join Date
Mar 2010
Posts
952
Rep Power
8
The problem with the OP's original example is simply a bad name choice:
Originally Posted by talper
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. Originally Posted by Tolls
You're only fooling yourself you know.
;)
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. Senior Member
Join Date
Apr 2010
Location
Posts
278
Rep Power
7
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 Last

#### Posting Permissions

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