Find solution
What's the difference between recursion and corecursion?

What is the difference between infinite-recursion and deadlock?

  • here is some thing i thought is a deadlock when i first read the definition.(later found to be infinite recursion). fn1() { fn2(); return *something*; } fn2() { fn1(); return *something"; } a deadlock is some thing where two processes wait for each-other to return something. why cant the above code where two functions are waiting for each-other be a deadlock? site any real practical deadlock please. I've been confused. and how do i detect one?

  • Answer:

    An infinite recursion is a circular definition, like trying to find the first or last moment you can represent on an analog watch, through stepping it by seconds from now. Once it comes full circle, you know it can repeat forever. Program-wise, an infinite loop is sort of the same thing, just written (and implemented) a little differently. Deadlock is a stalemate of two or more actors waiting for a circular dependency to resolve, like deciding who goes first through an intersection when everyone arrives simultaneously, and everyone yields to traffic from the right. Program-wise, single-threaded software can never arrive at a single condition in more than one way at a time, so this doesn't happen without multiple control flows. Your example falls into the former category because each function is defined in terms of the other. You couldn't resolve this by saying that either of them comes before the other, by extension, that would mean it has to come before itself also. One common, real deadlock is message exchange with a blocking send facility; say processes 0,1,2,...,N-1 all need to pass a message to their successor in a ring topology (i.e. "myself + 1, mod N"), and receive one from their predecessor. If this is done by all of them calling "send_to(me+1), receive_from(me-1)" in that order, and no send call returns until reception has begun, you have a splendid deadlock on your hands. Deadlock can be detected by creating a dependency graph and checking it for the presence of cycles, but it is far preferable to avoid them by design (priority schemes with strict ordering do the trick). You can also remedy it by strategic placement of timeout/back-off mechanisms, but that doesn't really fix the issue, so it's best kept for a last resort non-solution, IMHO.

Jan Christian Meyer at Quora Visit the source

Was this solution helpful to you?

Other answers

In the example you cite, there is no waiting: f1 calls f2 which calls f1, etc etc etc. There is only 1 path of execution. The processor keeps executing instructions until some limit is reached like stack space is exhausted at which point the program will crash and stop running. Deadlock is a whole different thing: in deadlock, you have a path of execution (a thread or a process) which invokes some sort of primitive (usually supplied by the OS or the language itself) in which the execution is suspended until some condition is met, except that the condition is never met, so the path of execution is suspended and remains suspended forever. The sleep() primitive, for example, pauses the thread until an event occurs, names the specified amount of time elapses. Most computing environments provide the ability to create a lock object and the system itself insures that only 1 thread can own the lock at a time. For example, incrementing a counter requires a read operation, an addition of 1, and when a write operation. If two threads are attempting to increment the counter at the same time, the counter will not necessarily get incremented twice, depending on how the reads and writes are intermingled. The solution is to create some sort of exclusive lock and then no thread can increase the counter until it possesses the lock:  // a lock named "CounterLock". Any number of threads can create a handle lock = CreateLock("CounterLock"); lock.getLock(); // suspends until no other thread owns the lock // now we own the lock. Anyone else calling getLock will suspend counter = counter + 1; //now we free the lock. any thread suspended will run lock.freeLock() In the classic deadlock, you have two threads trying to get two locks but each one has already got 1 lock, so they both wait for the other to finish and free its lock, so they end up waiting forever thread 1 thread 2 lockA.getLock() lockB.getLock() lockB.getLock() lockA.getLock() If the timing is just wrong, thread 1 will get lock A at the same time thread 2 gets lockB. But now thread 1 cannot get lockB because thread 2 has it, and thread 2 can't get lockA because thread 1 has it, so neither can make progress and both get suspended forever. In infinite recursion, the program will eventually run out of memory and crash (usually pretty quickly). In deadlock the program can get stuck forever and never terminate.

TR Livesey

Related Q & A:

Just Added Q & A:

Find solution

For every problem there is a solution! Proved by Solucija.

  • Got an issue and looking for advice?

  • Ask Solucija to search every corner of the Web for help.

  • Get workable solutions and helpful tips in a moment.

Just ask Solucija about an issue you face and immediately get a list of ready solutions, answers and tips from other Internet users. We always provide the most suitable and complete answer to your question at the top, along with a few good alternatives below.