Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- Discussion Forums
- KX Tech
- Re: higher-order function with recursive

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

higher-order function with recursive

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2021.04.20 10:04 AM

I am new to KDB+ and q. I am trying implement higher-order function with recursive and found below code in the docs.

I could not understand how it is working.

Could you please explain below code.

q) 10 {x,sum -2#x}/ 1 1

3 REPLIES 3

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2021.04.20 10:26 AM

This is generating Fibonacci sequence, in each iteration appending the sum of last two elements.

Can also use scan

q)last flip 10{x[1],sum x}\1 1

1 2 3 5 8 13 21 34 55 89 144

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2021.04.20 11:22 AM

so basically you are looking at one of the applications of iterators (previously known as adverbs). This particular form can be compared to a "Do" loop in other programming languages. Let's have a look at the code, for simplicity let's define the function f as following

f:{x,sum -2#x}

Then your code becomes

10 f/ 1 1

On a side note this could also be written as f/[10;1 1] which might make it easier to understand. In this case / (over) acts as an accumulator, executing your function f 10 times using 1 1 as initial parameter. the result of the first iteration then becomes the input of the second iteration and so on.

what does f do?

q is executed left of right, means from right to left. -2#x takes the last two elements of x (1 1), sum sums them and the result gets concatenated to the initial input x, thus after your first iteration you get 1 1 2. This will now become the input to your second iteration. A helpful way to understand over better is to use scan \ instead of over. Scan does basically the same as over except it outputs the intermediate steps. The result of over is the last output of scan.

q)10 {x,sum -2#x}\1 1

1 1

1 1 2

1 1 2 3

1 1 2 3 5

1 1 2 3 5 8

1 1 2 3 5 8 13

1 1 2 3 5 8 13 21

1 1 2 3 5 8 13 21 34

1 1 2 3 5 8 13 21 34 55

1 1 2 3 5 8 13 21 34 55 89

1 1 2 3 5 8 13 21 34 55 89 144

Hope this helps.

More details about Iteration can be found here https://code.kx.com/q/basics/iteration/

There is also a great white paper about it here https://code.kx.com/q/wp/iterators/

And the particular DO case is explained here: https://code.kx.com/q/ref/accumulators/

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

2021.04.20 10:35 PM

Thanks Alexander for your** **explanation**.**

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Resources

Popular Links

Follow Us

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.