# Why do we use recursive function?

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

1. ### Werapon Pat Thread Starter Member

Jan 14, 2018
35
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
12,284
2,724
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
24,560
7,700
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 Expert

Aug 27, 2009
6,209
6,987
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
8,749
2,115
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,748
260
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 Expert

Aug 27, 2009
6,209
6,987
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,208
427
In fact, many physical entities themselves are recursive in nature....the famous Telegrapher's Equation just being one.

9. ### MrSoftware Senior Member

Oct 29, 2013
1,503
487
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
24,560
7,700
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 Expert

Aug 27, 2009
6,209
6,987
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 )
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
24,560
7,700
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.