Corecursion
કોમ્પ્યુટર વિજ્ઞાનમાં, કોરકર્સન એ કામગીરીનો એક પ્રકાર છે જે પુનરાવર્તન માટે બેવડા છે. જ્યારે રિકર્શન વિશ્લેષણાત્મક રીતે કામ કરે છે, બેઝ કેસથી આગળ ડેટાથી શરૂ કરીને તેને નાના ડેટામાં વિભાજિત કરે છે અને જ્યાં સુધી કોઈ બેઝ કેસ સુધી ન પહોંચે ત્યાં સુધી પુનરાવર્તન કરે છે, કોરકર્શન કૃત્રિમ રીતે કામ કરે છે, બેઝ કેસથી શરૂ કરીને તેને બનાવે છે, પુનરાવર્તિત રીતે બેઝ કેસમાંથી વધુ દૂર કરેલા ડેટાનું ઉત્પાદન કરે છે. સરળ શબ્દોમાં કહીએ તો, કોરકર્સિવ એલ્ગોરિધમ્સ ડેટાનો ઉપયોગ કરે છે જે તેઓ જાતે ઉત્પન્ન કરે છે, જેમ જેમ તેઓ ઉપલબ્ધ થાય છે, અને જરૂરી બને છે, ડેટાના વધુ બિટ્સ ઉત્પન્ન કરવા માટે. એક સમાન પરંતુ અલગ ખ્યાલ જનરેટિવ રિકર્શન છે જેમાં કોરક્રશન અને રિકર્શનમાં અંતર્ગત ચોક્કસ "દિશા" નો અભાવ હોઈ શકે છે. જ્યાં પુનરાવર્તન પ્રોગ્રામ્સને મનસ્વી રીતે જટિલ ડેટા પર કામ કરવાની મંજૂરી આપે છે, જ્યાં સુધી તેમને સરળ ડેટા (બેઝ કેસો) સુધી ઘટાડી શકાય છે, ત્યાં કોરકર્શન પ્રોગ્રામ્સને મનસ્વી રીતે જટિલ અને સંભવિત અનંત ડેટા સ્ટ્રક્ચર્સ, જેમ કે સ્ટ્રીમ્સ ઉત્પન્ન કરવાની મંજૂરી આપે છે, જ્યાં સુધી તે મર્યાદિત પગલાઓના ક્રમમાં સરળ ડેટા (બેઝ કેસો) માંથી ઉત્પન્ન કરી શકાય. જ્યાં પુનરાવર્તન સમાપ્ત ન થઈ શકે, ક્યારેય પાયાની સ્થિતિ સુધી પહોંચતું નથી, ત્યાં કોરકર્સન પાયાની સ્થિતિથી શરૂ થાય છે, અને આમ તે પછીના પગલાંઓ નિર્ધારિત રીતે ઉત્પન્ન કરે છે, જો કે તે અનિશ્ચિત સમય સુધી આગળ વધી શકે છે (અને આમ કડક મૂલ્યાંકન હેઠળ સમાપ્ત થતું નથી), અથવા તે ઉત્પાદન કરતાં વધુ વપરાશ કરી શકે છે અને આમ બિન-ઉત્પાદક બની શકે છે. ઘણા કાર્યો કે જેનું પરંપરાગત રીતે પુનરાવર્તિત તરીકે વિશ્લેષણ કરવામાં આવે છે તે વૈકલ્પિક રીતે, અને દલીલપૂર્વક વધુ કુદરતી રીતે, કોરકર્સિવ કાર્યો તરીકે અર્થઘટન કરી શકાય છે જે આપેલ તબક્કે સમાપ્ત થાય છે, ઉદાહરણ તરીકે પુનરાવર્તન સંબંધો જેમ કે ફેક્ટોરિયલ. કોરક્રિસન પરિણામો તરીકે મર્યાદિત અને અનંત ડેટા સ્ટ્રક્ચર્સ બંને ઉત્પન્ન કરી શકે છે, અને સ્વ-સંદર્ભિત ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ કરી શકે છે. કોરક્રિસનનો ઉપયોગ ઘણીવાર આળસુ મૂલ્યાંકન સાથે કરવામાં આવે છે, જે સંભવિત અનંત માળખાના માત્ર મર્યાદિત સબસેટનું ઉત્પાદન કરે છે (એક જ સમયે સંપૂર્ણ અનંત માળખું ઉત્પન્ન કરવાનો પ્રયાસ કરવાને બદલે). કાર્યાત્મક પ્રોગ્રામિંગમાં કોરકર્સન એ ખાસ કરીને મહત્વપૂર્ણ ખ્યાલ છે, જ્યાં કોરકર્સન અને કોડેટા કુલ ભાષાઓને અનંત ડેટા સ્ટ્રક્ચર્સ સાથે કામ કરવાની મંજૂરી આપે છે. ઉદાહરણો કોરક્રિસનને પુનરાવર્તનથી વિપરીત સમજી શકાય છે, જે વધુ પરિચિત છે. જ્યારે કોરકર્સન મુખ્યત્વે કાર્યાત્મક પ્રોગ્રામિંગમાં રસ ધરાવે છે, ત્યારે તેને અનિવાર્ય પ્રોગ્રામિંગનો ઉપયોગ કરીને સચિત્ર કરી શકાય છે, જે પાયથોનમાં જનરેટર સુવિધાનો ઉપયોગ કરીને નીચે કરવામાં આવે છે. આ ઉદાહરણોમાં સ્થાનિક ચલોનો ઉપયોગ કરવામાં આવે છે, અને અનિવાર્યપણે (વિનાશક રીતે) મૂલ્યો સોંપવામાં આવે છે, જો કે આ શુદ્ધ કાર્યાત્મક પ્રોગ્રામિંગમાં કોરકર્સનમાં જરૂરી નથી. શુદ્ધ કાર્યાત્મક પ્રોગ્રામિંગમાં, સ્થાનિક ચલને સોંપવાને બદલે, આ ગણતરી કરેલ મૂલ્યો એક અપરિવર્તનીય ક્રમ બનાવે છે, અને પૂર્વ મૂલ્યોને સ્વ-સંદર્ભ દ્વારા એક્સેસ કરવામાં આવે છે (અનુક્રમ સંદર્ભમાં પછીના મૂલ્યો, ગણતરી કરવાના અનુક્રમમાં અગાઉના મૂલ્યો). સોંપણીઓ ફક્ત આને અનિવાર્ય નમૂનારૂપમાં વ્યક્ત કરે છે અને સ્પષ્ટપણે સ્પષ્ટ કરે છે કે ગણતરીઓ ક્યાં થાય છે, જે પ્રદર્શનને સ્પષ્ટ કરવા માટે કામ કરે છે. ફેક્ટોરિયલ રિકર્શનનું ઉત્તમ ઉદાહરણ ફેક્ટોરિયલની ગણતરી છે, જેને 0 દ્વારા પુનરાવર્તિત રીતે વ્યાખ્યાયિત કરવામાં આવે છે! : = 1 અને n! : = n × (n-1)!. આપેલ ઇનપુટ પર તેના પરિણામની પુનરાવર્તિત ગણતરી કરવા માટે, પુનરાવર્તિત કાર્ય પોતે જ એક અલગ ("નાના") ઇનપુટ સાથે (એક નકલ) કૉલ કરે છે અને તેનું પરિણામ બનાવવા માટે આ કૉલના પરિણામનો ઉપયોગ કરે છે. જ્યાં સુધી બેઝ કેસ સુધી પહોંચી ન જાય ત્યાં સુધી રિકર્સિવ કોલ એ જ કરે છે. આમ આ પ્રક્રિયામાં કોલ સ્ટેક વિકસે છે. ઉદાહરણ તરીકે, ફેક્સ (3) ની ગણતરી કરવા માટે, આ પુનરાવર્તિત રીતે ફેક્સ (2), ફેક્સ (1), ફેક્સ (0) (સ્ટેકને "વાઇન્ડિંગ અપ") કહે છે, જે બિંદુએ રિકર્શન ફેક્સ (0) = 1 સાથે સમાપ્ત થાય છે, અને પછી સ્ટેક્સ વિપરીત ક્રમમાં અનવાઇન્ડ થાય છે અને પરિણામોની ગણતરી કોલ સ્ટેક્સ સાથે પ્રારંભિક કોલ ફ્રેમ ફેક્સ (3) તરફ પાછા જતા સમયે કરવામાં આવે છે જે ફેક્સ (2) = 2 ના પરિણામનો ઉપયોગ કરીને અંતિમ પરિણામની ગણતરી 3 × 2 = 3 × ફેક્સ (2) =: ફેક્સ (3) તરીકે કરે છે અને અંતે ફેક્સ (3) = 6 પરત કરે છે. આ ઉદાહરણમાં વિધેય એક જ મૂલ્ય આપે છે. આ સ્ટેકને અનવાઇન્ડીંગને સમજાવી શકાય છે, ફેક્ટોરિયલ કોરકોર્સિવલીને, ઇટરેટર તરીકે વ્યાખ્યાયિત કરી શકાય છે, જ્યાં એક કેસ સાથે શરૂ થાય છે, પછી આ પ્રારંભિક મૂલ્યથી સંખ્યા 1,2,3 વધારવા માટે ફેક્ટોરિયલ મૂલ્યોની રચના થાય છે. ઉપરની રિકર્સિવ વ્યાખ્યામાં "ટાઇમ એરો" સાથે ઉલટું થાય છે, જેમ કે, તેને પાછળની તરફ વાંચીને કોરકર્સિવ અલ્ગોરિધમ આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે જે તમામ ફેક્ટોરિયલનો પ્રવાહ ઉત્પન્ન કરે છે. આને ચોક્કસપણે જનરેટર તરીકે લાગુ કરી શકાય છે. પ્રતીકાત્મક રીતે, નોંધ્યું છે કે આગામી ફેક્ટોરિયલ મૂલ્યની ગણતરી માટે n અને f (અગાઉના ફેક્ટોરિયલ મૂલ્ય) બંનેનો ટ્રેક રાખવાની જરૂર છે, આને આ રીતે રજૂ કરી શકાય છેઃ અથવા હાસ્કેલમાં, (\(n, f)-> (n + 1, f * (n + 1)) 'ઇટરેટ' (0,1) એટલે કે, "દરેક પગલાથી શરૂ કરીને, આગામી મૂલ્યોની ગણતરી આ રીતે કરવામાં આવે છે". આ ગાણિતિક રીતે સમકક્ષ છે અને પુનરાવર્તિત વ્યાખ્યા સાથે લગભગ સમાન છે, પરંતુ તે ભાર મૂકે છે કે ફેક્ટોરિયલ મૂલ્યો બનાવવામાં આવી રહ્યા છે, પ્રારંભિક કેસથી આગળ જતા, પહેલા પાછળની તરફ ગયા પછી ગણતરી કરવાને બદલે, બેઝ કેસ પર, ઘટાડા સાથે. કોરકર્સિવ ફંક્શનના સીધા આઉટપુટમાં માત્ર ફેક્ટોરિયલ મૂલ્યો જ હોતા નથી, પરંતુ દરેક મૂલ્ય માટે અનુક્રમમાં તેના અનુક્રમણિકા n ની સહાયક માહિતીનો પણ સમાવેશ થાય છે, જેથી જ્યારે જરૂર પડે ત્યારે તે બધામાંથી કોઈપણ એક ચોક્કસ પરિણામ પસંદ કરી શકાય. ડીનોટેશનલ સિમેન્ટિક્સ સાથે જોડાણ છે, જ્યાં પુનરાવર્તિત કાર્યક્રમોના સંકેતો આ રીતે કોરકોર્સિવ રીતે બનાવવામાં આવે છે. પાયથોનમાં, રિકર્સિવ ફેક્ટોરિયલ ફંક્શનને આ રીતે વ્યાખ્યાયિત કરી શકાય છેઃ ડેફ ફેક્ટોરિયલ (n: int)-> int: "રિકર્સિવ ફેક્ટોરિયલ ફંક્શન". જો n = = 0: વળતર 1 અન્યથાઃ વળતર n * ફેક્ટોરિયલ (n-1) આને પછી ઉદાહરણ તરીકે 5 ની ગણતરી કરવા માટે ફેક્ટોરિયલ (5) તરીકે કહી શકાય!. અનુરૂપ કોરકર્સિવ જનરેટરને આ રીતે વ્યાખ્યાયિત કરી શકાય છેઃ ડેફ ફેક્ટોરિયલ્સ (): "કોરકર્સિવ જનરેટર". n, f = 0,1 જ્યારે સાચુંઃ ઉપજ f n, f = n + 1, f * (n + 1) આ ક્રમમાં ફેક્ટોરિયલ્સનો અનંત પ્રવાહ પેદા કરે છે; તેનો મર્યાદિત ભાગ આના દ્વારા ઉત્પન્ન કરી શકાય છેઃ ડેફ n _ ફેક્ટોરિયલ્સ (n: int): k, f = 0,1 જ્યારે k <= n: ઉપજ f k, f = k + 1, f * (k + 1) આ પછી 5 સુધી ફેક્ટોરિયલ્સ ઉત્પન્ન કરવા માટે કહી શકાય! મારફતેઃ f માટે n _ ફેક્ટોરિયલ્સમાં (5): પ્રિન્ટ (f) જો આપણે માત્ર ચોક્કસ ફેક્ટોરિયલમાં જ રસ ધરાવીએ છીએ, તો માત્ર છેલ્લું મૂલ્ય લઈ શકાય છે, અથવા આપણે ઉત્પાદન અને ઍક્સેસને એક ફંક્શનમાં ફ્યુઝ કરી શકીએ છીએ, ડેફ nth _ ફેક્ટોરિયલ (n: int): k, f = 0,1 જ્યારે k <n: k, f = k + 1, f * (k + 1) રીટર્ન f. આમ એમ કહી શકાય કે કોરકર્સનનો ખ્યાલ પુનરાવર્તિત વ્યાખ્યાઓ દ્વારા પુનરાવર્તિત ગણતરી પ્રક્રિયાઓના મૂર્ત સ્વરૂપનું સ્પષ્ટીકરણ છે, જ્યાં લાગુ પડે છે. ફિબોનાકી ક્રમ એ જ રીતે, ફિબોનાકી ક્રમને આ રીતે રજૂ કરી શકાય છેઃ કારણ કે ફિબોનાકી ક્રમ એ ક્રમ 2 નો પુનરાવર્તન સંબંધ છે, કોરકર્સિવ સંબંધે બે ક્રમિક શબ્દોને ટ્રેક કરવા જોઈએ, જે એક પગલાથી આગળ વધવા માટે અનુરૂપ છે, અને આગામી પદની ગણતરીને અનુરૂપ છે. આ પછી નીચે પ્રમાણે અમલમાં મૂકી શકાય છે (સમાંતર સોંપણીનો ઉપયોગ કરીને): ડેફ ફાઇબોનાચી _ સિક્વન્સ (): a, b = 0,1 જ્યારે સાચુંઃ a a, b = b, a + b મેળવો હાસ્કેલમાં, નકશો fst ((\(a, b)-> (b, a + b)) 'પુનરાવર્તન' (0,1)) ઊંડાઈ-પ્રથમ અભિગમ દ્વારા ટ્રી ટ્રાવર્સલ ટ્રી ટ્રાવર્સલ એ પુનરાવર્તનનું ઉત્તમ ઉદાહરણ છે. બેવડું, પહોળાઈ-પ્રથમ ટ્રેવર્સલ ખૂબ જ કુદરતી રીતે કોરકર્શન દ્વારા અમલમાં મૂકી શકાય છે. પુનરાવર્તિત રીતે, કોઈ વ્યક્તિ વૃક્ષને તેના મૂળ નોડને ડેટા સ્ટ્રક્ચરમાં મૂકીને પસાર કરી શકે છે, પછી જ્યારે તે ખાલી ન હોય ત્યારે તે ડેટા સ્ટ્રક્ચર સાથે પુનરાવર્તન કરી શકે છે, દરેક પગલા પર તેમાંથી પ્રથમ નોડને દૂર કરી શકે છે અને દૂર કરેલા નોડના ચાઈલ્ડ નોડ્સને તે ડેટા સ્ટ્રક્ચરમાં પાછા મૂકી શકે છે. જો ડેટા સ્ટ્રક્ચર એક સ્ટૅક (LIFO) હોય, તો આ ડેપ્થ-ફર્સ્ટ ટ્રાવર્સલ આપે છે, અને જો ડેટા સ્ટ્રક્ચર કતાર (FIFO) હોય, તો આ પહોળાઈ-ફર્સ્ટ ટ્રાવર્સલ આપે છેઃ રિકર્શનનો ઉપયોગ કરીને, વૃક્ષની ડેપ્થ-ફર્સ્ટ ટ્રાવર્સલનો અમલ કરવામાં આવે છે, જે બદલામાં રુટ નોડના દરેક ચાઈલ્ડ નોડ્સને પુનરાવર્તિત રીતે પસાર કરે છે. આમ જ્યાં સુધી પ્રથમ ચાઈલ્ડ સબટ્રી સમાપ્ત ન થાય ત્યાં સુધી બીજી ચાઈલ્ડ સબટ્રી પર પ્રક્રિયા કરવામાં આવતી નથી. રુટ નોડનું મૂલ્ય અલગથી નિયંત્રિત કરવામાં આવે છે, પછી ભલે તે પ્રથમ ચાઈલ્ડ પસાર થાય તે પહેલાં (પ્રી-ઓર્ડર ટ્રાવર્સલમાં પરિણમે છે), પ્રથમ સમાપ્ત થયા પછી અને બીજા (ઇન-ઓર્ડર) પહેલાં, અથવા બીજા ચાઈલ્ડ નોડ સમાપ્ત થયા પછી (પોસ્ટ-ઓર્ડર)-પ્રદર્શનની સરળતા માટે વૃક્ષ દ્વિસંગી છે એમ ધારીને. કોલ સ્ટેક (રિકર્સિવ ટ્રાવર્સલ ફંક્શન ઇન્વોકેશન્સનો) એ સ્ટેકને અનુરૂપ છે જે ઉપર ઉલ્લેખિત સ્પષ્ટ LIFO સ્ટ્રક્ચર મેનીપ્યુલેશન સાથે પુનરાવર્તિત થશે. પ્રતીકાત્મક રીતે, "પુનરાવર્તન" ના અહીં બે અર્થો છે. પ્રથમ, ટ્રી ટ્રાવર્સલ કાર્યોનું પુનરાવર્તિત આહ્વાન. વધુ ચોક્કસપણે, આપણે અહીં મૂલ્યોની પરિણામી સૂચિ કેવી રીતે બનાવવામાં આવે છે તેની સાથે સંઘર્ષ કરવાની જરૂર છે. પુનરાવર્તિત, બોટમ-અપ આઉટપુટ સર્જન જમણેથી ડાબે ટ્રી ટ્રાવર્સલમાં પરિણમશે. તે વાસ્તવમાં ઇચ્છિત ડાબેથી જમણે ક્રમમાં કરવા માટે ક્રમને કેટલાક બાહ્ય માધ્યમો દ્વારા લાગુ કરવાની જરૂર પડશે, અથવા જો આઉટપુટ ઉપરથી નીચેની ફેશનમાં બનાવવામાં આવે તો તે આપમેળે પ્રાપ્ત થશે, એટલે કે. કોરકર્સિવલી. ટોપ-ડાઉન ક્રમમાં તેનું આઉટપુટ બનાવતી પહોળાઈ-પ્રથમ ટ્રાવર્સલ, મૂળ નોડથી શરૂ કરીને, તેનું મૂલ્ય આઉટપુટ કરીને, પછી પહોળાઈ-પ્રથમ સબટ્રીઝને પસાર કરીને પણ અમલમાં મૂકી શકાય છે-એટલે કે, સબટ્રીની સંપૂર્ણ સૂચિને આગળના પગલા પર પસાર કરવી (એક પણ સબટ્રી નહીં, પુનરાવર્તિત અભિગમની જેમ)-આગળના પગલા પર તેમના તમામ રુટ નોડના મૂલ્યોનું આઉટપુટ કરવું, પછી તેમના ચાઈલ્ડ સબટ્રી વગેરે પર પસાર કરવું. આ કિસ્સામાં જનરેટર કાર્ય, ખરેખર આઉટપુટ ક્રમ પોતે, કતાર તરીકે કાર્ય કરે છે. ઉપરના ફેક્ટોરિયલ ઉદાહરણની જેમ, જ્યાં અનુક્રમણિકાની સહાયક માહિતી (જે પગલું એક હતું, એન) ને આગળ ધપાવવામાં આવી હતી, તે ઉપરાંત એન! ના વાસ્તવિક આઉટપુટ ઉપરાંત, આ કિસ્સામાં બાકીની સબટ્રીની સહાયક માહિતીને આગળ ધપાવવામાં આવે છે, વાસ્તવિક આઉટપુટ ઉપરાંત. પ્રતીકાત્મક રીતે, એટલે કે દરેક તબક્કે, એક આ સ્તરના ગાંઠોમાં મૂલ્યોની સૂચિ બહાર પાડે છે, પછી આગલા સ્તરના ગાંઠો તરફ આગળ વધે છે. આ ક્રમમાંથી માત્ર નોડ મૂલ્યો પેદા કરવા માટે સહાયક ચાઈલ્ડ ટ્રી ડેટાને કાઢી નાખવાની જરૂર છે, પછી યાદીઓની સૂચિને સપાટ કરવાની જરૂર છે (મૂલ્યોને શરૂઆતમાં સ્તર (ઊંડાઈ) દ્વારા જૂથબદ્ધ કરવામાં આવે છે; સપાટ (અનગ્રુપિંગ) એક સપાટ રેખીય સૂચિ આપે છે). આ વિસ્તૃત રીતે ઉપરના સ્પષ્ટીકરણની સમકક્ષ છે. હાસ્કેલમાં, કોન્કેટમેપ fst (((v, ts)-> (રુટ વેલ્યુ ts, ચાઈલ્ડ ટ્રી ts)) 'ઇટરેટ' ([], [ફુલટ્રી]) નોંધપાત્ર રીતે, અનંત વૃક્ષને જોતાં, કોરકર્સિવ બ્રેડ્થ-ફર્સ્ટ ટ્રાવર્સલ તમામ ગાંઠોને પાર કરશે, જેમ કે મર્યાદિત વૃક્ષ માટે, જ્યારે રિકર્સિવ ડેપ્થ-ફર્સ્ટ ટ્રાવર્સલ એક શાખા નીચે જશે અને તમામ ગાંઠોને પાર કરશે નહીં, અને ખરેખર જો પોસ્ટ-ઓર્ડરને પાર કરશે, જેમ કે આ ઉદાહરણમાં (અથવા ક્રમમાં), તે કોઈ ગાંઠોની મુલાકાત લેશે નહીં, કારણ કે તે ક્યારેય પાંદડા સુધી પહોંચશે નહીં. આ અનંત ડેટા સ્ટ્રક્ચર્સ સાથે વ્યવહાર કરવા માટે પુનરાવર્તનને બદલે કોરકર્સનની ઉપયોગીતા દર્શાવે છે. અનંત શાખાઓ ધરાવતા વૃક્ષો માટે હજુ પણ એક ચેતવણી બાકી છે, જેને જગ્યાને વધુ સારી રીતે અન્વેષણ કરવા માટે વધુ સચેત ઇન્ટરલેસિંગની જરૂર છે. ડુવેટેલિંગ જુઓ. પાયથોનમાં, આને નીચે પ્રમાણે અમલમાં મૂકી શકાય છે. સામાન્ય પોસ્ટ-ઓર્ડર ડેપ્થ-ફર્સ્ટ ટ્રાવર્સલને આ રીતે વ્યાખ્યાયિત કરી શકાય છેઃ ડેફ ડીએફ (નોડ): "પોસ્ટ-ઓર્ડર ડેપ્થ-ફર્સ્ટ ટ્રાવર્સલ". જો નોડ કંઈ નથી તોઃ df (node.left) df (node.right) પ્રિન્ટ (node.value) પછી વૃક્ષના ગાંઠોના મૂલ્યોને પોસ્ટ-ઓર્ડર ઊંડાઈ-પ્રથમ ક્રમમાં છાપવા માટે df (t) દ્વારા કૉલ કરી શકાય છે. પહોળાઈ-પ્રથમ કોરકર્સિવ જનરેટરને આ રીતે વ્યાખ્યાયિત કરી શકાય છેઃ ડેફ બીએફ (વૃક્ષ): "પહોળાઈ-પ્રથમ કોરકર્સિવ જનરેટર". વૃક્ષ સૂચિ = [વૃક્ષ] જ્યારે વૃક્ષ સૂચિઃ નવી વૃક્ષ સૂચિ = [વૃક્ષ સૂચિમાં વૃક્ષ માટેઃ જો વૃક્ષ કંઈ નથીઃ ઉપજ tree.value new_tree_list.append (tree.left) new_tree_list.append (tree.right) વૃક્ષ સૂચિ = નવી વૃક્ષ સૂચિ આ પછી વૃક્ષના ગાંઠોના મૂલ્યોને પહોળાઈ-પ્રથમ ક્રમમાં છાપવા માટે કહી શકાયઃ bf (t) માં i માટેઃ છાપ (i) વ્યાખ્યા પ્રારંભિક ડેટા પ્રકારોને અમુક પ્રકારના સમીકરણના ઓછામાં ઓછા નિશ્ચિત બિંદુ (આઇસોમોર્ફિઝમ સુધી) તરીકે વ્યાખ્યાયિત કરી શકાય છે; આઇસોમોર્ફિઝમ પછી પ્રારંભિક બીજગણિત દ્વારા આપવામાં આવે છે. દ્વિસંગી રીતે, અંતિમ (અથવા અંતિમ) ડેટા પ્રકારોને પ્રકાર સમીકરણના સૌથી મોટા નિશ્ચિત બિંદુ તરીકે વ્યાખ્યાયિત કરી શકાય છે; આઇસોમોર્ફિઝમ પછી અંતિમ કોલ બીજગણિત દ્વારા આપવામાં આવે છે. જો પ્રવચનનું ક્ષેત્ર સમૂહો અને કુલ કાર્યોની શ્રેણી હોય, તો અંતિમ ડેટા પ્રકારોમાં અનંત, બિન-સ્થાપિત મૂલ્યો હોઈ શકે છે, જ્યારે પ્રારંભિક પ્રકારો નથી. બીજી બાજુ, જો પ્રવચનનું ક્ષેત્ર સંપૂર્ણ આંશિક ક્રમ અને સતત કાર્યોની શ્રેણી હોય, જે આશરે હાસ્કેલ પ્રોગ્રામિંગ ભાષાને અનુરૂપ હોય, તો અંતિમ પ્રકારો પ્રારંભિક પ્રકારો સાથે મેળ ખાય છે, અને અનુરૂપ અંતિમ કોલ બીજગણિત અને પ્રારંભિક બીજગણિત એક સમરૂપતા બનાવે છે. કોરકર્સન એ પછી પુનરાવર્તિત કાર્યોને વ્યાખ્યાયિત કરવા માટેની એક તકનીક છે જેની શ્રેણી (કોડોમેન) અંતિમ ડેટા પ્રકાર છે, જે સામાન્ય પુનરાવર્તન પુનરાવર્તિત રીતે કાર્યોને વ્યાખ્યાયિત કરે છે જેની ડોમેન પ્રારંભિક ડેટા પ્રકાર છે. નીચેની ચર્ચા હાસ્કેલમાં કેટલાક ઉદાહરણો પૂરા પાડે છે જે કોરકર્સનને અલગ પાડે છે. આશરે કહીએ તો, જો કોઈ આ વ્યાખ્યાઓને સમૂહોની શ્રેણીમાં મૂકશે, તો તે હજુ પણ કોરકર્સિવ હશે. આ અનૌપચારિક ઉપયોગ હાસ્કેલ વિશેના વર્તમાન પાઠ્યપુસ્તકો સાથે સુસંગત છે. આ લેખમાં ઉપયોગમાં લેવાતા ઉદાહરણો કોરકર્સનને વ્યાખ્યાયિત કરવાના અને તે શું છે તે સમજાવવાના પ્રયાસોની આગાહી કરે છે. ચર્ચા કોડેટા પર પ્રિમિટિવ કોરકર્શન માટેનો નિયમ ડેટા પર પ્રિમિટિવ રિકર્શન માટેનો નિયમ છે. તેના કન્સ્ટ્રકટરો પર પેટર્ન-મેચિંગ દ્વારા દલીલ પર ઉતરવાને બદલે (જેને પહેલાં, ક્યાંક બોલાવવામાં આવ્યા હતા, તેથી આપણે તૈયાર ડેટમ પ્રાપ્ત કરીએ છીએ અને તેના ઘટક પેટા-ભાગો પર પહોંચીએ છીએ, એટલે કે. "ક્ષેત્રો"), આપણે તેના "વિનાશક" (અથવા "નિરીક્ષકો", જેને પછીથી, ક્યાંક બોલાવવામાં આવશે-ભરીને પરિણામ પર ચઢીએ છીએ-તેથી આપણે ખરેખર એક કન્સ્ટ્રક્ટરને બોલાવી રહ્યા છીએ, પરિણામનો બીજો ભાગ બનાવી રહ્યા છીએ જે પછીથી અવલોકન કરવામાં આવશે). આમ કોરકર્શન (સંભવિત અનંત) કોડેટા બનાવે છે, જ્યારે સામાન્ય પુનરાવર્તન (જરૂરી મર્યાદિત) માહિતીનું વિશ્લેષણ કરે છે. સામાન્ય પુનરાવર્તન કોડેટા પર લાગુ ન પણ થઈ શકે કારણ કે તે સમાપ્ત ન પણ થઈ શકે. તેનાથી વિપરીત, જો પરિણામનો પ્રકાર ડેટા હોય તો કોરકર્સન સખત રીતે જરૂરી નથી, કારણ કે ડેટા મર્યાદિત હોવો જોઈએ. "Coq માં પ્રવાહો સાથે પ્રોગ્રામિંગઃ એક કેસ સ્ટડીઃ એરાટોસ્થેનિસની ચાળણી" માં આપણે શોધીએ છીએ કે hd (કોન્સેક એ. એસ.) = a til (કોન્સેક એ. એસ.) = s (ચાળણી પી. એસ.) = જો ડિવ પી (એચ. ડી. એસ.) હોય તો ચાળણી પી (ટી. એલ. એસ.) અન્યથા કોન્સેક (એચ. ડી. એસ.) (ચાળણી પી (ટી. એલ. એસ.)) એચ. ડી. (પ્રાઇમ એસ.) = (એચ. ડી. એસ.) ટી. એલ. (પ્રાઇમ એસ.) = પ્રાઇમ (ચાળણી (એચ. ડી. એસ.) (ટી. એલ. એસ.) જ્યાં પ્રાઇમ "સ્ટ્રીમ (એનયુ 2) પર પ્રાઇમ ઓપરેશન લાગુ કરીને મેળવવામાં આવે છે". ઉપરોક્ત સંકેતલિપીને અનુસરીને, અવિભાજ્ય સંખ્યાઓનો ક્રમ (તેમાં 0 ઉપસર્ગ સાથે) અને સંખ્યાઓના પ્રવાહોને ક્રમશઃ છાંટવામાં આવે છે, તેને હાસ્કેલમાં (\(p, s @(h: t))-> (h, ચાળણી ht) 'પુનરાવર્તન' (0, [2]) તરીકે રજૂ કરી શકાય છે. જો પ્રારંભિક પ્રવાહ તરીકે [5,10.] સાથે બોલાવવામાં આવે. અહીં હાસ્કેલનું બીજું ઉદાહરણ છે. નીચેની વ્યાખ્યા રેખીય સમયમાં ફિબોનાકી સંખ્યાઓની સૂચિ ઉત્પન્ન કરે છેઃ તંતુઓ = 0:1: (+) તંતુઓ (પૂંછડીના તંતુઓ) સાથે ઝિપ આ અનંત સૂચિ આળસુ મૂલ્યાંકન પર આધારિત છે; તત્વોની ગણતરી જરૂરી ધોરણે કરવામાં આવે છે, અને માત્ર મર્યાદિત ઉપસર્ગો હંમેશા મેમરીમાં સ્પષ્ટ રીતે રજૂ થાય છે. આ સુવિધા કોડેટાના ભાગો પરના અલ્ગોરિધમ્સને સમાપ્ત કરવાની મંજૂરી આપે છે; આવી તકનીકો હાસ્કેલ પ્રોગ્રામિંગનો એક મહત્વપૂર્ણ ભાગ છે. આ પાયથોનમાં પણ કરી શકાય છેઃ આઈટરટૂલમાંથી આયાત ટી, સાંકળ, આઇસ્લાઇસ, આઈમેપ ડેફ એડ (x, y): રીટર્ન x + y ડેફ ફાઇબોનાચી (): ડેફ ડિફર્ડ આઉટપુટ (): આઉટપુટમાં i માટેઃ યીલ્ડ i પરિણામ, c1, c2 = ટી (ડિફર્ડ આઉટપુટ (), 3) જોડી = આઈમેપ (ઉમેરો, c1, આઇસ્લાઇસ (c2,1, કંઈ નહીં)) આઉટપુટ = સાંકળ ([0,1], જોડી) આઇસ્લાઇસમાં i માટે વળતર પરિણામ (ફાઇબોનાચી (), 20): પ્રિન્ટ (i) ઝિપની વ્યાખ્યા આ તરફ દોરી જાય છેઃ ફાઈબ્સ = 0 સામાન્ય પુનરાવર્તન સ્વ-સંદર્ભિત કાર્યોનો ઉપયોગ કરે છે, પરંતુ સ્વ-સંદર્ભિત માહિતીને સમાવતું નથી. જો કે, ફિબોનાકી ઉદાહરણ માટે આ જરૂરી નથી. તેને નીચે પ્રમાણે ફરીથી લખી શકાય છેઃ ફાઈબ્સ = ફાઈબજેન (0,1) ફાઈબજેન (x, y) = x: ફાઈબજેન (y, x + y) આ પરિણામ બનાવવા માટે માત્ર સ્વ-સંદર્ભિત કાર્યનો ઉપયોગ કરે છે. જો તેનો ઉપયોગ કડક સૂચિ કન્સ્ટ્રક્ટર સાથે કરવામાં આવ્યો હોત તો તે ભાગેડુ પુનરાવર્તનનું ઉદાહરણ હશે, પરંતુ બિન-કડક સૂચિ કન્સ્ટ્રક્ટર સાથે આ સંરક્ષિત પુનરાવર્તન ધીમે ધીમે અનિશ્ચિત સમય માટે વ્યાખ્યાયિત સૂચિ બનાવે છે. કોરકર્સનને અનંત પદાર્થ ઉત્પન્ન કરવાની જરૂર નથી; કોરકર્સિવ કતાર એ આ ઘટનાનું ખાસ કરીને સારું ઉદાહરણ છે. નીચેની વ્યાખ્યા રેખીય સમયમાં ઉપર-નીચેની રીતે દ્વિસંગી વૃક્ષની પહોળાઈ-પ્રથમ પરિભ્રમણ ઉત્પન્ન કરે છે (પહેલેથી જ ઉપર ઉલ્લેખિત સપાટતાનો સમાવેશ કરે છે): માહિતી વૃક્ષ a b = પર્ણ a | શાખા b (વૃક્ષ a b) (વૃક્ષ a b) bftrav:: વૃક્ષ a b-> [વૃક્ષ a b] bftrav વૃક્ષ = વૃક્ષ ts જ્યાં ts = જીન 1 (વૃક્ષઃ ts) જીન 0 p = [] જેન લેન (લીફ p) = જીન (લેન-1) p જેન લેન (શાખા _ l r: p) = l: r: જીન (લેન + 1) p-------------------------------------------------------------- આ સૂચિ ઇનપુટ કતાર અને પરિણામ બંને તરીકે બેવડા હેતુને પૂર્ણ કરે છે (જીન લેન પી સૂચિ સાથે તેના ઇનપુટ બેક-પોઇન્ટર, પી કરતા આગળ તેનું આઉટપુટ લેન નોચ ઉત્પન્ન કરે છે). જો અને માત્ર ત્યારે જ તે મર્યાદિત હોય જો પ્રારંભિક વૃક્ષ મર્યાદિત હોય. સમાપ્તિની ખાતરી કરવા માટે કતારની લંબાઈને સ્પષ્ટપણે ટ્રેક કરવી આવશ્યક છે; જો આ વ્યાખ્યા માત્ર અનંત વૃક્ષો પર લાગુ કરવામાં આવે તો તેને સુરક્ષિત રીતે દૂર કરી શકાય છે. આ હાસ્કેલ કોડ સ્વ-સંદર્ભિત માહિતી માળખાનો ઉપયોગ કરે છે, પરંતુ તે અનિવાર્યપણે આળસુ મૂલ્યાંકન પર આધારિત નથી. તેનો સીધો અનુવાદ કરી શકાય છે, દા. ત. પ્રોલોગ જે આળસુ ભાષા નથી. જે જરૂરી છે તે ટોચ-નીચેની રીતે સૂચિ (કતાર તરીકે વપરાય છે) બનાવવાની ક્ષમતા છે. તે માટે, પ્રોલોગ પાસે પૂંછડી પુનરાવર્તન મોડ્યુલો વિપક્ષ છે (એટલે કે. સમાપ્ત થયેલ યાદીઓ ખોલો). જે યોજના, સી, વગેરેમાં પણ અનુકરણપાત્ર છે. મ્યુટેબલ ટેલ સેન્ટીનલ પોઇન્ટર સાથે લિંક કરેલી સૂચિઓનો ઉપયોગ કરીનેઃ bftrav (ટ્રી, [Tree|TS]):-bfgen (1, [Tree|TS], TS). bfgen (0, _, []):-! કતારમાં% 0 એન્ટ્રીઓ-- bfgen (N, [પર્ણ (_) |P, TS) ને બંધ કરો અને બંધ કરો-- N2 એ N-1, bfgen (N2, P, TS) છે. bfgen (N, [શાખા (_, L, R) |P], [L, R|TS]):-N2 એ N + 1, bfgen (N2, P, TS) છે. %%---------------------- બીજું ચોક્કસ ઉદાહરણ પહોળાઈ-પ્રથમ લેબલિંગની સમસ્યાનું સમાધાન આપે છે. ફંક્શન લેબલ દ્વિસંગી વૃક્ષના દરેક નોડની પહોળાઈની પ્રથમ ફેશનમાં મુલાકાત લે છે, દરેક લેબલને પૂર્ણાંક સાથે બદલે છે, દરેક અનુગામી પૂર્ણાંક છેલ્લા કરતા 1 વડે મોટો છે. આ ઉકેલ સ્વ-સંદર્ભિત માહિતી માળખાનો ઉપયોગ કરે છે, અને દ્વિસંગી વૃક્ષ મર્યાદિત અથવા અનંત હોઈ શકે છે. લેબલઃ: ટ્રી એ બી-> ટ્રી ઇન્ટ ઇન્ટ લેબલ ટી = ટીએન જ્યાં (ટીએન, એનએસ) = ગો ટી (1: એનએસ) જાઓઃઃ ટ્રી એ બી-> [ઇન્ટ]-> (ટ્રી ઇન્ટ ઇન્ટ, [ઇન્ટ]) જાઓ (લીફ _) (i: a) = (લીફ i, i + 1: a) જાઓ (શાખા _ lr) (i: a) = (શાખા i ln rn, i + 1: c) જ્યાં (ln, b) = ગો એલ એ (rn, c) = ગો આર બી અથવા પ્રોલોગમાં, સરખામણી માટે, લેબલ (ટ્રી, Tn):-લેબલ (ટ્રી, [1|Ns], Tn, Ns લેબલ (પર્ણ (_), [I|A], પર્ણ (I), [I + 1|A]). લેબલ (શાખા (_, L, R), [I|A], શાખા (I, Ln, Rn), [I + 1|C]:-લેબલ (L, A, Ln, B), લેબલ (R, B, Rn, C). એપોમોર્ફિઝમ (જેમ કે એનામોર્ફિઝમ, જેમ કે અનફોલ્ડ) એ કોરકર્શનનું એક સ્વરૂપ છે જે રીતે પેરામોર્ફિઝમ (જેમ કે કેટામોર્ફિઝમ, જેમ કે ફોલ્ડ) એ પુનરાવર્તનનું એક સ્વરૂપ છે. CoQ પ્રૂફ સહાયક કોફિક્સપોઈન્ટ આદેશનો ઉપયોગ કરીને કોરકર્શન અને કોઇનડક્શનને સપોર્ટ કરે છે. ઇતિહાસ કોરક્રિસન, જેને પરિપત્ર પ્રોગ્રામિંગ તરીકે ઓળખવામાં આવે છે, તે ઓછામાં ઓછું જ્હોન હ્યુજીસ અને ફિલિપ વેડલરને શ્રેય આપે છે; વધુ સામાન્ય સ્વરૂપો વિકસાવવામાં આવ્યા હતા. મૂળ પ્રેરણાઓમાં વધુ કાર્યક્ષમ અલ્ગોરિધમ્સ બનાવવાનો સમાવેશ થાય છે (કેટલાક કિસ્સાઓમાં બહુવિધ પાસની જરૂરિયાતને બદલે ડેટાને પસાર કરવાની મંજૂરી આપવી) અને કાર્યાત્મક ભાષાઓમાં શાસ્ત્રીય ડેટા સ્ટ્રક્ચર્સ, જેમ કે બમણી લિંક કરેલી સૂચિ અને કતારોનો અમલ કરવો. બીસિમ્યુલેશન કોઇનડક્શન રિકર્શન એનામોર્ફિઝમ નોટ્સ સંદર્ભો સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાન સ્વ-સંદર્ભ લેખો ઉદાહરણ સાથે હાસ્કેલ કોડ લેખો ઉદાહરણ તરીકે પાયથોન (પ્રોગ્રામિંગ લેંગ્વેજ) કોડ સાથે કાર્યાત્મક પ્રોગ્રામિંગ શ્રેણી સિદ્ધાંત રિકર્શન