You are invited to Log in or Register a free Frihost Account!

# What can recursive function do?

Arrogant
While learing about recursive function,I found that it could be used in solving Tower of Hanoi and finding the determinant of a nxn matrix.
Well thats kind of cool... Can you tell me other examples of good use of recursion?
All iterative functions can be rewritten as a recursive function and vice versa, but some problems are more suitable to solve using recursion. I think recursive functions are especially suitable when you have a branching search of some kind e.g. searching for a file in a file system or searching for the best future state in a turn-based game.

The choice between iterative and recursive function also depends on what language you use. In functional programming languages you often have to use recursion for all kinds of repetition. In some other languages recursion can be slower than iteration and if the recursion is deep you could easily run out of stack space, causing a stack overflow.
D'Artagnan
 Arrogant wrote: While learing about recursive function,I found that it could be used in solving Tower of Hanoi and finding the determinant of a nxn matrix. Well thats kind of cool... Can you tell me other examples of good use of recursion?

 Quote: All iterative functions can be rewritten as a recursive function and vice versa, but some problems are more suitable to solve using recursion. I think recursive functions are especially suitable when you have a branching search of some kind e.g. searching for a file in a file system or searching for the best future state in a turn-based game.

my two bits of real world use, not sure if the best uses though...

i've used it to make menus (kind of overkill in php but the function was really flexible and still in use by the company),

i used it in enterprise systems where we needed to control the manufacturing of complex machinery and we used recursion to generate the product component trees and to make several kinds of verifications and calculations with the whole set of componets and components of components in a final product (actually components and final products were "classes" of products)
Marcuzzo
I've used a few recursive functions in my life and I have to say that I had it all wrong.
when you check the javascript example at Wikipedia : http://en.wikipedia.org/wiki/Recursion_(computer_science)

this is impressive stuff:
 Code: function fib(n) {     return (n < 2 ? n : fib(n - 1) + fib(n - 2)); }

when you put in an echo and call WScript.echo ( fib(6)); you get:

 Code: C:\Users\marco\Desktop>cscript fibonacci.js Microsoft (R) Windows Script Host versie 5.8 Copyright (C) Microsoft Corporation 1996-2001. Alle rechten voorbehouden. checking 6 checking 5 checking 4 checking 3 checking 2 checking 1 checking 0 checking 1 checking 2 checking 1 checking 0 checking 3 checking 2 checking 1 checking 0 checking 1 checking 4 checking 3 checking 2 checking 1 checking 0 checking 1 checking 2 checking 1 checking 0 8 C:\Users\marco\Desktop>

didn't see that one coming
 Arrogant wrote: While learing about recursive function,I found that it could be used in solving Tower of Hanoi and finding the determinant of a nxn matrix.
Yes indeed, and here it is as implemented in JavaScript:
 Code: var hanoi = function hanoi(disc, src, aux, dst) {     if (disc > 0) {         hanoi(disc - 1, src, dst, aux);         console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);         hanoi(disc - 1, aux, src, dst);     } }; //Function invocation with 5 disks hanoi(5, 'Src', 'Aux', 'Dst');
Just give it the number of discs it should move and the three posts to be used...

Marcuzzo wrote:
I've used a few recursive functions in my life and I have to say that I had it all wrong.
when you check the javascript example at Wikipedia : http://en.wikipedia.org/wiki/Recursion_(computer_science)

this is impressive stuff:
 Code: function fib(n) {     return (n < 2 ? n : fib(n - 1) + fib(n - 2)); }

when you put in an echo and call WScript.echo ( fib(6)); you get:
(...................)
didn't see that one coming
Well, yes, that Fibonacci function is very crude and computationally intensive... You called it once and it calls itself 24 !... and if you asked for fib(15), you'll get 1973 recursions..and for fib(50).. well forget it, I cancelled the call after 2,537,347 recursions with nothing in sight :-)..

A better way to do it in JavaScript is to make our function capable of remembering the values it has already computed... which significantly reduces its workload... and make it a lot more efficient.. and It goes like this :
 Code: var fibonacci = (function () {     var memo = [0, 1],          fib = function (n){ var result = memo[n];                     if (typeof result !== 'number') { result = fib(n - 1) + fib(n - 2);  memo[n] = result; }                          return result;                 };     return fib; }());

With this function, fibonacci(6) is computed in 11 recursions; fibonacci(15) in 29 and fibonacci(50) in 99 recursions and it's equal to 12,586,269,025.

It should be said that JavaScript doesn't have tail recursion optimization (meaning that if a function returns the result of invoking itself recursively, then the invocation is replaced with a loop), which means that functions that recurse very deeply can fail by exhausting the return stack.

PS: Both functions (the hanoi and fibonacci) are borrowed from Doug Crockford.. the well known JavaScript authority..
The Fibonacci function is often used to demonstrate recursion but it's not really suitable for recursion because the naive implementation has to do a lot of the calculations multiple times. Writing it as an iterative function is maybe not as elegant but it should be more efficient.
 Code: function fib(n) {    var a = 1;    var b = 0;    for (var i = 0; i < n; i++)    {       var tmp = a;       a += b;       b = tmp;    }    return b; }
The Fibonacci function is often used to demonstrate recursion but it's not really suitable for recursion because the naive implementation has to do a lot of the calculations multiple times. Writing it as an iterative function is maybe not as elegant but it should be more efficient.
 Code: function fib(n) {    var a = 1;    var b = 0;    for (var i = 0; i < n; i++)    {       var tmp = a;       a += b;       b = tmp;    }    return b; }

Agreed !.. the one thing I would change in your function (for the sake of code clarity) is to move the tmp variable declaration outside the loop... JavaScript doesn't have block scoping.. which makes tmp variable visible anywhere within that function ... But the final result, in this case, doesn't change anyway ..
amagard
Computing the factorial of a number would be another application of a recursive function.
I agree to Peterssidan:
 Quote: All iterative functions can be rewritten as a recursive function and vice versa

In many cases it is probably a matter of taste which implementation is the better one. I actually think that the human brain is not designed for thinking recursively, that's probably also the experience Marcuzzo made:
 Quote: I've used a few recursive functions in my life and I have to say that I had it all wrong.

I made the same experience when learning Turbo Prolog long time ago: it is hard to force our natural procedural thinking into recursive algorithms.

Here is my implementation of a Factorial method in Python ( which is actually not needed since Python comes with a Factorial method in the math module ):
 Code: import sys def fact_p(n):     i = 1     for k in range(n):         i *= (k+1)     return i     def fact_r(n):     if n == 1:         return 1     else:         return n * fact_r(n-1)  print fact_p(int(sys.argv[1]))  print fact_r(int(sys.argv[1]))

We probably could discuss forever now which of the two implementations is the "better" one ( and what our criteria for "better" actually would be ).
Arrogant
Recursion has a lot of potential as i see it..It is also used in Josephus Problem
And i recently solved a problem of possible coin combinations using recursion
Stay_Classy
Many things, such as fractal trees, require complex array systems without recursion. You would have to keep track of the depth, the angle, etc, where in recursion, you could have the compiler figure all that out for you. It basically goes back to whether you want to do more work or whether you want the computer to do more work.
Arrogant
YEAH recursion's cool
I just solved a problem "Summation of primes" using recursion..
Helped a lot
Cant think if its possible the other way

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP