Today we will study principles of recursion and then solve questions related to recursion. This is the continuation of the last part, so in case you have missed that one, make sure to have a quick check here
Summary of the week-
Day 1 We learnt how to make user defined functions. User defined functions are custom functions designed by the programmer. They provide code reusability and flexibility while solving complicated problems. All this was backed up with two sample questions and one conceptual exercise.
Day 2 We learnt how to return values from functions. By breaking complicated operations into functions, we can make the code more compact and flexible. This is possible because we can return data-types back to the function call. Returning multiple values is invalid, but we can return a list which can hold the values.
Day 3 We studied recursion in Python. We implemented it by calling the function from inside it. We then solved some good questions related to recursion.
Guidelines for using recursion.
Recursion is a tool to allow programmer to concentrate on the key step of an algorithm, without initially having to worry about how to couple that step with the others.
Recursion is basically breaking apart a problem into parts, solving a single part and the while problem gets solved magically.
Consider an example. We want to find the shortest path to a city. So first, we find shortest paths to all it's neighboring cities, and then choose the route which is smallest. And how do we find the shortest path to the neighboring cities? Well in the same way! This is the beauty of recursion. We can address a complicated problem by making smaller replicas to the main problem on and forever! This is known as the travelling salesman problem, which we solved using recursion.
We first start any problem by asking "How can this problem be divided into parts?" Once we have a simple short step to solve a mini-problem of the same type, applying it to a larger problem is easy.
Finally we need to decide a stopping rule to prevent the recursion from running indefinitely. For example in the above problem, we stop when we reach to the city from where we have to start.
Exercises
The Greatest Common Divisor (GCD) of two positive integers is the largest integer that divides both of the two integers. Thus, the GCD of 8 and 12 is 4, the GCD of 9 and 18 is 9, and the GCD of 16 and 25 is 1. Write a recursive function namd
GCD (x,y)that implements this division algorithm: if y=0, then the GCD of x and y is x; otherwise the GCD of x and y is the same as the GCD of y and x%y.The binomial coefficients may be defined by the following recurrence relation, which is the idea of the pascal's triangle.
C(n,0)=1 and C(n,n)=1 for n>=0
C(n,k)=C(n-1,k)+C(n-1,k-1) for n>k>0
Write a recursive function which will generate C(n,k) by using the above formulaThe Ackermann's function, defined as follows, is a standered device to determine how well recursion is implemented in any device.
A(0,n)=n+1 for n>=0
A(m,0)=A(m-1,1) for m>0
A(m,n)=A(m-1,A(m,n-1)) for m>0 and n>0
Yes, the above exercises are a bit difficult. But the key is finding C(n,k) or A(m,n) and directly implementing it. The rest is just about when to stop the recursion conditions. All the best for solving them! Solving these exercises will make you all fluent with recursion and it's problem solving principles.
All Answers here
A bit about the course
I know, I am going a bit slow for some of you. But this is for the benifit of those who are here for the first time. This week was a gentle intro to user defined functions. In the coming weeks, I will cover all the details of the language. For those who already know coding basics, they can just skim through the blog and mull upon the exercises. The exercises provided will strengthen and reinforce the concepts. Moreover they are directly taken or similar to past coding tests from the interview panel...
Epilogue- We all know that neither me nor you have ever seen each other. Learning in remote environment is a difficult, and teaching is perhaps even more difficult. Teaching is never a one-way process. When a teacher teaches with pattern, he/she expects that the student must respond back. Either with doubts, remarks or nods of approval.
But friends, being remote, we cannot interact with each other. The only way we can connect is through the comments below. So I urge everyone to comment on the posts. Currently I am in doubt whether you all are understanding me or not. Should I speed up the pace or maybe explain more clearly? I am not getting any feedback from you. Any doubts, discussions, remarks or even a simple hi from you is a great source of motivation for me. So I look forward to your comments below...😊
For those who have not yet made account in Dev.to, you can have a free easy sign-up using your mail or GitHub accounts. I would suggest the budding developers to create your GitHub free account right away. You would require to register sooner or later anyways
🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥
Follow me on GitHub for updates.........
Top comments (0)