• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion practice  RSS feed

 
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I see most of the algorithms are implemented using recursion. Also in several interviews interviewers explicitly asked to solve the problem using
recursion only. When speak about recursion i am unable to think any way and understanding those algorithms or solution is difficult to me.

Is there any way to practice so that i can start recursively? Right now, i am trying to do some practice in codingbat.
 
Marshal
Posts: 56606
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
… and how did you answer those interview questions. Remember interview questions are different from real‑life questions. How you answer them matters just as much as what you say.

I would suggest that most algorithms are not implemented recursively. For most things you use recursion as an alternative to iteration. Historically however recursion is older; Alan Turing's definition of a complete language was one which supports sequence selection and recursion. It was over 30 years later that Böhm and Jacopini demonstrated that all programs can be written with sequence selection and iteration. Also (I think) Dijkstra showed that recursion and iteration were mutually equivalent in terms of their weakest‑predicate effects.

you should give up trying to understand recursion, as I did years ago. Just remember it works and use it. And practice as much as possible. Start by working through factorials, Fibonacci numbers (running in O(n) or O(logn) compexity), palindromes and powers of integers. Keep going until you can do them in your sleep.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
and how did you answer those interview questions.

I saw questions on the internet. Even i receive a interview request in which it is mentioned that candidate should know recursion use for data structure and daily work.

and practice as much as possible

Yup i need to practice hard.
 
Saloon Keeper
Posts: 7993
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It may seem like an overused example, but I think the Towers of Hanoi is a *great* way of understanding recursion.

In this game, you need to move a tower of discs from one peg to another. Smaller discs can only be on top of larger discs. You have a third peg to help out. You can only move one disc at a time.

Here's how to solve it:



Wait, so if we can can only move one disc at a time, then how do we move the entire stack except for the last one to peg B? Is there some magic function to do this? Yes! The function you're currently writing!
 
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's take a simple example and see if we can help you understand.

5! (factorial), as you probably know, is 1 * 2 * 3 * 4 * 5. There is a simple iterative way to solve this.



There's nothing wrong with this code, but let's try to think of it recursively. The heart of recursion is being able to break down a task into subtasks. If we consider a method call fact(5) that will return the factorial of 5, we can think of the task this way:

fact(5) = 1 * 2 * 3 * 4 * 5 = ( 1 * 2 * 3 * 4 ) * 5 = fact(4) * 5

If we generalize this, we get:

fact(n) = fact(n - 1) * n

So now we can write our fact method like this:



But there's a problem: when does the recursion stop? Well, we know that fact(1) = 1, so there's no reason to go farther than that. So this gives us:



Now you have a recursive way to solve the problem. Is this case the recursive way is not "better", just different. But sometimes recursion is the best way to deal with a problem. Let's take processing a directory tree.



There are ways of doing this iteratively, but they're not the best way.
 
Sheriff
Posts: 4932
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Tushar,

Your pain is fully understandable. For some reason, quite many people struggling with it. So don't worry, you'll get it at some point.

Some classic general theory, it might will help you:
First thing: recursive function is a function that calls itself.
Second: as Knute already explained, just in different words, a recursive function normally has two parts:
1. Stopping condition. Processing the case where the recursive function does not call itself.
2. Recursive step. Processing the case where the recursive function calls itself.
Very important to remember, that recursive call must have different parameters than those of the calling function because otherwise the program gets into an infinite loop (since it wouldn't reach stopping condition, as state wouldn't change ever).

Some time ago I wrote some of the main sorting algorithms in recursive way (without loops at all). I'm just not sure if i'm allowed to post it here, well, might wouldn't be a good idea. If you'd decide to practice of rewriting Bubble, or Insertion sort algorithms in recursive way, might would be a good start, so we could help.
What also I could suggest you, if you could find some video about sorting algorithms, visual representation of it should definitely help.
Recursion actually is like a spacial thinking - visual view helped me at some point. Found one video for you > watch
 
Campbell Ritchie
Marshal
Posts: 56606
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
LV pointed out something important. All recursion must have a base case where the recursion can stop. Otherwise it will go on for ever until you run out of memory or stack space.
 
Liutauras Vilda
Sheriff
Posts: 4932
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:All recursion must have a base case where the recursion can stop. Otherwise it will go on for ever until you run out of memory or stack space.

Moreover, what Campbell Ritchie just reminded, that "base case" condition check has to be above recursive/-s calls, otherwise would be faced the same issues.

Check one below Tushar
 
Campbell Ritchie
Marshal
Posts: 56606
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote: . . .
. . .
Look at §10.5.2 here. That shouild read
return (x == 0) ? 1 : recursiveCall(x - 1); //The first () are redundant.
And I would prefer to call an int i, j or k. Keep x y z for doubles.

Also please explain why your use of x-- there will cause your recursion to run
for ever until you run out of memory or stack space.
 
Liutauras Vilda
Sheriff
Posts: 4932
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, Campbell, cannot disagree also as agree Since OP trying to understand recursion, probably it would add more confusion.
In terms of readability, personally i'd prefer old school way of doing this.

Campbell Ritchie wrote:Also please explain why your use of x-- there will cause your recursion to run

You're right about that. Should be x-1 or (--x that should work).
 
Campbell Ritchie
Marshal
Posts: 56606
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote: . . . Since OP trying to understand recursion, probably it would add more confusion. . . .
You are probably right there.

I presume everybody else knows why using x-- would cause that program to run for ever until you exhaust your memory or stack space.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suppose recursion needs practice and more practice to start thinking recursively.
 
Liutauras Vilda
Sheriff
Posts: 4932
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:I presume everybody else knows why using x-- would cause that program to run for ever until you exhaust your memory or stack space.
Actually you pointed out to a very good point to stop and think about.
I never actually used shortcut in recursive call for incrementing or decrementing, so I never jumped to a traps before as I did now. Well, very interesting and at the same time logical, that function being called with the same parameters, since expression not being evaluated and x not being decremented.
Could you please express your thoughts Campbell Ritchie in proper English, please.
 
Campbell Ritchie
Marshal
Posts: 56606
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Think? Maybe. I gave up thinking how recursion works years ago. I have a compiler with hundreds of recursions in, so I simply have to trust that it works




… and it does work.
 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tushar Goel wrote:I suppose recursion needs practice and more practice to start thinking recursively.

It does. Whenever you see a task that can be broken into subtasks and those subtasks are the same as the task, you have a problem that recursion can solve.

Try creating a method that will return the Fibonacci number when passed a sequence number.
 
Campbell Ritchie
Marshal
Posts: 56606
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote: . . . Try creating a method that will return the Fibonacci number when passed a sequence number.
Fibonacci numbers is an interesting example for recursion; there are algorithms which run in logarithmic time, in linear time and in exponential time.
 
Liutauras Vilda
Sheriff
Posts: 4932
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tushar Goel wrote:I suppose recursion needs practice and more practice to start thinking recursively.

Well, probably practice at first instance not much can help here. It seems you need to understand whats happening here first, then of course you'd need some practise on different cases to prove yourself that it works how you understand.

You need some kind of visual diagram so you could see whats happening. Try to find on internet some visual representation of recursion.

Paradox, in general recursion is the way how solve problems easier (not understand easier), every time as Knute said, you make your problem smaller (subtask), and solve that first, with less amount of inputs.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:
Tushar Goel wrote:I suppose recursion needs practice and more practice to start thinking recursively.

It does. Whenever you see a task that can be broken into subtasks and those subtasks are the same as the task, you have a problem that recursion can solve.

But that doesn't necessarily mean that you should use it.

For example, the recursive Factorial (or indeed, Fibonacci) series is good as a teaching aid; but almost certainly NOT what you would use in practise. In general, for recursion to be a good option, it's use should reduce the problem geometrically on each iteration - sometimes called "divide and conquer".

Winston
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
sometimes called "divide and conquer".

Its sound interesting.

Thanks all, to check the visual image to learn the recursion is good way to understand. I am also doing some practice on coding bat. It seems to be good
option to me.
 
Ranch Hand
Posts: 10128
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I see recursive logic much easily done using functional paradigm! Working with Scala, the last couple of months, I tend to write tail recursive logic most of the times. Try doing the Functional & Reactive Programming courses through Coursera. You will learn to solve and write recursive logic with the added benefit of learning a new programming language!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!