Recursion Practise

Recursion.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "from typing import List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Excercise 1\n",
    "\n",
    "Write a funtion that calculate the sum of all integers up to n, assuming n is 10:  \n",
    "sum = 1 + 2 + 3 + ... + 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_sum(cur):\n",
    "    if cur == 1:\n",
    "        return 1\n",
    "    return cur + sum(cur-1)\n",
    "\n",
    "def tail_recursion_sum(cur, total=0):\n",
    "    if cur == 0:\n",
    "        return total\n",
    "    return tail_recursion_sum(cur-1, cur+total)\n",
    "\n",
    "def loop_sum(cur):\n",
    "    sum = 0\n",
    "    for i in range(1,cur+1):\n",
    "        sum += i\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = randint(1,100)\n",
    "recursive_sum(i) == loop_sum(i) == tail_recursion_sum(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Excercise 2\n",
    "\n",
    "Calculate the ith Fibonacci sequence:  \n",
    "0, 1, 1, 2, 3, 5, 8, 13, 21, 34..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_fib(ith, counter, pre, cur):\n",
    "    if ith < counter + 2:\n",
    "        return pre\n",
    "    \n",
    "    return recursive_fib(ith, counter+1, cur, pre+cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loop_fib(ith, pre, cur):\n",
    "    counter = 0\n",
    "    sum = 0\n",
    "    while counter < ith-2:\n",
    "        sum = pre + cur\n",
    "        tmp = cur\n",
    "        cur = sum\n",
    "        pre = tmp\n",
    "        counter += 1\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = randint(1,100)\n",
    "recursive_fib(i,0,0,1) == loop_fib(i,0,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Excercise 3\n",
    "Count the number of digits of a positive number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_count(n, counter):\n",
    "    if n / 10 < 1:\n",
    "        return counter\n",
    "    \n",
    "    return recursive_count(n/10, counter+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loop_count(n):\n",
    "    counter = 1\n",
    "    i = n\n",
    "    while i >= 10:\n",
    "        i = i/10\n",
    "        counter += 1\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = randint(1000,100000)\n",
    "recursive_count(i,1) == loop_count(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Excercise 4\n",
    "Find the largest integer in a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recursive_find_max(l:List[int], max):\n",
    "    if not l:\n",
    "        return max\n",
    "    \n",
    "    if max < l[0]:\n",
    "        max = l[0]\n",
    "    \n",
    "    return recursive_find_max(l[1:], max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loop_find_max(l:List[int]):\n",
    "    max = 0\n",
    "    for i in l:\n",
    "        if max < i:\n",
    "            max = i\n",
    "    return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[67, 96, 14, 65, 44]\n",
      "max = 96\n",
      "max = 96\n"
     ]
    }
   ],
   "source": [
    "l = []\n",
    "for i in range(5):\n",
    "    l.append(randint(1,100))\n",
    "\n",
    "print(l)\n",
    "print('max = ' + str(recursive_find_max(l, 0)))\n",
    "print('max = ' + str(loop_find_max(l)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}