[PYTHON] Sample program for finding Fibonacci sequence

When I was thinking about FizzBuzz problem, I also programmed the problem of "Create a program that generates and displays 45 Fibonacci sequences (for the time being)". I'm starting to wonder if it could be a kind of indicator for. See the tags in this article and the comment text in the sample code for what you want to say.

The execution of the following sample program (excluding comments) has been confirmed on this site.

For C

fib.c


#include <stdio.h>

// #define NOT_TAILRECUR

#ifdef NOT_TAILRECUR
unsigned long long fib(int x)
{
  if (x == 0)
    return (0);
  else
  if (x == 1)
    return (1);
  else
    return (fib(x-1) + fib(x-2));
}
#else
unsigned long long fib_r(
  int x,
  unsigned long long a,
  unsigned long long b)
{
  if (x == 0)
    return (a);
  else
    return (fib_r(x-1, b, a+b));
}
unsigned long long fib(int x)
{
  return (fib_r(x, 0, 1));
}
#endif

int main(void)
{
  for (int n = 0; n < 45; n++)
    printf("%llu ", fib(n));
  printf("\n");
  return (0);
}

For Python

fib.py


#### not tail-recur
#def fib(x):
#    if x == 0:
#      return (0)
#    elif x == 1:
#      return (1)
#    else:
#      return (fib(x-1) + fib(x-2))

def fib(x):
  def fib_r(x,a,b):
      if x == 0:
        return (a)
      else:
        return (fib_r(x-1, b, a+b))
  return (fib_r(x,0,1))

for i in range(45):
  print(fib(i), "", end="")

For Scheme

fib.scm


;;;; not tail-recur
;(define fib
;  (lambda (x)
;    (cond ((equal? x 0) 0)
;          ((equal? x 1) 1)
;          (else
;            (+ (fib (- x 1)) (fib (- x 2)))))))

(define fib
  (lambda (x)
    (let loop ((x x) (a 0) (b 1))
      (if (equal? x 0) a (loop (- x 1) b (+ a b))))))

(print (map fib (iota 45)))

Recommended Posts

Sample program for finding Fibonacci sequence
Thank you for the Fibonacci sequence.
[Python] A program for finding the Fibonacci sequence (recursive function, divide-and-conquer method, dynamic programming method)
A shell program that displays the Fibonacci sequence
List of sample program distribution sites for python books
Program for studying statistics
Implementation of Fibonacci sequence
[Python] Sample code for Python grammar