findind it very difficult to understand recursion.

[talper]

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:

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.

[m00nchile]

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:

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:

return sum(n / 10) + n % 10;‏

And the method starts again. In our case it would go like this:

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:

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:

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.

[talper]

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.

[m00nchile]

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.

[talper]

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:

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.

[m00nchile]

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.

[cselic]

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

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:

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

[JosAH]

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:

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:

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

[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

[JosAH]

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

[Tolls]

Cartoons would be a must as well...

[sonny]

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

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

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 ;)

[talper]

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.

[JosAH]

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)

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:

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

[Tolls]

I don't have a friend;

Oh...you poor thing!
We'll be your friends...:)

[JosAH]

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

[Tolls]

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.
;)

[gcalvin]

The problem with the OP's original example is simply a bad name choice:

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.

        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-

[JosAH]

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 ;-)

[cselic]

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: