Power of recursion through intuition and example

How to explain recursion to a kid ?

Well, ask the kid that if he is standing in a long queue, how would he/she find out number of people in front.

explain him this way –

He can ask the same question to the person in front and that person can ask the same question to the person in front. It will keep going till the first person in the queue, who will tell person behind him that there are zero people in front of him. Person behind the first one will know that there is exactly one guy standing in front of him (remember first person said 0, so 0+1 =1). This will keep happening till words reach to the kid who asked the question in first place.

Basically recursion two most important concept in it –

  1. Base case(in queue example when there are no more people in front).
  2. Recursion with smaller population(asking the same question to guy in front).

Let’s see more concrete example –

How many ways are there to choose group of 4(k) people out of 60(n) people?

On the broader way, I can divide the total no of groups in two part. First part where in groups John(any arbitrary pick) is there plus the groups  where John is not there

Now think closely about first part – these groups will always have John(well that’s how we defined this part of groups). So there are just 3 more people left to be chosen out of 59 people.

Now about second part – This part will never have John in any of it’s groups. Since he has been already excluded and we still need 4 people to choose, we are left with choosing 4 people from group of 59 people.

So, I can write samller problem, nck = (n-1)c(k-1)+(n-1)ck

Now let’s talk about base-

  1. In second scenario, population is decreasing so, some point of time n will become equal to k. In that case where you have choose k people from k people , answer is 1.
  2. In first part, where population and choices both are decreasing by one and k will become 0. In that case where you have to choose 0 people from n. Then also answer is n.

 

public class Choose {
public static void main(String[] args) {
System.out.println(new Choose().choices(60, 4));
}

public int choices(int n, int k){
if(n==k || k==0){
return 1;
}
else
return choices(n-1,k-1)+choices(n-1, k);
}

}

Continue reading “Power of recursion through intuition and example” →