recursionfunctional-programmingschemeflattentail-recursion# Converting a function with two recursive calls in scheme to make it tail-recursive

Before I start: YES, this is a homework from college. Before I get told that I'm lazy and evil: this part of the homework was to convert two functions we already had, this one is the 6th.

```
(define (flatten-list a-list)
(cond ((null? a-list) '())
((list? (car a-list))
(append (flatten-list (car a-list)) (flatten-list (cdr a-list))))
(else (cons (car a-list) (flatten-list (cdr a-list))))))
```

The function, as you can guess, flattens a list even if it's nested. My specific problem with the transformation comes in the (list? (car a-list)) condition, in which I'm doing two recursive calls. I already did fibonacci, which I can do by just having two "acummulators" on the tail recursion. However, my mind is not trained in this yet to know how it should go.

I would appreciate if I was given hints and not the result. Thanks!

Solution

Here's my solution:

```
(define (flatten-iter a-list)
(define (flat-do acc lst-interm lst)
(cond
((null? lst)
(reverse acc))
((and (list? lst-interm) (not (null? lst-interm)))
(flat-do acc (car lst-interm) (append (cdr lst-interm) lst)))
((not (list? lst-interm))
(flat-do (cons lst-interm acc) empty lst))
((list? (car lst))
(flat-do acc (car lst) (cdr lst)))
(else
(flat-do (cons (car lst) acc) empty (cdr lst)))))
(flat-do empty empty a-list))
(flatten-iter (list 1 (list 2 (list 3 4 (list 5 empty 6))) 7 8))
=> (1 2 3 4 5 6 7 8)
```

Tail-recrusive functions require that they never return, and thus you can't use stack for storing your program's state. Instead, you use function arguments to pass the state between function calls. Therefore, we need to determine how to maintain the state. Because the result of our function is `list?`

, it's meaningful to grow an `empty`

list; we're using `acc`

for this purpose. You can see how it works in `else`

branch above. But we should be able to process nested lists. And while we're going deeper, we should keep the rest elements of the nested list for further processing. Sample list: `(list 1 (list 2 3) 4 5)`

Until `(list 2 3)`

we have already added `1`

to accumulator. Since we can't use stack, we need some other place to store the rest elements of the list. And this place is the `lst`

argument, which contains elements of the original list to be flattened. We can just `append`

the `lst`

to the rest elements `(cdr (list 2 3))`

which are `(list 3)`

, and proceed with the list's head we stumbled upon while flattening, i. e. (car (list 2 3)) which is just `2`

. Now, `(and (list? lst-interm) (not (null? lst-interm)))`

succeeds because `flat-do`

is called this way:

```
(flat-do (list 1) (list 2 3) (list 4 5))
```

and the condition triggers this code:

```
(flat-do (list 1) (car (list 2 3)) (append (cdr (list 2 3)) (list 4 5)))
```

`flat-do`

again is called this way: (flat-do (list 1) 2 (list 3 4 5))

The condition `(not (list? 2))`

now succeeds and the code `(flat-do (cons 2 1) empty (list 3 4 5))`

is evaluated.

The rest processing is done with `else`

branch until `lst`

is `null?`

and `reverse`

is performed on `acc`

. Function then returns the reversed accumulator.

- Should I use global variables in recursion
- Find permutation of array - Where am I going wrong?
- Problem in thinking recursively. How to take recursive leap of faith?
- OCaml higher order functions
- NASM ways to create symbols local to a function and how they behave in case of recursion
- How to stop recursion after finding solution / return
- How to implement multi-level category recursion function in php?
- Identifying pattern and code for this problem
- Staircase problem - Varying base cases in different coditions
- Printing 2D array using recursion (C programming)
- Is there a generic way to make deep recursive functions work without changing system recursion limit?
- Parent value as sum of all children values within nested javascript object
- Problem with recursive calls when x only takes t time, but when 10x it needs 100t time and much slower
- Depth first search implementation: algorithm keeps on searching out only to the right
- Javascript - recursion/for loop for flattening array
- Finding a key recursively in a dictionary
- How to recursively delete list items based on its nested content
- Return by reference is consistently faster than return value and stack with recursion
- Why does this Prolog program not terminate?
- How do I know if a function is tail recursive in F#
- C Recursive directory fetcher
- Staircase problem - explanation of recursive approach
- How to resolve common children in tree and give them unique names in Python?
- Two calls inside a recursive function
- Node.js recursively list full path of files
- my recursive function keeps going even after reaching the base case
- How to (Efficiently) Find Subpaths in Recursive Trees through Cypher (Graph vs Regex)
- How to Recursively Create a Tree with Cypher (Neo4j)
- Tic-Tac-Toe with minimax can be beaten in middle row or middle column. How to fix it so it becomes unbeatable?
- Kotlin - How to recursively call a lambda function