Trusted answers to developer questions

Muhammad Ahmad

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The **Recaman's sequence** is named after its inventor, Bernardo Recaman. It's a well-known sequence that is defined by the **recurrence relation**. We can define it by recursion.

In the recurrence relation of the Recaman's sequence, at least two sequences are attributed. We form the sequence _{n} by taking _{0}

Recurrence relations must fulfill the following conditions:

**Condition 1**:**Condition 2**: The absolute difference between the term and its preceding term equal the term number$n$ .

In the recurrence relation, we subtract, or visit the previous term, if we can. Otherwise, we add, or visit next term. We'll understand this by seeing some initial terms.

Let's generate this sequence through C/C++ program.

**Program**:$n$ th number in Recaman's sequence**Input**:`n`

=`10`

**Output**:`0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, ...`

arr(0) = 0if n > 0 and the number is notalready included in the sequence,arr(n) = arr(n - 1) - n //Visit the previous number in seqelsearr(n) = arr(n - 1) + n //Visit the next number in seq

The pseudo-code for the recursive function

This pseudo-code is a function whose range is natural numbers, with ^{th} term.

// This program prints n-th number of the Recaman's sequence#include <iostream>using namespace std;// The function prints the first n terms of the Recaman's sequenceint rec_seq(int size){// Create an array to store termsint arr[size];// The very first term of the sequence is always 0arr[0] = 0;cout << arr[0]<<" ,";int i = 1;int j = 0;// Generate the rest of the terms using the recursive// formulawhile(i< size){int curr = arr[i-1] - i; //Visit the previous term on lineint j;while(j < i){// If arr[i-1] - i is negative or the term already existsif ((arr[j] == curr) || curr < 0){curr = arr[i-1] + i; // Visit the next termbreak;}j++;}arr[i] = curr;cout << arr[i] << " ,";i++;}}// Driver codeint main(){int size = 10;cout << "First "<< size << " terms are: " ;rec_seq(size);cout << "......."<<endl;return 0;}

A Raceman's sequence generator

The code chunk above generates the Recaman's sequence and saves it into an array of input size

- Line 13: The first term of the sequence is always
$0$ , that is,$a$ _{0}$=$ $0$ - Line 20: This generates the previous number by
`arr[i - 1] - i`

. - Line 27: This checks if the number generated by line 20 is already present in the array, or if it's a negative number.
- Line 29: If the number is negative or already present in the sequence, it generates the next number by
`arr[i - 1] + 1`

.

We can use Recamán's sequence to secure 2D images by

Neil Sloane has conjectured that every number eventually appears,^{ }but this has not been proved. The illustration below will give us an idea of how the algorithm produces a sequence by moving backward and forward on a number line.

RELATED TAGS

CONTRIBUTOR

Muhammad Ahmad

Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses