Why do we use recursive function?

Discussion in 'Programmer's Corner' started by Werapon Pat, Feb 23, 2018.

  1. Werapon Pat

    Thread Starter New Member

    Jan 14, 2018
    27
    0
    So I have learnt about it and at the end of class my teacher said
    by the way, you know what, recursive function is hard to write and its processing efficiency is inferior.
    So why do we use that instead of just write a normal loop?
     
  2. Papabravo

    Expert

    Feb 24, 2006
    11,637
    2,440
    Conceptually, there are many problems which are recursive in nature. Converting an algebraic expression from infix notation to RPN is a classic example. I would suggest the opposite, that recursive functions are easy to write and understand. Converting them to more efficient forms is easier when you understand the underlying process.
     
  3. WBahn

    Moderator

    Mar 31, 2012
    22,859
    6,822
    You might need a new teacher.

    Many, many problems are far easier to solve with recursive algorithms and their performance can be quite good. Among the most efficient sorting algorithms are some that are doubly recursive, such as Quick Sort.
     
    Papabravo likes this.
  4. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    4,660
    4,986
    That's much too broad a statement for programming in general. There is a entire class of programming (Functional programming) that uses recursive as a key tool of the language.
    https://dzone.com/articles/functional-programming-recursion
     
  5. dl324

    AAC Fanatic!

    Mar 30, 2015
    6,949
    1,606
    Sometimes it's easier to solve a problem using a recursive function. They may be more difficult to understand, but are more elegant than a "normal loop".
     
  6. John P

    AAC Fanatic!

    Oct 14, 2008
    1,709
    252
    Your teacher might be right that a recursive function isn't as efficient as the same thing without recursion. But computer power is incredibly cheap, and your time has value (we hope). So it makes sense to use any technique that makes you more efficient. Once you own the computer, you don't have to pay it anything extra if you waste its time. (Up to the level of bitcoin mining: then the cost of extra electricity becomes an issue.)

    I just worked on a project where a computer had to "explore" a branching pattern, represented as a series of notations describing a series of left and right branches which each eventually lead to a dead end. There would be ways to do it by counting branches, but it seemed easiest to call the routine recursively for every new branch, either left or right. That's because each branch led to a "new tree" which was computationally the same as the original main stem. So in this case it was "If you reach a branch, explore it. If you hit a dead end, return". It wasn't hard to write at all.
     
  7. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    4,660
    4,986
    The recursive function is most efficient and logical as a programming tool when the static data is the functional state as in the branching algorithm above, Fibonacci sequences or most Chess programs. When this is not (changing loop variable, creating and managing a stack frame) iteration can be 'better'. So the real question to the teacher should be the screw problem. "Which sorts of problems is iteration (flat blade ) better at than recursion (phillips head), and vice versa?". In the end it might not matter on the machine hardware, a very good compiler will optimize the human code into a unstructured, unrecognizable collection of goto(s) and tables anyway. ;)
     
  8. KL7AJ

    AAC Fanatic!

    Nov 4, 2008
    2,173
    401
    In fact, many physical entities themselves are recursive in nature....the famous Telegrapher's Equation just being one.
     
  9. MrSoftware

    Well-Known Member

    Oct 29, 2013
    1,012
    276
    But when programming recursion, you have to be aware of your resource limits and be careful not to exceed them. Stack overflow from too many recursive calls probably being the most obvious.
     
  10. WBahn

    Moderator

    Mar 31, 2012
    22,859
    6,822
    Though the classic recursive Fibonacci function is exponential time complexity and most people can get to the 50th or 60th Fibonacci number long before even today's fast computers can. Not that long ago, it was around the 30th value when most people caught up to the machine. Each successive number basically takes twice as long to compute as the prior number did.

    The function I'm talking about looks like this:

    Code (C):
    1.  
    2. long unsigned fib(int n)
    3. {
    4.    if (n < 2)
    5.       return (unsigned long) n;
    6.    return fib(n-1) + fib(n-2);
    7. }
    8.  
     
    nsaspook likes this.
  11. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    4,660
    4,986
    That's slow in any language but you can use a functional language like Haskell to find a number in the sequence much faster.

    Code (Text):
    1.  
    2. fib.hs
    3.  
    4. module Main where
    5. import System.Environment (getArgs)
    6.  
    7. fibs :: [Integer]
    8. fibs = 0:1:zipWith (+) fibs (tail fibs)
    9.  
    10. fib n = fibs !! n
    11.  
    12. main = getArgs >>= print . fib . read . head
    13.  
    14.  
    15. root@nmusic:~# ghc --make -fforce-recomp fib.hs -O3 -o fibhO
    16. [1 of 1] Compiling Main ( fib.hs, fib.o )
    17. Linking fibhO ...
    18. root@nmusic:~# time ./fibhO 5000
    19. 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
    20.  
    21. real 0m0.005s
    22. user 0m0.005s
    23. sys 0m0.000s
    24.  
    https://jeremybytes.blogspot.com/2014/01/a-functional-fibonacci-sequence-as.html
     
  12. WBahn

    Moderator

    Mar 31, 2012
    22,859
    6,822
    I've never even looked at Haskell, so I have no idea what the "zipWith" is or what the syntax is of the line it is in. I'm assuming the (tail fibs) is somehow establishing that the function is tail recursive, which I think all functional programming languages require be converted to an iterative implementation.
     
Loading...