Adding recursion

Problem: the function you are defining is not in the scope.



In [1]:

    
(let ((f (lambda (n) 
           (if (= n 1) 1 (f (- n 1))))))
  (f 10))









    



Traceback (most recent call last):
  File "In [1]", line 1, col 1, in 'let'
  File "In [1]", line 3, col 3, in 'f'
  File "In [1]", line 2, col 27
RunTimeError: unbound variable 'f'

Y-combinator

Derive the y-combinator



In [3]:

    
(let ((f (lambda (n f) 
           (if (= n 1) 1 (f (- n 1) f)))))
  (f 10 f))









    Out[3]:





1

Better: Put the recursive name in the scope

Make it a global
Poke it into scope

The Call Stack

Implementing recursion. Use Python's call stack.



In [1]:

    
(letrec ((f (lambda (n) 
           (if (= n 1) 1 (f (- n 1))))))
  (f 10))









    Out[1]:





1



In [ ]: