[Tutor] recursion

[dn]

On 16/08/2022 11.23, Alan Gauld via Tutor wrote:
> On 15/08/2022 18:19, Mats Wichmann wrote:
> 
>>> There are things like traversing trees which are harder to do without
>>> recursion but Fibonacci is absolutely trivial to do 
> 
> The other common recursion function is factorial() and
> that too is nearly trivial to do non-recursively. But
> traversing trees etc and other real-world uses of
> recursion are a lot harder to teach! (You need to teach
> trees for a start!)
> 
> I suspect the problem is that recursio is introduced
> too early in the curriculum, but teachers like it
> because it's cool from an academic standpoint and
> can help teach a regular approach to designing programs.
> (see the online book "How to Design Programs" for
> an example of the approach...http://htdp.org)


Does the recursion/iteration decision also depend upon the definition of
the 'result' from Fibonacci?

Is the objective to find a single value?
- the next Fibonacci number
- the tenth Fibonacci number
- the first Fibonacci number larger than 10

Alternately, is the objective to find a group:
- the first ten Fibonacci numbers
- the next ten Fibonacci numbers
- ten Fibonacci numbers larger than 10
(feels a bit contrived!)

A recursive method will handle the first category happily. However,
cannot handle the second without repeated calls to populate a list - and
one hopes/assumes, some "memoisation" - which is itself, effectively, a
list.


However, when there is much (much) more to the script, and the Fibonacci
but a small part, having a list could become 'expensive'. More
importantly to code-design, the list-creation will likely occur 'at the
front end' and (thus) dislocated from where it is used (cohesion,
coupling, independence, interdependence, code-organisation, ...).

Unlike many?most other programming-languages, Python offers the
generator option (ie iteration as generation) which will answer both of
the above categories, and places the (?self-documenting) call right in
the midst of 'the action' without unnecessary distraction!

Accordingly, the preference (@Mats), and the curriculum/temptation idea
(@Alan). What 'they' do should not define what 'we' do/can do!
-- 
Regards,
=dn