recursionfunctional-programmingiterationocamldynamic-programming# OCaml higher order functions

Somebody please explain the algorithm in this problem for OCaml.

I have the solution but I do not understand it.

Define iterup: (int * 𝛼 → 𝛼) → int → int → 𝛼 → 𝛼. Iterup takes a function which receives the current number and the accumulator. It increments the counter number from a given start to a given end and applies the function each time. The last argument is the start value of the accumulator.

The solution is

```
let rec iterup f st ed acc =
if st > ed then
acc
else
iterup f (st+1) ed (f st acc)
```

What I do not understand is why we take in both n and s as arguments to f in the last part (f n s). What does that get us to when we talk in terms of tail recursion.

Solution

The last argument provides an *accumulator* which is a very idiomatic way to achieve tail recursion in OCaml. The function provided via the `f`

argument provides a way to update that accumulator.

Every path in a recursive function either needs to be an exit from the recursion, or an update to the state passed to the function. Without at least one of each, we get stuck in unbounded recursion: an infinite loop.

Let's look at a call of `iterup`

.

```
iterup (fun a b -> a + b) 1 5 0
iterup (fun a b -> a + b) 2 5 (0 + 1)
iterup (fun a b -> a + b) 3 5 (1 + 2)
iterup (fun a b -> a + b) 4 5 (3 + 3)
iterup (fun a b -> a + b) 5 5 (6 + 4)
iterup (fun a b -> a + b) 6 5 (10 + 5)
15
```

At no point do we have to work our way back up the call stack to find the solution, so the stack space used can be optimized to be constant.

- python recursion i dont understand this output pls help me
- I'm trying to understand recursion in Tcl, but every time the recursion finishes it throws errors
- How to remove all numbers from a list in Lisp
- Calculate the total weight of segments
- Why does the expression !(cin>>word) cause infinite recursion?
- What's the best way to recursively traverse a BinaryTree in Java without void methods?
- can anybody explains the code and also recursion tree
- Is it possible to limit the depth of a recursive directory listing in S3 bucket?
- takeWhile implementation in JavaScript - Looking for better ideas
- I used a recursive function to modify a string, but if the string is too large the function returns nothing
- How to Compress Paths in SQL Server Using Recursive CTE with Node Visibility Conditions?
- Why this recursion example in ocaml doesn't work for negative number?
- Recursive loop on a list to print xml with indent
- Big O of algorithm that steps over array recursively
- Powerset of a list with equal elements in Java
- Recursion in FP-Growth Algorithm
- Passing list to function results in no case clause matching
- Convert tree-like structure formatted as a string using indentations to a list of paths
- Recursive function fails depending on lexical scoping
- Creating a list of interleaved elements: Prolog
- How to get the recursive difference formula between two columns in excel
- Get all values and associative keys as a flat array from a multidimensional array of variable depth/structure
- How can I make a recursive square root in Python?
- Issue with Memoization in Recursive Function for Finding Combinations Summing to Target
- Finding a continuous route through a list of lists
- How to get all possible combinations of elements in a given list?
- How can I get the nested keys of a map in clojure?
- Computing Checkmate Correctly
- Node.js recursively list full path of files
- C# Binary Search of a number in an array using recursion