Thinking Recursion

From: python1 (python1_at_spamless.net)
Date: 03/22/05 

Date: Tue, 22 Mar 2005 10:11:12 -0700

As a little background, I program in (good-ol' ANSI) C; script in dos,
sh, and Python; and write a lot of SQL. I'm mainly a hobbiest.

Trivial problems involving recursion are taking ages to solve/express in
prolog. I assume that after some point it 'clicks', but the progression
is slow. Bratko suggests thinking declaratively, as opposed to
procedurally (which I catch myself drifting to), but either way seems
non-intuitive.

This is probably the third time I've tried to learn Prolog over the last
half-decade, and once again progress has slowed to a stop once something
like this comes up (from "Programming in Prolog"):

append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

...which is understandable if contemplated long enough, but I don't
think I would have come up with this on my own.

How I read it is:

1. It is a fact that the boundary condition of appending occurs when the
first input list is empty; the second and third must be equal.

2. It is a rule that appending, when the first and third input is a
non-empty list, is satisfied if a call to append with the tail of the
first input, the whole of the second input, and the tail of the third
input is successful.

...phew. Is this how I should be thinking?

How long did it take for /you/ to start thinking recursion?

Relevant Pages

  • Re: Thinking Recursion
    ... It is a fact that the boundary condition of appending occurs when the ... > first input list is empty; the second and third must be equal. ... is satisfied if a call to append with the tail of the ... The result of appending List2 to List1 has the same head as List1. ...
    (comp.lang.prolog)
  • Re: Thinking Recursion
    ... >>This is probably the third time I've tried to learn Prolog over the last ... It is a fact that the boundary condition of appending occurs when the ... if we want to talk about Prolog programs we need to agree on how ... and LPTP represents Prolog clauses as variable-free ...
    (comp.lang.prolog)