Fibonacci strings generation#8295
Sign in

Fibonacci strings generation (Editorial)

Implement a recursive function that generates the -th Fibonacci string.

Algorithm implementation

The function f returns the -th Fibonacci string.

string f(int n)
{
  if (n == 0) return "a";
  if (n == 1) return "b";
  return f(n-1) + f(n-2);
}

The main part of the program. Read the input value and print the -th Fibonacci string.

cin >> n;
cout << f(n) << endl;

Algorithm implementation — without STL

The function f returns the -th Fibonacci string.

void f(int n)
{
  if (n == 0)
  {
    printf("a"); return;
  }
  if (n == 1)
  {
    printf("b"); return;
  }
  f(n-1);
  f(n-2);
}
C++

The main part of the program. Read the input value and print the -th Fibonacci string.

scanf("%d",&n);
f(n); printf("\n");

Java implementation

import java.util.*;

public class Main
{
  static String f(int n)
  {
    if (n == 0) return "a";
    if (n == 1) return "b";
    return f(n - 1) + f(n - 2);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    System.out.println(f(n));
    con.close();
  }
}
Java

Python implementation

The function f returns the -th Fibonacci string.

def f(n):
  if n == 0:
    return "a"
  elif n == 1:
    return "b"
  else:
    return f(n-1) + f(n-2)
Python

The main part of the program. Read the input value and print the -th Fibonacci string.

n = int(input())
print(f(n))