C++ Recursion Fibonacci Series Tutorial
We’re revisiting the Fibonacci Series code of C Recursion Find Revisit Tutorial and compiling it, plus some extended functionality, via the g++ c++ compiler on a macOS command line, as per …
g++ fibonacci_series.cpp -o fibonacci_series.out
… regarding the changed fibonacci_series.cpp code. Today’s tutorial picture displays the execution run involving the interactive input as per …
./fibonacci_series.out
How many numbers are there in your fibonacci sequence (-ve for in a row): 23
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657
0, 1
0 + 1 = 1
0, 1, 1
0 + 1 = 1
0, 1, 1, 2
1 + 1 = 2
0, 1, 1, 2, 3
1 + 2 = 3
0, 1, 1, 2, 3, 5
2 + 3 = 5
0, 1, 1, 2, 3, 5, 8
3 + 5 = 8
0, 1, 1, 2, 3, 5, 8, 13
5 + 8 = 13
0, 1, 1, 2, 3, 5, 8, 13, 21
8 + 13 = 21
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
13 + 21 = 34
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
21 + 34 = 55
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
34 + 55 = 89
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
55 + 89 = 144
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
89 + 144 = 233
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
144 + 233 = 377
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
233 + 377 = 610
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
377 + 610 = 987
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
610 + 987 = 1597
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
987 + 1597 = 2584
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
1597 + 2584 = 4181
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
2584 + 4181 = 6765
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
4181 + 6765 = 10946
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
6765 + 10946 = 17711
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657
10946 + 17711 = 28657
… using the C++ command line code …
// Fibonacci sequence
// Number in series interactively or via command line argument
// fibonacci_series.cpp
// RJM Programming - December, 2022
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char aline[500];
int done=0;
int last=-1;
char oneline[500];
char lblanks[500];
//int nums[]={0,1};
int lastf=0;
int lastlastf=0;
int countFibonacci(int i) { // Recursive function
int fibonacci;
if (i == 0) { return 0; } else if (i == 1) { if (done == 0) { done=1; sprintf((aline + strlen(aline)), "1%s", " "); } return 1; }
fibonacci = countFibonacci(i-1) + countFibonacci(i-2);
if (fibonacci > last) {
strcpy(aline, lblanks);
strcat(aline, oneline);
//sprintf((aline + strlen(aline)), "%d%s", fibonacci, ", ");
sprintf((aline + strlen(aline)), "%d%s", fibonacci, " ");
//nums[1]=fibonacci;
}
last=fibonacci;
return fibonacci;
}
int main(int argc, char *args[]) {
char delim[3]=", ";
char explanation[5000];
int nsize = 0, fibonacci, i, j, k;
char catend[20];
// Check for argument 1 number in series
if (argc > 1) {
for(i=0; i<strlen(args[1]); i++) {
if (args[1][i] == '-' || (args[1][i] >= '0' && args[1][i] <= '9')) {
nsize = nsize;
} else if (args[0][i] != '-') {
nsize--;
}
}
if (nsize == 0) sscanf(args[1], "%d", &nsize);
}
strcpy(explanation, "\n\n");
strcpy(aline, "0, ");
oneline[0]=0;
lblanks[0]=0;
if (argc <= 1) { //nsize <= 0) {
//printf("How many numbers are there in your fibonacci sequence (-ve for in a row): ");
printf("How many numbers are there in your fibonacci sequence: ");
scanf(" %d", &nsize);
}
//if (nsize > 0) { strcpy(delim, "\n\0"); }
for (i=-5; i<=(int) abs(nsize * 3); i++) {
sprintf((lblanks + strlen(lblanks)), "%s", " ");
}
k=strlen(lblanks);
strcpy(aline, lblanks);
strcat(aline, "0, ");
for (i=0; i<=(int) abs(nsize); i++) {
fibonacci = countFibonacci(i);
if (i == (int) abs(nsize)) {
printf("%d", fibonacci);
sprintf((oneline + strlen(oneline)), "%d%s", fibonacci, "\0");
if (strstr(aline, "1")) {
if (lastf != 0) {
sprintf(catend, "%d%s%d%s%d%s", lastlastf, " + ", lastf, " = ", fibonacci, "\n");
} else {
sprintf(catend, "%d%s%d%s%d%s", lastlastf, " + ", 1, " = ", fibonacci, "\n");
}
strcat(explanation, strcat(strcat(aline, "\n "), catend));
}
//oneline[0]=0;
aline[0]=0;
k-=2;
sprintf(lblanks, "%s", "\0");
for (j=0; j<k; j++) {
sprintf((lblanks + strlen(lblanks)), "%s", " ");
}
sprintf(aline, "%s%s", lblanks, "\0");
strcat(aline, "0, ");
lastlastf=lastf;
lastf=fibonacci;
} else {
printf("%d%s", fibonacci, delim);
sprintf((oneline + strlen(oneline)), "%d%s%s", fibonacci, delim, "\0");
if (strstr(aline, "1")) {
if (lastf != 0) {
sprintf(catend, "%d%s%d%s%d%s", lastlastf, " + ", lastf, " = ", fibonacci, "\n");
} else {
sprintf(catend, "%d%s%d%s%d%s", lastlastf, " + ", 1, " = ", fibonacci, "\n");
}
strcat(explanation, strcat(strcat(aline, "\n "), catend));
}
//oneline[0]=0;
aline[0]=0;
k-=2;
sprintf(lblanks, "%s", "\0");
for (j=0; j<k; j++) {
sprintf((lblanks + strlen(lblanks)), "%s", " ");
}
sprintf(aline, "%s%s", lblanks, "\0");
strcat(aline, "0, ");
lastlastf=lastf;
lastf=fibonacci;
}
}
//strcat(explanation, strcat(oneline, " a new line\n"));
printf("\n%s\n", explanation);
}
Previous relevant C Recursion Find Revisit Tutorial is shown below.
C Recursion Find Revisit Tutorial
Yesterday’s C Recursion Revisit Tutorial had us finding a macOS Xcode produced executable via the command line “find” command. We find this excellent “find” command trades off the time it takes for the convenience to the user. And this came into play when we noted, from yesterday’s …
find / -name 'Fibonacci' 2> /dev/null
… a mix of executable and non-executable files, causing a degree of confusion, and yet online published alternatives such as find / -name ‘Fibonacci’ -type f -executable 2> /dev/null just didn’t work, and some solutions, such as an xargs one might need to wait for the whole list to be produced before producing any (hence our trades off assertion). So, what else? Well, macOS “find” has this useful “-ls” switch as per …
-ls This primary always evaluates to true. The following information
for the current file is written to standard output: its inode
number, size in 512-byte blocks, file permissions, number of hard
links, owner, group, size in bytes, last modification time, and
pathname. If the file is a block or character special file, the
major and minor numbers will be displayed instead of the size in
bytes. If the file is a symbolic link, the pathname of the
linked-to file will be displayed preceded by ‘->’. The format
is identical to that produced by ls -dgils.
… that brings along information at each record that could help, and means we can pipe some extra (thanks to this useful link for ideas) …
find / -name 'Fibonacci' -ls 2> /dev/null | grep 'rwx' | grep -v 'drwx' | rev | cut -d' ' -f 1 | rev
… to narrow the result set down to just executables for the longer “find” command line “parented” command set. And the result is? Yes, both files found were Xcode executables which worked, as you can see at today’s tutorial picture.
A word of warning here is that we do not know the behaviour, with methodology above, should filenames contain any blank characters.
Previous relevant C Recursion Revisit Tutorial is shown below.
C Recursion Revisit Tutorial
Back in October, 2013 we presented C Recursion Primer Tutorial as a C++ ( but really just straight C code) Xcode (IDE) project on Mac OS X. That’s a long time ago, looking at it from late in 2021. So what’s the go now with …
- macOS Big Sur v11.6 …
- Xcode Version 13.0 (13A233)
… and while we are there, tweak the main.cpp code because we’ve never found a “project revisit” yet, where we didn’t want to change something.
You might be pleased to know that the Xcode Version 13.0 (13A233) way to setup this project …
- click Xcode (macOS desktop) icon
- File -> New -> Project…
- macOS (tab) … Application (section) … Command Line Tool … click Next
- Product Name … fill in a suitable project name (eg. Fibonacci)
- Language -> C … click Next
- we just edited the project’s main.c for today’s “Fibonacci series revisit with delimitation selection“
… does not require any “code signing”. Forgotten what C looks like? A really simple C “main.c” can look like …
// Fibonacci sequence
// Number in series interactively or via command line argument
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int countFibonacci(int i) { // Recursive function
int fibonacci;
if (i == 0) { return 0; } else if (i == 1) { return 1; }
fibonacci = countFibonacci(i-1) + countFibonacci(i-2);
return fibonacci;
}
int main(int argc, char *args[]) {
char delim[3]=", \0";
int nsize = 0, fibonacci, i;
// Check for argument 1 number in series
if (argc > 1) {
for(i=0; i<strlen(args[1]); i++) {
if (args[1][i] == '-' || (args[1][i] >= '0' && args[1][i] <= '9')) {
nsize = nsize;
} else if (args[0][i] != '-') {
nsize--;
}
}
if (nsize == 0) sscanf(args[1], "%d", &nsize);
}
if (argc <= 1) { //nsize <= 0) {
printf("How many numbers are there in your fibonacci sequence (-ve for in a row): ");
scanf(" %d", &nsize);
}
if (nsize > 0) { strcpy(delim, "\n\0"); }
for (i=0; i<=(int) abs(nsize); i++) {
fibonacci = countFibonacci(i);
if (i == (int) abs(nsize)) { printf("%d", fibonacci); } else { printf("%d%s", fibonacci, delim); }
}
printf("\n");
}
Did you know?
Am sure we can hear a lot of you say …
Isn’t the “Command Line” bit of “Command Line Tool” a bit removed from how you Run the C program in Xcode?
We’d agree. But every time you successfully Compile in Xcode a C (or C++) program, behind the scenes a [ProjectName] executable is created in a folder on your macOS computer. We found where via …
find / -name 'Fibonacci' 2> /dev/null
… “Fibonacci” being our [ProjectName] today … and got back …
/System/Volumes/Data/private/var/folders/y2/tw11n9vj5wv77xybybymdld00000gn/T/ba4bf3d76352a83c42e6ccf2829b5dd567ea7140/Fibonacci
/System/Volumes/Data/Users/user/Library/Developer/Xcode/DerivedData/Fibonacci-ghevtgngocmwbcbpmalympfdifht/Build/Products/Debug/Fibonacci
/System/Volumes/Data/Applications/MAMP/htdocs/Fibonacci
/System/Volumes/Data/Applications/MAMP/htdocs/Fibonacci/Fibonacci
/private/var/folders/y2/tw11n9vj5wv77xybybymdld00000gn/T/ba4bf3d76352a83c42e6ccf2829b5dd567ea7140/Fibonacci
/Users/user/Library/Developer/Xcode/DerivedData/Fibonacci-ghevtgngocmwbcbpmalympfdifht/Build/Products/Debug/Fibonacci
/Applications/MAMP/htdocs/Fibonacci
/Applications/MAMP/htdocs/Fibonacci/Fibonacci
… and ruling out the Xcode project last two places (which are distinct from where Xcode creates the executable) we deduced …
/System/Volumes/Data/Users/user/Library/Developer/Xcode/DerivedData/Fibonacci-ghevtgngocmwbcbpmalympfdifht/Build/Products/Debug/Fibonacci -9
… would get us …
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
… as it should … on the “Command Line” (in Terminal application of macOS).
More macOS command line “find” command refinement thoughts tomorrow!
Previous relevant C Recursion Primer Tutorial is shown below.
C Recursion Primer Tutorial
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition. Specifically this defines an infinite number of instances (function values), using a finite expression that for some instances may refer to other instances, but in such a way that no loop or infinite chain of references can occur. The term is also used more generally to describe a process of repeating objects in a self-similar way.
Recursion is not just applicable to C. Already we have shown the same scenario, which you can compare and contrast, here, in Java, with Java Recursion Primer Tutorial, shown below. It is a good technique to use in many programming applications unless its use becomes too esoteric. It is usually true that a non-recursive technique can be used in place of the recursive technique. As you might guess, you can reduce the size of your code using recursion in your code. Recursive functions need an “anal” hard coded return, ahead of time, for the end-of-the-line value returned … as you see here for when i=1 or i=0 … if you don’t do this, it may be that your recursive function contributes to infinite looping … the stuff of nightmares.
Today’s tutorial in C(++) in Xcode shows you a way to find the path to your executable, the knowledge of which can then be applied to run the executable from a (Mac Terminal) Linux bash command line, as shown in the picture above and the last slide of the tutorial.
Link to Recursion information … via Wikipedia (as per information above).
This tutorial shows the use of a recursive function used to show the Fibonacci Sequence of a designated sequence size, both interactively or via (Mac Terminal application Linux bash) command line arguments.
Liber Abaci also posed, and solved, a problem involving the growth of a population of rabbits based on idealized assumptions. The solution, generation by generation, was a sequence of numbers later known as Fibonacci numbers. The number sequence was known to Indian mathematicians as early as the 6th century,[10][11][12] but it was Fibonacci’s Liber Abaci that introduced it to the West.
In the Fibonacci sequence of numbers, each number is the sum of the previous two numbers, starting with 0 and 1. This sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 … [13]
The higher up in the sequence, the more closely the ratio of two consecutive Fibonacci numbers will approach the golden ratio (approximately 1 : 1.618 or 0.618 : 1).
Link to Fibonacci Sequence information … via Wikipedia (as per information above).
Link to … Elementary my dear Watson! … wow.
Download programming code and rename to main.cpp or main.c … depending on your environment.
If this was interesting you may be interested in this too.
Previous relevant (compare and contrast) Java Recursion Primer Tutorial is shown below.
Java Recursion Primer Tutorial
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition. Specifically this defines an infinite number of instances (function values), using a finite expression that for some instances may refer to other instances, but in such a way that no loop or infinite chain of references can occur. The term is also used more generally to describe a process of repeating objects in a self-similar way.
Recursion is not just applicable to Java. It is a good technique to use in many programming applications unless its use becomes too esoteric. It is usually true that a non-recursive technique can be used in place of the recursive technique. As you might guess, you can reduce the size of your code using recursion in your code. Recursive functions need an “anal” hard coded return, ahead of time, for the end-of-the-line value returned … as you see here for when i=1 or i=0 … if you don’t do this, it may be that your recursive function contributes to infinite looping … the stuff of nightmares.
Link to Recursion information … via Wikipedia (as per information above).
This tutorial shows the use of a recursive function used to show the Fibonacci Sequence of a designated sequence size.
Liber Abaci also posed, and solved, a problem involving the growth of a population of rabbits based on idealized assumptions. The solution, generation by generation, was a sequence of numbers later known as Fibonacci numbers. The number sequence was known to Indian mathematicians as early as the 6th century,[10][11][12] but it was Fibonacci’s Liber Abaci that introduced it to the West.
In the Fibonacci sequence of numbers, each number is the sum of the previous two numbers, starting with 0 and 1. This sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 … [13]
The higher up in the sequence, the more closely the ratio of two consecutive Fibonacci numbers will approach the golden ratio (approximately 1 : 1.618 or 0.618 : 1).
Link to Fibonacci Sequence information … via Wikipedia (as per information above).
Link to … Elementary my dear Watson! … wow.
Download programming code and rename to fibonacciRecursive.java
If this was interesting you may be interested in this too.
If this was interesting you may be interested in this too.
If this was interesting you may be interested in this too.
If this was interesting you may be interested in this too.
If this was interesting you may be interested in this too.
