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.

- Printing lists recursively in Python without mutating a list
- How to return the right array for f(0), tail-call optimized Fibonacci?
- Writing Recamans sequence recursion program, why does the counter keep moving up and down?
- Getting "fully qualified" location names from a parent-child table
- Check if specific array key exists in multidimensional array - PHP
- Set Recursion Limit doesn't work in the standalone Python interpretator but works in online interpretators
- Since Java 9 HashMap.computeIfAbsent() throws ConcurrentModificationException on attempt to memoize recursive function results
- Typing for tuple or list of tuples in recursive function
- Why doesn't the "repeated" number go up in the traceback as I increase the recursion limit?
- Mypy type narrowing with recursive generic types
- Code to handle arbitrary number of for loops in Python/Numba
- Checking an integer is palindrome using recursion without using any extra reverse function
- Generating Gray codes recursively without initialising the base case outside of the function
- recursive JSON.stringify implementation
- Why by changing the position of print statement, in Fibonacci pattern, in recursion, the order of output changes?
- Populate WinForms TreeView from DataTable
- Checking whether an array is sorted via recursion
- Count number of paths on 2d-array (grid Traveller)
- Backward recursion
- My test task for trainee. Javascript - quadratic equation and game theory
- Python exceeds recursion limit
- Exactly even divisible using python recursion
- Advanced typescript: find all the values of the key "id" in a nested object
- Longest Ordered Subsequence of Vowels - Dynamic Programming
- Windows Batch File Looping Through Directories to Process Files?
- F# dynamically generated nested collection function signature cannot be unified
- Recursive CTE result is infinite
- SQL Recursion CTE infinite loop
- Recursive Bubble Sort in Java
- JS array concatenation for results of recursive flattening