Is recursion a declarative approach to solve the problems?

Question

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)?

Answer 1

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

Answer 2

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.