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?

 

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.

 

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?

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.

 

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?

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

 

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".

 

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.

 

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.

 

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.

In fact, many physical entities themselves are recursive in nature....the famous Telegrapher's Equation just being one.

 

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.

 

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.

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:

long unsigned fib(int n)
{
   if (n < 2)
      return (unsigned long) n;
   return fib(n-1) + fib(n-2);
}

 

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:

fib.hs

long unsigned fib(int n)
{
   if (n < 2)
      return (unsigned long) n;
   return fib(n-1) + fib(n-2);
}

That's slow in any language but you can use a functional language like Haskell to find a number in the sequence much faster.

fib.hs

module Main where
import System.Environment (getArgs)

fibs :: [Integer]
fibs = 0:1:zipWith (+) fibs (tail fibs)

fib n = fibs !! n

main = getArgs >>= print . fib . read . head


root@nmusic:~# ghc --make -fforce-recomp fib.hs -O3 -o fibhO
[1 of 1] Compiling Main ( fib.hs, fib.o )
Linking fibhO ...
root@nmusic:~# time ./fibhO 5000
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

real 0m0.005s
user 0m0.005s
sys 0m0.000s

https://jeremybytes.blogspot.com/2014/01/a-functional-fibonacci-sequence-as.html

 

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.

 

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?

You're teacher is a teacher because they can't _do_. Not everything is about performance. Writing code is about trading performance versus resources in a balanced manner. Sometimes, the most efficient code calls a portion of itself over and over in order to deal with the same problem repeatedly, such as navigating a sorting or search binary tree.

Get another teacher.

 

Write a compiler. Do it without recursion first, then do it with recursion. Then you will understand.

Bob

 

Perhaps I have been at this for too long, but I cannot even THINK of walking a directory tree WITHOUT recursion!

I certainly agree with the "new teacher" approach and no, I don't want any examples thank you!

 

The only reason why you do anything in programming is to solve a problem in the most efficient way. Efficiency will come down to time and also memory. If the problem that is trying to be solved will be overall more efficient (less time/memory) by using recursion, then you'd use that.

 

Recursion is not seen often when using imperative languages (C and C++ are examples of imperative languages) except perhaps when processing recursive data structures like trees.

Such functions can also consume stack space as the successive calls are made but this isn't always the case. There is a form of recursion named tail recursion and with support from the language/compiler this can totally eliminate stack growth.

But this probably isn't the case for most C compilers or even C++.

It is the case though for most functional languages, these languages use recursion as the norm and loops are either impossible or very rare, variables too are never or seldom used in functional languages.

Compilers for functional languages are able to recognize that a recursive invocation is a tail call and thus optimize the generated code (basically it becomes a loop). This is possible when there are no computations following the recursive call itself which means no local (stack) storage is accessed after the call returns (so there's no need for any stack frame) so if you have a nested recursive call some 100 levels deep all that happens is 100 returns to 99, 99 returns to 98 etc etc and the outermost call itself returns. Why do that when you can just have call 100 return directly - in these cases recursive calls use no stack not even for the return addresses for each invocation and so are actually very efficient.

 

The only reason why you do anything in programming is to solve a problem in the most efficient way. Efficiency will come down to time and also memory. If the problem that is trying to be solved will be overall more efficient (less time/memory) by using recursion, then you'd use that.

Solving the problem in the most efficient way is often not the goal at all. If a slow, brute force solution that can be implemented in ten minutes is efficient enough, that that is a perfectly fine solution and there's no need to spend two hours coming up with a solution that is ten times as efficient (according to whatever metric is being used to determine efficiency). Also, most applications are better off trading efficiency for maintainability. Only if an application NEEDS greater efficiency should maintainability be sacrificed.

 

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:

long unsigned fib(int n)
{
   if (n < 2)
      return (unsigned long) n;
   return fib(n-1) + fib(n-2);
}

Yes Fibonacci is more interesting, here's a simple recursive version and tail recursive version written in F#. The tail recursive version eats no stack.