递归斐波那契计算的可视化

Question

有没有program/website可以可视化递归斐波那契计算的图形。我想显示需要多少递归步骤。

Answer 1

我发现这是一个巧妙的小挑战，让我分享一下我的实现：

var canvas = document.getElementById("canvas");
var width = canvas.width;
var height = canvas.height;
var ctx = canvas.getContext("2d");

var FN = 8;
var FONT_SIZE = 11; // in points
var SHOW_BOXES = false;
var SHOW_DISCS = true;
var SHOW_FIB_N = true;

function Tree(fn) {
  var pdata = {};
  pdata.lhs = null;
  pdata.rhs = null;
  pdata.fn = fn;

  this.getLeft = function() { return pdata.lhs; };
  this.setLeft = function(node) { pdata.lhs = node; };
  this.getRight = function() { return pdata.rhs; };
  this.setRight = function(node) { pdata.rhs = node; };
  this.getFn = function() { return pdata.fn; };
}

function fib(n) {
  if(n == 0)
    return new Tree(0);
  if(n == 1)
    return new Tree(1);
  else {
    var lhs = fib(n-1);
    var rhs = fib(n-2);
    var root = new Tree(lhs.getFn() + rhs.getFn());
    root.setLeft(lhs);
    root.setRight(rhs);
    return root;
  }
}

var root = fib(FN);

function Box(x0, y0, x1, y1) {
  if(arguments.length < 4) {
    x0 = 1;
    y0 = 1;
    x1 = -1;
    y1 = -1;
  }

  this.x0 = x0;
  this.y0 = y0;
  this.x1 = x1;
  this.y1 = y1;

  this.width = function() { return this.x1 - this.x0; };
  this.height = function() { return this.y1 - this.y0; };

  this.offset = function(x, y) {
    this.x0 += x;
    this.y0 += y;
    this.x1 += x;
    this.y1 += y;
  };

  this.extend = function(x, y) {
    if(this.x1 < this.x0 || this.y1 < this.y0) {
      this.x0 = x;
      this.x1 = x;
      this.y0 = y;
      this.y1 = y;
    } else {
      this.x0 = this.x0 < x ? this.x0 : x;
      this.y0 = this.y0 < y ? this.y0 : y;
      this.x1 = this.x1 > x ? this.x1 : x;
      this.y1 = this.y1 > y ? this.y1 : y;
    }
  }
};

(function () {
  // assume spheres of radius 0.5
  function setBounds(node, offX, offY) {
    var bbox = new Box(offX, offY, offX + 1, offY + 1);
    if(node.getLeft() != null || node.getRight() != null) {
      var lhs = node.getLeft(), rhs = node.getRight();
      if(lhs != null) {
        setBounds(lhs, offX + 0, offY + 1.1);
        bbox.extend(lhs.bbox.x0, lhs.bbox.y0);
        bbox.extend(lhs.bbox.x1, lhs.bbox.y1);
      }
      if(rhs != null) {
        setBounds(rhs, offX + (lhs != null ? lhs.bbox.width() : 0), offY + 1.1);
        bbox.extend(rhs.bbox.x0, rhs.bbox.y0);
        bbox.extend(rhs.bbox.x1, rhs.bbox.y1);
      }
    }
    node.bbox = bbox;
  }
  setBounds(root, 0, 0);
})();

var transf = (function() {
  var b = 2;
  var sx = (width - 2 * b) / root.bbox.width();
  var sy = (height - 2 * b) / root.bbox.height();
  return {
    ox: b / sx - root.bbox.x0,
    oy: b / sx - root.bbox.y0,
    sx: sx,
    sy: sy,
  };
})();
transf.smin = Math.min(transf.sx, transf.sy);

ctx.clearRect(0, 0, width, height);
(function(g) {
  g.font = FONT_SIZE + "pt Arial";
  g.textAlign = "center";
  g.strokeStyle = "#000000";
  function draw(node, pX, pY) {
    if(node == null) return;
    var cX = (node.bbox.x0 + node.bbox.x1) / 2;
    var cY = (node.bbox.y0 + 0.5);
    var radius = 0.475;
    cX = transf.sx * (cX + transf.ox);
    cY = transf.sy * (cY + transf.oy);
    radius *= transf.smin;
    draw(node.getLeft(), cX, cY);
    draw(node.getRight(), cX, cY);
    if(SHOW_BOXES) {
      g.fillStyle = "#ff0000";
      g.beginPath();
      g.moveTo(transf.sx * (node.bbox.x0 + transf.ox), transf.sy * (node.bbox.y0 + transf.oy));
      g.lineTo(transf.sx * (node.bbox.x1 + transf.ox), transf.sy * (node.bbox.y0 + transf.oy));
      g.lineTo(transf.sx * (node.bbox.x1 + transf.ox), transf.sy * (node.bbox.y1 + transf.oy));
      g.lineTo(transf.sx * (node.bbox.x0 + transf.ox), transf.sy * (node.bbox.y1 + transf.oy));
      g.closePath();
      g.stroke();
    }
    if(SHOW_DISCS) {
      if(arguments.length >= 3) {
        g.beginPath();
        g.moveTo(pX, pY);
        g.lineTo(cX, cY);
        g.stroke();
      }
      g.fillStyle = "#ff0000";
      g.beginPath();
      g.arc(cX, cY, radius, 0, 2 * Math.PI);
      g.fill();
      g.stroke();
    }
    if(SHOW_FIB_N) {
      g.fillStyle = "#0000ff";
      g.fillText(node.getFn(), cX, cY + FONT_SIZE / 2);
    }
  }
  draw(root);
})(ctx);

<canvas id="canvas" width="800" height="480" />

递归斐波那契计算的可视化

Visualization of recursive Fibonacci calculation

visualization

fibonacci