0

I have noticed many problems in algorithms textbook are solved by recursion (divide and conquer, backtracking,...)

As I tried to enhance my skills in writing them, I have noticed, I just need to translate a recursive definition of the problem to the code. Then I don't even need to know how it will be executed. I thought recursion may naturally belong to functional programming.

Actually I am new to functional or declarative programming (I just was studying some about them). Is it a good advice for students to think declaratively (think to relate the definitions rather how) when they want to write a recursive algorithm? Could it be a general rule for any recursive algorithm?

Beside, what is exactly the declarative approach to solve a problem (as it is in functional programming)?

  • 3
    Real world problems can be either declarative ("This is what we have, this is what we need") either imperative ("Our process is to do this, then this, and maybe this"), or some other flavor. It's understanding and tying up different problems expressed in different languages and styles that's a challenge. I'd say approach the problem in the way most natural to how it's formulated, then use your skills to transform and translate it to the form that is best to work with in the situation. – Ordous Feb 16 '15 at 20:03
5

Broadly speaking, declarative programming concerns itself with telling the computer what to do. Imperative programming concerns itself with telling the computer how to do it. Any non-trivial program will necessarily contain both.

Imperative programming is typically associated with control flow, loops and mutable state. Programs written in the procedural paradigm are typically imperative, though they don't necessarily have to be; you can write functions in a procedural language that operate in much the same way that they do in a functional language.

Imperative programming begins at the machine language level, where loops, jumps and state are common. From there, you can create higher abstractions by writing programming languages, starting from assembly language (which, for the most part, maps to processor instructions). You can progress to a procedural language like C, make it object-oriented (C with classes), add a lot more sophistication (C++), and still be entrenched in imperative programming for the most part.

Declarative programming is characterized more by declarations than instructions. It encompasses domain-specific languages like SQL, functional languages like Haskell, and declarative data structures like XML. Purely functional programming languages dispense with mutable state, preferring to store state in the spaces between function calls, rather than as private members of a class. You can write purely functional code in an imperative/OO language, as Linq demonstrates.

The reason you see recursion a lot in purely functional languages is because those language also dispense with loops. Without a loop (a construct that is grounded specifically in the how), one must resort to recursion to get loop-like behavior. As you have already discovered, many problems can be expressed naturally using recursion, once you understand it.

The important thing to remember about thinking declaratively is that it's just another level of abstraction. Should your students think about solving problems declaratively? Absolutely, but they must also be capable of telling the computer how to solve the problem, not just what.

It's no accident that the programming languages that are considered most practical and pragmatic by their practicioners are the ones that you can write code in both declarative and imperative styles.

Further Reading

Imperative Programming
Declarative Programming

  • Thank you for your complete answer. But I don't think recursion is just to remove loops. Some problem naturally are better solved or stated with recursion. (for example trees manipulations), Anyway I don't see much "HOW" in recursive programs, however there are parts which are about "HOW". Then I thought recursion may naturally belong to declarative language or its just a declarative expression and meant to get that acknowledge by the question. – Ahmad Feb 17 '15 at 5:42
  • What I said was that recursion substitutes for loops in purely functional languages. In impure functional languages such as Common Lisp, there are loop functions available. Every language has imperative constructs under the covers, and if they don't, just keep going down through the abstraction layers until you reach machine language. There's always a "how" somewhere. – Robert Harvey Feb 17 '15 at 5:46
  • By Waht do you mean to define problem based on the existing definitions? it's actually what recursive algorithms do, define base and define the n base on n-1. However I know an engine is needed to drive or evaluate the function based on the basic functions. interesting! – Ahmad Feb 17 '15 at 10:31
  • Isn't a bit strange to give a functional programming example to explain declarative programming and not give logic / constraints programming examples other than SQL ? – Rhangaun Feb 17 '15 at 16:55
  • @skeptic: The list is not comprehensive. I didn't list every purely-functional language either. – Robert Harvey Feb 17 '15 at 16:59
0

I think recursive functions belongs to the declarative paradigm:

  • Define the base: Factorial(1) = 1;
  • Define Factorial n : Factorial(n) = n* Factorial(n-1);

However, any recursive function shouldn't be a complete declarative function. You can define the base and relate (define) the solution of the main problem to solution (definition) of sub-problems. But for this relation you may need a procedure (imperative procedure)

For example consider merge sort:

  • Define the base: One element is already sorted
  • Define the Sort (l,h) : m=(l+h)/2; sub1=Sort(l,m); sub2=Sort(m+1,h); return merge(sub1,sub2);

In this definition merge could be an imperative procedure to relate the definition or solution of sorting the whole array to the sort of the sub-arrays.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.